.png)
Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
What is an algorithm and what are the properties of an algorithm?
What are the steps that need to follow while designing an algorithm ?
What are the parameters that help in deciding the best possible algorithm for a problem ?
Explain with example the concept of linear space complexity?
Explain the difference between Big o, Small o notations with example.
According to you which is more important Time complexity or Space complexity? Justify.
Consider f(n)=100n+6, g(n)=n^2 . Is f(n)=O(g(n)) and also find c and n.
What is Recurrence Relation? Discuss four methods for solving Recurrence.
What is Substitution Method for solving recurrence relation?
What is Recursion Tree Method for solving recurrence relation?
Algorithm Basics
Question-1) What is the difference between Algorithm and Pseudo code?
Answer:
Algorithm | Pseudo code |
|
|
|
|
|
|
Question- 2) What is an algorithm and what are the properties of an algorithm?
Answer: An algorithm refers to a computable set of steps commonly used in mathematics, computing, linguistic and related disciplines to carry out certain calculations or data processing. It is an effective method which uses a list of well-defined instructions to complete a task, starting from a given initial state to achieve the desired end state.
There are five key properties for an algorithm to be called as an algorithm which are as follows :
Input: Input can be any data considered for processing in an algorithm on which operations are being performed which are basically considered from an external file.
Output: Output is the result data of an algorithm. It is the quantity produced at the conclusion of an algorithm.
Definiteness: It is the property which tells about the unambiguousness of an instruction in the given algorithm. Each instruction (line of code) must be as clear as possible.
Finiteness: An algorithm must be terminate after a finite number of steps, i.e., after number of set of instructions.
Effectiveness: It is the property which deals about how successful an algorithm in making the user to understand, i.e., tells about the level of user-friendly nature.
Question- 3) What are the steps that need to follow while designing an algorithm ?
Answer: Steps required while designing an algorithm:
Obtain the description of the problem statement for which the algorithm is meant to be designed.
Analyze the given problem statement.
Develop the algorithm.
Refine and review the algorithm until it is considered to be the best one.
Question- 4) What are the parameters that help in deciding the best possible algorithm for a problem ?
Answer: The criteria for judging algorithms that have a more direct relationship to perform are computing the time and storage requirements. Also called as Performance Analysis which helps one to judge the effectiveness of an algorithm.
Performance Analysis considers two most important criteria as parameters in judging, namely:
Time Complexity: Time taken by a program is nothing but the collective time at both run-time and compile-time.
Space Complexity: Space complexity of an algorithm is the amount of memory required to complete the execution given piece of code, i.e., program.
Question- 5) What do you understand by constant time complexity ?
Answer: A given algorithm is said to be taking constant time complexity if and only if the algorithms takes the same amount of time irrespective of the input data.
Example-1:
Searching an element in a hash table.
Example-2:
Printing the first element of a given array
Explanation: Here, irrespective of length and type of array, it takes constant time to print the very first element.
Question- 6) Explain with example the concept of linear space complexity?
Answer: The instance where the space quantity required by an algorithm is proportional to the amount of the input data, i.e., the space consumed by an algorithm increases as the data of input increases, is said to be linear space complexity.
Example:
An array of elements.
Explanation: Here, the space consumed by the algorithm depends upon the number of elements, i.e., more the number of elements in the input array, greater the space consumed by the algorithm.
Question- 7) What do you understand by order of growth?
Answer:
Order of growth is the set of functions which best describes the complexity of an algorithm (both space and time), in an asymptotic notation.
These are nine set of functions, in total.
The priority is given either on top-down or left-right order.
Higher priority is given to the topmost or left-most function and the priority decreases as one move towards down/left the chart.
Following is the left-right chart of order of growth:
Name | Constant | Logarithmic | Square Root | Linear | Multiple Logarithmic | Quadratic | Cubic | Exponential | Factorial |
Function | 1 | Log(n) | n^(1/2) | n | N*Log(n) | n^2 | n^3 | 2^n | n! |
An algorithm is said to be optimal if it is taking constant function for both time and space complexities.
Question- 8) Explain lower bound and upper bound of an algorithm?
Answer: As the terms suggest, lower & upper bound refers to lower and upper boundary.
For an algorithm, Big Omega asymptotic function is considered to be the lower bound and Big Oh function is considered to be the upper bound.
Question- 9) Explain the difference between Big o, Small o notations with example.
Answer: Big Oh notation as well as small o notations varies in terms of exactness / displacement towards the upper bound.
Here, small o notation is not tight to the upper bound where as the Big o notation gives an upper bound with relation of a constant factor.
Example:
Finding the sum of elements in a given array.
Here, small O notation can be considered to be o(n) for the time complexity as it takes time to process n elements and some miscellaneous time to carry out the algorithm, where as Big o notation can be considered as O(n)+c, where c is some constant time that can be considered for that missed out extra time other than the time taken to process n elements of the array .
Question- 10) Differentiate Big-omega and little-omega.
Answer: Omega is considered to be the best case of a function.
Little omega and Big omega do keenly differ in terms of precision, i.e., little omega is considered to be a rough estimate of the mentioned order of growth, where as the Big-omega represents the exact order of growth.
Question- 11) According to you which is more important Time complexity or Space complexity? Justify.
Answer: In my opinion, time complexity is more important than space complexity.
We are currently living in such a technology generation where memory/space is a resource which is available in abundance. In this view, I prefer time complexity over space complexity.
Question- 12) Consider f(n)=100n+6, g(n)=n^2 . Is f(n)=O(g(n)) and also find c and n.
Answer:
Above image is the solution for the given question.
Question- 13) What is asymptotic behavior?
Answer: Asymptotic behavior, best describes about either a function or expression.
It is a bounded behavior where the function reaches almost the limit but never touches the limit, i.e., boundary.
Question- 14) Discuss various Asymptotic Notations.
Answer: Various Asymptotic notations are:
Oh(O) notation – Big Oh, small Oh
Omega notation – Big omega, little omega
Theta notation
Question- 15) What is Recurrence Relation? Discuss four methods for solving Recurrence.
Answer: The relation of an algorithm where it calls itself for a set of conditions is called to be a recursive relation.
The four key methods of solving a recursive relation are :
Iteration method
Substitution method
Recursive Tree method
Master’s method.
Question- 16) What is Substitution Method for solving recurrence relation?
Answer: This is one of the methods to solve a recurrence relation which works on the trial and error analysis type approach.
Steps followed:
Guess the solution
Use the induction method to check the correctness of the hypothesis.
Question- 17) What is Iteration Method for solving recurrence relation?
Answer: Steps involved in solving a recursive relation using iteration method:
Find an explicit equation for the given expression/function.
Bound the recurrence of the expression that involves n.
In this method, the expression is iteratively broke down and is carried out for k – steps and then solved with the obtained generalized equation.
Question- 18) What is Recursion Tree Method for solving recurrence relation?
Answer: This is considered to be one of the most efficient approaches in the recursive relations. This works on the divide and conquers mechanism.
Here, the entire complexity is divided into sub-portions of simple quantities and then collectively calculated for the entire given quantity.
Question- 19) What is Master Method for solving recurrence relation?
Answer: This method of approach is basically adapted for solving the recurrence relations of the form:
T(n)=a*T(n/b)+f(n), for a>=1,b>1,f(n)>0
There is determined the complexity of the function depending upon three broadly classified cases where the case decides whether the function falls under Big Oh function, Theta function or Omega function.
Comments