Algorithms Notes

mobiprep (6).png

Algorithm Basics

mobiprep (6).png

Divide And Conquer

mobiprep (6).png

Greedy Algorithm

mobiprep (6).png

Dynamic Programming

mobiprep (6).png

Shortest Path

mobiprep (6).png

Backtracking

mobiprep (6).png

Minimum Spanning Tree

mobiprep (6).png

Maximum Flow

mobiprep (6).png

Complexity Classes

Heading

Q

1

What is the difference between Algorithm and Pseudo code ?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Algorithm:
Is a finite set of instructions that if followed accomplishes a particular task.
One needs basic programming knowledge to understand an algorithm.
Meant to be the blueprint of a code/program.

Pseudo code:
Is an English-like statement that follows a loosely defined syntax and are used to convey the design of an algorithm.
One doesn’t need any knowledge in programming to understand a given pseudo code.
Can be called to be blueprint of an algorithm.

LRM_EXPORT_207556595493866_20190724_1939

Q

2

What is an algorithm and what are the properties of an algorithm?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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 :
1) 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.
2) Output:
Output is the result data of an algorithm.
It is the quantity produced at the conclusion of an algorithm.
3) 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.
4) Finiteness:
An algorithm must be terminate after a finite number of steps, i.e., after number of set of instructions.
5) 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.

LRM_EXPORT_207556595493866_20190724_1939

Q

3

What are the steps that need to follow while designing an algorithm ?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Steps required while designing an algorithm:
1. Obtain the description of the problem statement for which the algorithm is meant to be designed.
2.Analyze the given problem statement.
3.Develop the algorithm.
4.Refine and review the algorithm until it is considered to be the best one.

LRM_EXPORT_207556595493866_20190724_1939

Q

4

What are the parameters that help in deciding the best possible algorithm for a problem ?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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:
1) Time Complexity:
Time taken by a program is nothing but the collective time at both run-time and compile-time.
2) Space Complexity:
Space complexity of an algorithm is the amount of memory required to complete the execution given piece of code, i.e., program.

LRM_EXPORT_207556595493866_20190724_1939

Q

5

What do you understand by constant time complexity ?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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.

LRM_EXPORT_207556595493866_20190724_1939

Q

6

Explain with example the concept of linear space complexity?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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.

LRM_EXPORT_207556595493866_20190724_1939

Q

7

What do you understand by order of growth?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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.
An algorithm is said to be optimal if it is taking constant function for both time and space complexities.
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!

LRM_EXPORT_207556595493866_20190724_1939

Q

8

Explain lower bound and upper bound of an algorithm?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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.

LRM_EXPORT_207556595493866_20190724_1939

Q

9

Explain the difference between Big o, Small o notations with example.

LRM_EXPORT_207556595493866_20190724_1939

Ans

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 .

LRM_EXPORT_207556595493866_20190724_1939

Q

10

Differentiate Big-omega and little-omega.

LRM_EXPORT_207556595493866_20190724_1939

Ans

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.

LRM_EXPORT_207556595493866_20190724_1939