Analysis of Algorithm notes prepared by vit.pptx

basic notes and introduction for analysis of algorithm

1. Prepared By: Prof. Swapnil S. Sonawane Subject: Analysis of Algorithms Prof. Swapnil s. Sonawane (SSO)

2. Chapter #1: Introduction Prepared By: Prof. Swapnil S. Sonawane

3. Complexity: Algorithms can be compared or analyzed using two types of complexities: 1. Space Complexity: It is the space required for execution of algorithm excluding the space taken by inputs 2. Time Complexity: It is the time required for execution of algorithm excluding the time required for accepting the inputs Prepared By: Prof. Swapnil S. Sonawane

4. Write an algorithm for swapping two integer numbers Also find its time complexity Write an algorithm to check whether a number is even or odd and find its time complexity Find time complexity of following codes: Prepared By: Prof. Swapnil S. Sonawane

5. Types of Time Function: O(1) Constant O(log n) Logarithmic O(n) Linear O(n log n) Super Linear O(n^2) Quadratic O(n^3) Cubic O(2^n) Exponential Prepared By: Prof. Swapnil S. Sonawane

6. Asymptotic Notation: It is the analysis performed for larger number of inputs 1. Big ‘O’ Notation (Upper Bound): The function f(n)=O(g(n)) if and only if there exist positive constant c and n0, such that, f(n)<=c*g(n) for all n>=n0 Prepared By: Prof. Swapnil S. Sonawane

7. 2. Omega Notation ( Ω ) (Lower Bound): The function f(n)= Ω (g(n)) if and only if there exist positive constant c and n0, such that, f(n)>=c*g(n) for all n>=n0 Prepared By: Prof. Swapnil S. Sonawane

8. 3. Theta Notation ( θ ) (Average Bound): The function f(n)= θ (g(n)) if and only if there exist positive constant c and n0, such that, c1*g(n)<=f(n)<=c2*g(n) for all n>=n0 Prepared By: Prof. Swapnil S. Sonawane

9. Minimum Spanning Tree Algorithms: Kruskal’s Algorithm: Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. Kruskal's algorithm follows greedy approach which finds an optimum solution at every stage. Algorithm: Remove all loops and Parallel Edges Arrange all edges in their increasing order of weight Add the edge which has the least weightage but ignore/reject those edges that create a cycle or closed loop Add cost of every edge of spanning tree to get total cost Prepared By: Prof. Swapnil S. Sonawane

10. Prim’s Algorithm: Prim's algorithm to find minimum cost spanning tree uses the greedy approach. Prim's algorithm, treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph. Algorithm: Select starting vertex and consider all its directly connected edges Select edge with minimum weight Add the selected edge in spanning tree Select vertex of added edge and repeat step 1 until all vertex has been selected Prepared By: Prof. Swapnil S. Sonawane

11. Shortest Path Algorithm : Dijkstra’s Algorithm: It is a greedy algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights It is an algorithm that is used for finding the shortest distance, or path, from starting node to target node in a weighted graph Algorithm: 1. Begin from the node to be selected, the source node, and it examines the entire graph to determine the shortest path among that node and all the other nodes connected to source node Prepared By: Prof. Swapnil S. Sonawane

12. 2. Maintain the track of the currently recognized shortest distance from each node to the source code and updates these values if it identifies another shortest path. 3. Once the shortest path from the source code to another node is determined, the node is marked as “visited” and can be added to the path. 4. This process is being continued till all the nodes in the graph have been added to the path. Prepared By: Prof. Swapnil S. Sonawane

13. Fractional Knapsack Problem : The fractional knapsack problem is also one of the techniques which are used to solve the knapsack problem. In fractional knapsack, the items are broken in order to maximize the profit. The problem in which we break the item is known as a Fractional knapsack problem. This problem can be solved with the help of using two techniques: Brute-force approach: The brute-force approach tries all the possible solutions with all the different fractions, but it is a time-consuming approach. Greedy approach: In Greedy approach, we calculate the ratio of profit/weight, and accordingly, we will select the item. The item with the highest ratio would be selected first. Prepared By: Prof. Swapnil S. Sonawane

