Algorithms are important because they help programmers to create efficient and error free programs. In real life, there exist many different algorithms for the same problem. Therefore, to realize which algorithm will be best for our problem requires clear understanding of some founding concept of algorithms, which we will discuss here. Two important reasons that provide efficiency to your computer program are as follows :
1. To improve the efficiency of a computer program – With the best algorithm, a computer program will be able to produce very accurate results. An algorithm can be used to improve the speed at which a program executes a problem.
2.Proper utilization of resources :- The right choice of an algorithm will ensure that a program consumes the least amount of resources includes memory, process time, etc.
Lets explore the following videos to develop good understanding of the founding principles of ALGORITHMS. [Click the following links to watch the video]
- Introduction to Computer Algorithms
- Abstract Data Types (ADT) [read text] [download text]
- Tips for Analyzing Computer Algorithms [read text] [download text]
- What are Computational Models
- What are loop Invariants
- Lets understand Mathematical Model of Computation [read text] [download text]
- Basics of Asymptotic Notations [read text]
You are invited to raise queries by writing your question in the box given below
Expertvision 
I confused and cannot full understand what is considered to be an Abstract Data Type and what is not an ADT?
Also, is an Array an ADT?
What about Heap, Stack ? Are they considered as an ADT or not ?
Abstract Data Type – the type that defined methods by the user. For example, Stack ADT. It contains push(), pop(), size() and other methods. It is ADT. To implement it, the user uses different programming language features such as arrays, pointers, and others. After that, it becomes a data structure.
It is possible to define array ADT.
It is better to THINK about ADT as an object(instance of the class) that implements ‘interface’ or abstract class that defines how this object should behave. Interface – declares set of functions that must be defined by classes implementing this. So in order to understand ADT do not separate the notion of object from interface think of it as ‘one unit’
ADT is a mathematical model of Data Type and examples of types are Lists, Trees, Stacks and Queues. Also, ADT refers to set of Values and Operations.
Can you show some examples of Best and Average case somplexity?
Also I would like to see some examples of them. But theoretically, I think these explanation is very useful and clear!
For Best case Complexity:
It is the minimum time or steps taken by an algorithm to solve a problem.
Average case Complexity:
It is in between best case and worst case.
I mean the average time or steps taken by an algorithm to solve a problem.
I also be happy if someone show some real examples of these cases.
It is abstract if you can take an example from life like Queue you can imagine real queue where people want to buy something you see that person that come earlier will go earlier. Or stack you can imagine stack as a box with different books box is little beet bigger than book, but deep so you can put only one book by one and to take first book you will be needed to take all books from the box that are above
no problem ..next time don’t forgot to mention it
I know it, but it is better to see in practiсe
Let’s say you are searching an array of unsorted numbers for the number 5 using linear search.
Best Case:
Suppose that your array is [5,3,7,8,2,3,6]. When you begin searching it immediately finds the number 5 at the beginning which is the best case scenario because it is doing only one comparison.
Average Case:
Suppose that your array is [6,2,8,5,1,7,3]. When you begin searching it finds the number in 4 iterations. Because the worse case scenario is 7 iterations, and it happens when the searching number is at the end or does not exist in the array, so your 4 iterations is more like the middle of worst and best. That is why it can be considered average case scenario
Most of the time you do not need to know about Best and Average cases, instead you need to worry about worst case, because it guarantees that running time of particular algorithm do not exceed worst case time. For example, you have an array [6, 5, 4, 3, 2, 1], that is the worst scenario for sorting. As long as we know that, we may decide which algorithm to use in order to get sorted array. Knowing the worst case of bubble sort(n^2) we may immediately exclude that one, due to variety of better algorithms, such as Merge sort and Quick sort,(nlogn) which worst case is less.
What are those 6 subsets of cardinality 2 of 4 elements? “Tips for Analyzing Computer Algorithms”, 37:32 – time
{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} are those 6 subsets with cardinality 2 that we can form from A= {1,2,3,4}
6 subsets of cardinality 2 are : {1,2} , {1,3} , {1,4} , {2,3} , {2,4} , {3,4}
those 6 subsets are {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}
If you mean subset of cardinality {2,4,6} to find subset we calculate number of subsets 2^3=8 subsets.
Subsets: {2,4,6}, {2,4}, {2,6}, {4,6}, {2}, {4}, {6}, {}
Important thing to pay attention to the word “n choose k”, which means that we can have only subsets of size 2 from set with 4 elements. In other words, there are 6 ways to choose 2 elements from {1,2,3,4}.
They are {1,2}, {1,3}, {1,4}, {2, 3}, {2,4} and {3,4}.
Why we need Greedy method if it’s not guarantee to the solution? Can you give example of Greedy method in real life project
Greedy method is very popular among programmers. We need Greedy solution to produce locally optimal solution. Many algorithms and solutions rely on Greedy method
I guess with the help of Greedy Method we can divide the problem to several sub-issues and go forward to finding the solutions. The benefit of this method is that we don’t have to come back to the previous stages of the algorithm and reconsider them again. And also it can be more helpful than other methods for finding and excluding the worst case among solutions.
The best known problem is coin problem: we have collection of coins for example 1,17,20,28 and we want give 53 and we want the number of coins the minimum as possible. the greedy approach is here giving the greater coins first then giving smaller coins for example: 28+20+1+1+1+1+1=53 (num of coins 7) however this is wrong in this input because we can give 17+17+17+1+1=53 (num of coins 5). we can solve it DP and complexity O(mn) (m maxsimum value of coins)
The interesting part is if coins is 1,2,5,10 and we want to give for example 62, this greedy aprroach works 10+10+10+10+10+10+2 = 62 num of coins 7 and this is the correct answer and we need only O(n/m) (m max value of coins) complexity.
Main point is that sometimes greedy approach works and it is very faster and naiver than other approaches, but before using it we have to be 100% work in all inputs
I could not full understand the concept of Algorithm about Complexity of W(n) as in cases of Worst-case and Average-case analysis and the usage of it in operation performances
Worst-case is used to find maximum cost of algorithm (special case when the cost is minimum in a set of special inputs)
Average-case is used to find average cost by considering maximum cost of algorithm and minimum cost of algorithm.
Worst-case complexity of W(n) – it is a maximum number of operations (instructuons) to be done in particular Algorithm to solve a problem.
Average-case complexity of W(n) – it is average cost of algorithm
ADT is a mathematical model of Data Type and examples of types are Lists, Trees, Stacks and Queues. Also, ADT refers to set of Values and Operations.
During calculation of Average case, we should find values for n (n for Best case and n for Worst case) and which n should be taken for n0 always?
We take the biggest value of n between average case and worst case for n0
As I understood to define average complexity you should consider complexity of algorithm for all possible inputs, count how many degenerating and normal cases. If the number of degenerating cases divided by n tend towards 0 when n get big, then you can speak of average complexity of the overall function for normal cases.
It looks like you did not give video aboth themes that are used in our assignment but deadline is tomorrow how should we solve this?
The last 2 videos in the list are based on topics that we must to use to solve the assignment
https://ibb.co/PMXmQgM
In this part of the lectures, could you please explain why it is not O(k*n^2) instead of O(n^2)?
Because in O(k*n^2) k is just coefficient
What is the difference between Standart and Complex Abstract Data Types? Can someone clarify it by giving some proper examples?
In Standard ADTs’ design implementation we use the same design for the whole process so that it doesn’t change during till we finish the realization. Examples: Lists, Trees, Stacks, Queues.
In Complex ADT’s design implementation there might be some moderations in the process of designing and there are some logical advantages. Examples: Priority Queues, Union-Find Dictionaries.
We use Complex ADT for getting some logical advantage means in some cases to simplify the analysis of correctness of the algorithm. For example in queue elements are pulled in first-in first-out-order (FIFO) but in priority queue each element additionally has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Could you explain what the Abstract Data Type Specification is? And what kind of information it consists?
An abstract data type is a mathematical module that includes data with various operations. The implementation details are hidden, which is why it is called abstract. Abstraction allows you to regulate the complexity of a task by focusing on the logical properties of data and actions. For example array, list, queue, stack and etc. are the ADTs.
So the ADT specification is just describing how the operation behave. It describes the logical relationship among the public part of ADT which are using operations and constants. It cares about operation’s name, initial conditions, post conditions, what input operation will take and what output it will provide.
Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of value and a set of operations.
The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view. The process of providing only the essentials and hiding the details is known as abstraction.
When we solving ASYMPTOTIC NOTATIONS problems, C will be given or we should find C also?
For example, f(n)=3n+2, g(n)=n to find notation we need C , so C will be given or not?
C you can take yourself. As it was explained if you have f(n)=3n+2 and g(n)=n you will have 3n+2<= C*n. You can take C=4,5,6,7… as they are bigger than 3. But in examples you will be asked to find least upper bound, so closest upper bound for 3n is 4n (C=4).
We use asymptotic notation to describe a function f(n) in comparison to other function g(n). More precisely, lets say we find such a function cg(n) called tight upper bound for our f(n) function, that at any point n>=n0 the value of function f(n) can never be greater than the value of cg(n). We use that example (finding tight upper bound function) to analyze worst-case running time of an algorithm. All in all, f(n) function and g(n) function (to be compared to f(n)) are given and we need to c such that it makes g(n) tight-upper-bound function for f(n).
We know that ADT is defined using Specification and Design. So, the Specification of an ADT describes how the operations behave in terms of Inputs and Outputs. (Operations can be functions, methods, or procedures)
Indeed, a specification of operation includes three pieces of information that are Calling prototype, Preconditions and Postconditions.
I have a question regarding the time cost of iterating through an n-dimensional array, imagine we have a square NxN array of numbers and we need to search for a number in that array. And lets say we are doing linear search, obviously we iterate through every entry starting from position (0,0). But the interesting point begins after that, there are two ways of iterating, one way is going like this (e.g (0,0), (0,1), (0,2) … (0,n), (1,0), (1,1) …), second way is (e.g (0,0), (1,0), (2,0) … (n,0), (1,1), (2,1), … , (n,1)). In these scenarios what do you think of the costs of time in both cases? Are they the same? I am taking a square NxN dimensional array for it to be easy to understand and analyze. Explain your answer.
Yes, the time complexity will be the same, it will be n^2.
In my opinion, NxN matrix when you search by from left to right or top to bottom , in both case your worst case is n^2 but in cost of the time your second way is take much longer time because values are stored linearly in memory and with second way you should jump 1 pointer n times
Can someone explain how we equalise n! ~ n^n in Back Subtitution Method (Video part 1 22:54)?
n! (= 1*2*3*…*n) is a product of n numbers each less than or equal to n. Therefore it is less than the product of n numbers all equal to n; i.e., n^n.
In graph mathematics, n^n grows faster than n!. In asymptotical notation, n! <= n^n ( you can check it via putting any number or drawing graph). So we can conclude that n! can not grow faster than O(n^n). For more mathematician prove you can check Stirling's approximation: https://en.wikipedia.org/wiki/Stirling%27s_approximation
Good afternoon professor. I have a question. Can you please describe little bit more about what is the difference between preconditions and postconditions in ADT specification
precondition first you check condition then you do operation , postcondition after operation you check the result
In Abstract Data Type, Operation Specifications such as Postconditions, Preconditions and Calling Prototype describe how operations behave.
-In Preconditions, statements are TRUE once operation called.
-In Postconditions, statements are TRUE when operation returns.
Whereas both of them could be used to specify the meaning of a function.
(Examples could be witnessed in operations of ADT- > as in “Constructors” and “Access Functions”).
Additionally, following characterizations can be made to them:
-For Preconditions
1)The precondition is a prerequisite for the activation
2)A precondition states if it makes sense to call an operation
-For Postconditions
1)The postcondition defines the meaning of the operation
2)A postcondition states if the operation returns the desired result, or has the desired effect, relative to the given parameters that satisfy the precondition
What is the average case for insertion algorithm?
Why you need it? I haven’t seen its been used. In every program you must be more concerned about worst case and, sometimes, in best case.
Averege case in insertion algorithm is О(n^2)
The same O(n^2) as the worst case
What exact suggestions might be made about the proper difference and relation between Queue and Priority Queue?
Can you explain Abstract Data Type and give some example?
Abstract Data Type – the type that defined methods by the user. For example, Stack ADT. It contains push(), pop(), size() and other methods. It is ADT. To implement it, the user uses different programming language features such as arrays, pointers, and others. After that, it becomes a data structure.