14. Job Sequencing with Deadlines: We adopt a greedy algorithm to determine how the next job is selected for an optimal solution. The greedy algorithm described below always gives an optimal solution to the job sequencing problem. Sort all the given jobs in the decreasing order of their profits. Check the value of maximum deadline. Then, draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline. Pick up the jobs one by one and then put them on the Gantt chart as far as possible from 0 (starting point) such that the job gets completed before its deadline. Prepared By: Prof. Swapnil S. Sonawane

15. Greedy Method Dynamic Programming In a greedy Algorithm, we make whatever choice seems best at the moment in the hope that it will lead to optimal solution. In Dynamic Programming we make decision at each step considering current problem and solution to previously solved sub problem to calculate optimal solution . In Greedy Method, sometimes there is no such guarantee of getting Optimal Solution. It is guaranteed that Dynamic Programming will generate an optimal solution  It is more efficient in terms of memory as it never look back or revise previous choices It requires table for memorization, and it increases its memory complexity. Greedy methods are generally faster.  Dynamic Programming is generally slower. It do not use memorization and tabulation It uses memorization and tabulation concepts Example: Fractional knapsack Example: 0/1 knapsack problem Prepared By: Prof. Swapnil S. Sonawane

16. Prepared By: Prof. Swapnil S. Sonawane Multistage Graph: A multistage graph is directed graph, in which the nodes can be divided into different stages, such that all edges are connected from one stage to next stage only We need to find cost of every vertex with respect to its stage number using following formula: cost ( i , j )=min { c ( j , k ) + cost ( i+1, k ) } Final decision about shortest path and its cost can be taken using “Forward Method” approach

17. Floyd- Warshall Algorithm : Floyd- Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. Algorithm: n = no of vertices A = matrix of dimension n*n for k = 1 to n for i = 1 to n for j = 1 to n Ak[ i , j] = min (Ak-1[ i , j], Ak-1[ i , k] + Ak-1[k, j]) return A Complexity: O(n 3 ) Prepared By: Prof. Swapnil S. Sonawane

18. N Queens Problem: The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution and if we do not find such a row due to clashes, then we backtrack and return false. Prepared By: Prof. Swapnil S. Sonawane

19. Algorithm: 1) Start in the leftmost column 2) If all queens are placed, return true 3) Try all rows in the current column. a) If the queen can be placed safely in this row, then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in [row, column] leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows. 4) If all rows have been tried and nothing worked return false to trigger backtracking. Prepared By: Prof. Swapnil S. Sonawane

20. Graph Coloring Problem : The idea is to assign colors one by one to different vertices, starting from the vertex 0. Before assigning a color, check for safety by considering already assigned colors to the adjacent vertices i.e check if the adjacent vertices have the same color or not. If there is any color assignment that does not violate the conditions, mark the color assignment as part of the solution. If no assignment of color is possible then backtrack and return false. Prepared By: Prof. Swapnil S. Sonawane

21. Algorithm: Create a recursive function that takes the graph, current index, number of vertices, and output color array. If the current index is equal to the number of vertices. Print the color configuration in output array. Assign a color to a vertex (1 to m). For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices do not have the same color) recursively call the function with next index and number of vertices If any recursive function returns true break the loop and return true. If no recursive function returns true then return false. Prepared By: Prof. Swapnil S. Sonawane

22. Sum of Subset Problem : In this, we have weight vector of ‘n’ integers stored in ascending order We required sum of all subset as ‘m’ (Exact sum) The problem is to find all the subsets of given weight vector, where sum=m Prepared By: Prof. Swapnil S. Sonawane

23. Prepared By: Prof. Swapnil S. Sonawane Algorithm of “Sum of subsets”: Start with an empty set Add the next element from weight vector to the set If the subset is having sum M, then stop with that subset as solution. If the subset is not feasible or if we have reached the end of the set, then backtrack through the subset until we find the most suitable value. If the subset is feasible (sum of subbset < M) then go to step 2. If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without solution.

24. Prepared By: Prof. Swapnil S. Sonawane Branch and Bound: This is quite similar to backtracking as it also creates State-Space tree, but it is used to solve optimization problem In this we calculate bound of each node which represents the cost of reaching to solution node from that node If the solution represented by bound, is worse than best solution found so far, then that node is killed, and corresponding branch is closed The bound can also be used to select most promising node out of available E-node: It is a node which is currently getting expanded Live node: It is a node which is created but not expanded yet

25. Prepared By: Prof. Swapnil S. Sonawane In B&B at each E node, we find all the live nodes which can be generated using a single step Those which are infeasible are killed and others are added to list of live node Depending on policy of selecting next E node, B&B can be categorized as follows: LIFO BB/ LIFO Search: In this always the youngest node in the queue is used to extend the branch. This leads to a depth-first search FIFO BB/ FIFO Search: In this always the oldest node in the queue is used to extend the branch. This leads to a breadth-first search LC BB/ LC Search: In this the next E node selected will be live node with least cost. It uses estimated cost function ‘C^’ instead of actual cost function ‘C’

26. Prepared By: Prof. Swapnil S. Sonawane 15 Puzzle Problem: In this, we have a square block frame of 4X4 dimensions with 15 numbered tiles and an empty slot The problem is to reach goal state from initial state

27. Prepared By: Prof. Swapnil S. Sonawane There are maximum 4 legal moves, possibly as UP, DOWN, LEFT and RIGHT Hence, we need to find set of legal moves to transform initial state to goal state The estimated cost function can be calculated as, C^(x)= f(x) + g^(x) Here, f(x)=Depth of node x g^(x)=Number of nonblank tiles which are not in their goal state

28. Prepared By: Prof. Swapnil S. Sonawane Travelling Salesperson Problem using B&B: A better estimated cost function can be found using reduced cost function A row of a matrix is said to be reduced if it contains at least 1 zero and all remaining elements are non negative and similarly columns can also be reduced A matrix is said to be reduced if all rows and columns are reduced The following steps are used to find cost (C) of a node representing an edge from i to j:

29. Prepared By: Prof. Swapnil S. Sonawane Set all elements of row i and column j of matrix to ∞ Set A( j,1) to ∞ Reduce all rows and columns of the resultant matrix except the rows and columns containing ∞ Compute the total reduction value as, C^(S)=C^(R) + A( i , j) + r Where, S=Current node representing an edge from i to j R=Previous node A( i , j)=Cost of edge ( i , j) r=Reduction value

30. Prepared By: Prof. Swapnil S. Sonawane Brute force (Naïve) pattern matching: Naive pattern searching is the simplest method among other pattern searching algorithms. It checks for all character of the main string to the pattern. Naive algorithm is exact string matching(means finding one or all exact occurrences of a pattern in a text) algorithm. This algorithm is helpful for smaller texts. It does not need any pre-processing phases. We can find substring by checking once for the string. It also does not occupy extra space to perform the operation. The naive approach tests all the possible placement of Pattern P [1…….m] relative to text T [1……n]. We try shift s = 0, 1…….n-m, successively and for each shift s. Compare T [s+1……. s+m ] to P [1……m].It returns all the valid shifts found. The time complexity is O(n-m+1)

31. Prepared By: Prof. Swapnil S. Sonawane Knuth-Morris-Pratt Algorithm: KMP is an algorithm for string matching problem It is used to avoid comparison of element that have previously been involved in comparison with some elements of the pattern to be matched to avoid repetitive backtracking It has 2 components: a. The prefix function ( π ): It is used to encapsulate knowledge about how the pattern matches against shift of itself b. The KMP matcher: With text ‘T’, pattern ‘P’ and prefix function ‘ π ’ as inputs, it finds the occurrence of ‘P’ in ‘T’ and returns the number of shifts of ‘P’ after which occurrence are found

32. Prepared By: Prof. Swapnil S. Sonawane Rabin Carp Algorithm: The Rabin-Karp string matching algorithm calculates a hash value for the pattern, as well as for each M-character subsequences of text to be compared. If the hash values are unequal, the algorithm will determine the hash value for next M-character sequence. If the hash values are equal, the algorithm will analyze the pattern and the M-character sequence. In this way, there is only one comparison per text subsequence, and character matching is only required when the hash values match.