Design and Analysis of Algorithm for II year Computer science and Engineering students

This PPT is useful to learn Design and Analysis of Algorithm

1. Design and Analysis of Algorithms

2. UNIT I INTRODUCTION Notion of an Algorithm What is an algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.

3. Properties of Algorithm Finiteness terminates after a finite number of steps Definiteness rigorously and unambiguously specified Clearly specified input valid inputs are clearly specified Clearly specified/expected output can be proved to produce the correct output given a valid input Effectiveness steps are sufficiently simple and basic 6. Multiplicity The same algm can be represented in several diff.ways . 7. Speed Algms for the same problem can be based on very different ideas and can solve the problem with diff.speeds .

4. Algorithm and Program Step by step procedure for solving a computational problem. Independent dependent

5. Methods for solving the same problem Euclid’s Algorithm for computing greatest common divisor GCD( m,n ) Euclid’s algorithm is based on repeated application of equality gcd ( m,n ) = gcd ( n, m mod n ) until the second number becomes 0, which makes the problem trivial. Example: gcd (60,24) = gcd (24,12) = gcd (12,0) = 12 Two descriptions of Euclid’s algorithm 1.Structured description Step 1 If n = 0, return m and stop; otherwise go to Step 2 Step 2 Divide m by n and assign the value of the remainder to r Step 3 Assign the value of n to m and the value of r to n. Go to Step 1. 2.Pseudocode while n ≠ 0 do r ← m mod n m← n n ← r return m

6. Euclid’s algorithm Euclid( m,n ){ While m does not divide n r= nmodm n=m m=r end return m Eg.m =36, n=48 36 divides 48 -  no r=48mod36=12 n=36,m=12 12 divides 36  return 12

7. Other methods for gcd ( m,n ) [cont.] Middle-school procedure Step 1 Find the prime factorization of m Step 2 Find the prime factorization of n Step 3 Find all the common prime factors Step 4 Compute the product of all the common prime factors and return it as gcd ( m,n ) Eg . m=36 n=48 find gcd ( m,n ) m= 2*2 *3* 3 n= 2*2 *2*2* 3 Common factors are 2,2,3. Gcd =2*2*3=12

8. Other methods for computing gcd ( m,n ) Consecutive integer checking algorithm Step 1 Assign the value of min{ m,n } to t Step 2 Divide m by t. If the remainder is 0, go to Step 3; otherwise, go to Step 4 Step 3 Divide n by t. If the remainder is 0, return t and stop; otherwise, go to Step 4 Step 4 Decrease t by 1 and go to Step 2 T=min( m,n ) T divides both m and n return t T doesnotdecrease t by 1

9. Fundamentals of Algorithmic Problem Solving discuss a sequence of steps while designing and analyzing an algorithm. Understanding the Problem Decision making on Ascertaining the Capabilities of the Computational Device Choosing between Exact and Approximate Problem Solving Algorithm Design Techniques Designing an Algorithm and Data Structures Methods of Specifying an Algorithm Proving an Algorithm’s Correctness Analyzing an Algorithm Coding an Algorithm

10. Fundamentals of Algorithmic Problem Solving (Contd..) Understanding the Problem understand the problem completely before designing the algm . Read the problem’s description carefully and ask questions if you have any doubts about the problem. An input to an algorithm specifies an instance of the problem the algorithm . to specify exactly the set of instances the algorithm needs to handle. If you fail to do this, your algorithm may work correctly for a majority of inputs but crash on some “boundary” value. correct algorithm is not one that works most of the time, but one that works correctly for all legitimate inputs .

11. Fundamentals of Algorithmic Problem Solving (Contd..) Decision making on Once you completely understand a problem, we need to decide - the Capabilities of the Computational Devices - Choosing between Exact and Approximate Problem Solving - Algorithm Design Techniques - Designing an Algorithm and Data Structures need to ascertain the capabilities of the computational device the algorithm is intended for. Classify an algorithm from the execution point of view. Instructions are executed one after another, one operation at a time. Algorithms designed to be executed on such machines are called sequential algorithms/RAM Instructions are executed in parallel, concurrent operation at a time.Algorithms designed to be executed on such machines are called parallel algorithms.

12. Fundamentals of Algorithmic Problem Solving (Cont..) Choosing between Exact and Approximate Problem Solving The next principal decision is to choose between solving the problem exactly (exact algorithm) or solving the problem approximately (approximation algorithm) . exact algorithm Eg . extracting square roots, solving nonlinear equations, and evaluating definite integrals. approximation algorithm Eg . Vertex Cover, Traveling Salesman Problem Algorithm Design Techniques An algorithm design technique (or “strategy” or “paradigm”) is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing. Eg . Brute force technique,Divide and conquer,Greedy technique,Dynamic Programming ,Backtracking

13. Fundamentals of Algorithmic Problem Solving (Cont..) Designing an Algorithm and Data Structures Data structure and algorithm work together and they are interdependent. Hence choice of proper data structure is required before designing the algorithm. Implementation of program=data structure + algorithm. Various ways to specify an algorithm Natural language- is not clear. Pseudocode - is a mixture of a natural language and programming language constructs. Pseudo code is usually more precise than natural language. Flow chart - a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps.

14. Fundamentals of Algorithmic Problem Solving (Cont..) Proving an Algorithm’s Correctness/verification Once an algorithm has been specified, you have to prove its correctness . i.e you have to prove that the algorithm yields a required result for every legitimate input in a finite amount of time . A common technique for proving correctness is to use mathematical induction because an algorithm’s iterations provide a natural sequence of steps needed for such proofs . Analyzing an Algorithm two kinds of analyzing the algorithm efficiency: time efficiency- indicating how fast the algorithm runs space efficiency -indicating how much extra memory it uses. Another desirable characteristic of an algorithm is simplicity - generating sequence of instrns are easy to understand Generality - generality of the problem the algorithm solves and the set of inputs it accepts. Sometimes more easier to design the algorithm. Range of inputs These factors are not satisfactory then redesign the algorithm.

15. Fundamentals of Algorithmic Problem Solving (Cont..) Coding an Algorithm/implementation Implementation of algorithm is done by suitable programming languages. Optimality -writing the program code is optimal. This will reduce the burden of the compiler Important problem types Computing problems can be classified as Sorting Searching Numerical Geometric Combinatorial Graph String processing

16. Sorting Rearrange the items of a given list in increasing and decreasing order. Eg . sort list of nos .,characters from alphabets, character strings, etc.. We need to choose a piece of information to guide sorting. Such kind of piece of information is called key. Why we want sorting? Makes the list easier to answer. Useful in searching( eg . telephone books,dictionary ) Good sorting algm that sort an arbitrary array of size n using about nlog2n comparision .

17. Properties of sorting All algms can be analyzed by 2 important properties. 1) stable -it preserves the relative ordering of items with equal values. GPA NAME 9.2 Anu 9.3 (equal elmts ) Shenba (unsorted list) 9.3(equal elmts ) Mahesh (unsorted list) 9.3 (equal elmts ) Arathana (unsorted list) 9.4 tamil GPA NAME 9.2 Anu 9.3(equal elmts ) Arathana 9.3(equal elmts ) Mahesh 9.3(equal elmts ) Shenba 9.4 tamil

18. Properties of sorting In place property- does not require extra memory while sorting the list. Not In place property- require extra memory while sorting the list. Searching Find out the desired element from the list. Searching search-search key How to choose best searching algm ? Some algms work faster, they require more memory Some algms works better if the list is almost sorted. Thus efficiency of algm is varying at varying situations. Numerical pblms Mathematical equations, systems of equations, computing definite integrals, evaluating functions… These pblms are solved by approximate algms . Geometric pblms It deals with geometric objects such as points, lines & polygons. Used in computer graphics, robotics etc.. Eg . closest pair, convex hull.

19. Combinatorial pblms Pblms like permutations and combinations. Lot of possible solutions. find the optimal solution from possible solution Problem size become big, the complexity will become high. Eg.graph coloring pblm , tsp Graph problems Collection of vertices and edges. Shortest path, graph traversals,tsp String processing pblms Collection of characters Called pattern matching algm . Particular word is searching from the text

20. Fundamentals of the Analysis of Algorithm Efficiency/ Analysis Framework Measure the performance of an algorithm by computing 2 factors. Space complexity Time complexity Measuring an input size Measuring running time Order of growth

21. Space complexity Space complexity of an algorithm means the amount of space (memory) taken by an algorithm. By computing space complexity, we can analyze whether an algorithm requires more or less space. Memory space S(P) needed by a program P, consists of two components: A fixed part: needed for instruction space (byte code), simple variable space, constants space etc.  c A variable part: dependent on a particular instance of input and output data.  S p (instance) S(P ) = c + S p (instance ) Algorithm add (a, b, c) { return a+b+c ; } For every instance 3 computer words required to store variables: a, b, and c (assume a,b,c occupy one word size). Therefore S(P) = 3.

22. Space complexity Algorithm Sum(a[], n) { s:= 0.0; for i = 1 to n do s := s + a[i]; return s; } Every instance needs to store array a[] & n. Space needed to store n = 1 word. Space needed to store a[ ] = n floating point words (or at least n words) Space needed to store i and s = 2 words Hence S(P) = (n + 3 ).( i.e 1+n+2=n+3)

23. Time complexity Time complexity of an algorithm means the amount of time taken by an algorithm. By computing time complexity, we can analyze whether an algorithm requires fast or slow speed. Difficult to compute physically clocked time.so executing time depends on many factors such as System load No. of other programs running time Instruction set Speed of hardware The time complexity is given in terms of frequency count. Frequency count is a count denoting number of times of execution of statement.

24. Time complexity

25. Time complexity Matrix addition For(i=0;i< n;i ++) { For(j=0;j< n;j ++) { C[i][j]=a[i][j]+b[i][j] } Frequency count(FC) can be computed as follows For( i =0;i< n;i ++) i =0 executes once . Fc =1 i <n executes for n+1 times i ++ executes for n times For(j=0;j< n;j ++) j=0 executes n*1=n times j<n executes n*(n+1) times= n 2 +n times j++ executes n*n= n 2 times C[ i ][j]=a[ i ][j]+b[ i ][j] executes n*n= n 2 times Totally 3n 2 +4n+2

26. Measuring an input size If the i/p size is longer, then usually algm runs for a longer time. Hence we can compute the efficiency of an algm as a function to which i/p size is passed as a parameter. Eg . multiply of 2*2 matrix-should know order of these matrices then only we can enter the elmts of matrices. Measuring running time Time complexity is measured in terms of FC. we first identify logic operation of an algm  basic operation (more time consuming, such basic operation is located in inner loop) T (n) ≈ cop.C (n) Cop  execution time of an algorithm’s basic operation on a particular computer C(n)  number of times this operation needs to be executed for this algorithm. T(n)  running time of the algorithm

27. Measuring running time Eg . sorting comparing the elements and then placing them in the correct locations is a basic operation. Eg . PROBLEM INPUT SIZE BASIC OPERATION Searching element from list of n elements List of n elements Comparison of key with every element of list Matrix multiplication Two matrices with order n * n Actual multiplication of the elements in the matrices Gcd of 2 numbers 2 numbers Division

28. Order of growth Measuring the performance of an algorithm in relation with the input size n is called order of growth. For example, the order of growth for varying input size of n is as given below.

29. Worst-Case, Best-Case, and Average-Case Efficiencies Worst Case Time Complexity: when there are no matching elements or the first matching element happens to be the last one on the list. Algorithm makes the largest number of key comparisons among all possible inputs of size. C worst (n ) = n. Algorithm runs the longest among all possible inputs of that size. Time complexity for linear search in worst case=O(n) Best case time complexity Algorithm runs the fastest among all possible inputs of that size. For example, the best-case inputs for sequential search are lists of size n with their first element equal to a search key C best (n) = 1 Time complexity for linear search in best case=O(1)

30. Average Case time complexity This type of complexity gives information about the behavior of an algorithm on specific random input. Let p->probability of getting successful search Let n->total no.of elements in the list The first match of the element will occur at ith location.Hence probability of occuring first match is p/n for every ith element. The probability of getting unsuccessful search is (1-p). C avg (n) = probability of getting successful search(for elements 1 to n in the list) + probability of getting unsuccessful search. C avg (n) =n+1/2 there may be n elements at which chances of not getting element are possible. Hence n.(1-p). Time complexity for linear search in average case=O(n)

31. Amortized analysis Amortized analysis  is a method for analyzing a given algorithm's time complexity, or how much of a resource, especially time or memory in the context of computer programs, it takes to execute.

32. Fundamentals of the Analysis of Algorithm Efficiency (Cont..) The properties of order of growth : If F 1 (n) is order of g 1 (n) and F 2 (n) is order of g 2 (n), then F 1 (n) +F 2 (n) Polynomials of degree m .That means maximum degree is considered from the polynomial.

33. Asymptotic Notations and its Properties the efficiency analysis framework concentrates the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth, computer scientists use three notations: O (big oh), (big omega), and (big theta). t (n) and g(n) can be any nonnegative functions defined on the set of natural numbers. t (n) will be an algorithm’s running time (usually indicated by its basic operation count C(n)), and g(n) will be some simple function to compare the count with. To choose the best algorithm, we need to check efficiency of each algorithm. The efficiency can be measured by computing time complexity of each algorithm. Asymptotic notation is a shorthand way to represent the time complexity . Using asymptotic notations we can give time complexity as “fastest possible”, “slowest possible” or “average time”.

34. Asymptotic Notations and its Properties (Cont..) The big Oh notation is denoted by O .It is a method of representing the upper bound of algorithms running time. Using big oh notation we can give longest amount of time taken by the algorithm to compute. DEFINITION A function t (n) is said to be in O(g(n)), denoted t (n) ∈ O(g(n)), if t (n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0 such that t (n) ≤ cg(n) for all n ≥ n0.

35. Asymptotic Notations and its Properties (Cont..) Omega notation is denoted by ‘ Ω ’. This notation is used to represent the lower bound of algorithms running time. Using omega notation we can denote shortest amount of time taken by algorithm. DEFINITION A function t (n) is said to be in (g(n)), denoted t (n) ∈ (g(n)), if t (n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0 such that t (n) ≥ cg(n) for all n ≥ n0.

36. Asymptotic Notations and its Properties (Cont..) The theta notation is denoted by .By this method the running time is between upper bound and lower bound. DEFINITION A function t (n) is said to be in (g(n)), denoted t (n) ∈ (g(n)), if t (n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constants c1 and c2 and some nonnegative integer n0 such that c2g(n) ≤ t (n) ≤ c1g(n) for all n ≥ n0

37. Asymptotic Notations and its Properties (Cont..) Polynomials of degree m .That means maximum degree is considered from the polynomial. Eg.3n 2 +2n 2 +10 then its time complexity is O(n 3 ). Any constant value leads to O(1) time complexity. that is if f(n)=c then it ε O(1) time complexity.

38. Basic Efficiency Classes the time efficiencies of a large number of algorithms fall into only a few classes.

39. Basic Efficiency Classes

40. Mathematical Analysis for Recursive and Non-Recursive Algorithms

41. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) Methods for Solving Recurrence Equations: Substitution method Forward substitution Backward substitution Masters method Tree method The substitution method guess for the solution is made. There are two types of substitution: Forward substitution Backward substitution Forward substitution method: This method makes use of an initial condition in the initial term and value for the next term is generated. This process is continued until some formula is guessed. Backward substitution method: In this method values are substituted recursively in order to derive some formula.

42. Forward substitution T(n)=T(n-1)+n with initial condition T(0)=0 Let T(n)=T(n-1)+n If n=1 then T(1)=T(1-1)+1=T(0)+1=0+1=1 If n=2 then T(2)=T(2-1)+2=T(1)+2=1+2=3 If n=3 then T(3)=T(3-1)+3=T(2)+3=3+3=6 We can derive the formula T(n)=n(n+1)/2 =n 2 /2+n/2 = O(n 2 ) backward substitution T(n)=T(n-1)+n ---- 1 with initial condition T(0)=0 Let n=n-1,T(n-1)=T(n-1-1)+(n-1) T(n-1)=T(n-2)+(n-1) ---- 2 Sub eqn 2 in eqn 1 T(n)=T(n-2)+(n-1)+n - ----3 Let n=n-2,T(n-2)=(T(n-2-1)+(n-2) T(n-2)=T(n-3)+(n-2) --- -- 4 Sub eqn 4 in eqn 3 T(n)=T(n-3)+(n-2)+(n-1)+n . . . .

43. backward substitution T(n)=T(n-k)+(n-k+1)+(n-k+2)+….+n If k=n then T(n)=T(0)+1+2+…..n T(0)=0 T(n)=0+1+2+…..n We can derive the formula T(n)=n(n+1)/2 =n 2 /2+n/2 T(n)= O(n 2 )

44. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) Decide the input size based on parameter n. Identify algorithms basic operation. Check how many times the basic operation is executed. Set up the recurrence relation with some initial condition and expressing the basic operation. Solve the recurrence or atleast determine the order of growth. General Plan for Analysis Decide on parameter n indicating input size Identify algorithm’s basic operation Determine worst , average , and best cases for input of size n Set up a sum for the number of times the basic operation is executed Simplify the sum using standard formulas and rules

45. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) EXAMPLE 1 Consider the problem of finding the value of the largest element in a list of n numbers. For simplicity, we assume that the list is implemented as an array. The following is pseudocode of a standard algorithm for solving the problem. ALGORITHM MaxElement (A[0..n − 1]) //Determines the value of the largest element in a given array //Input: An array A[0..n − 1] of real numbers //Output: The value of the largest element in A maxval ←A[0] for i ←1 to n − 1 do if A[ i ]> maxval maxval←A [ i ] //if any value large//searching the maximum element from an arrayr than current_maxvalue then set new maxvalue by obtained larger value return maxval

46. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) measure of an input’s size here is the number of elements in the array, i.e., n. There are two operations in the loop’s body: the comparison A[ i ]> maxval and the assignment maxval←A [ i ]. Which of these two operations should we consider basic? Since the comparison is executed on each repetition of the loop and the assignment is not we should consider the comparison to be the algorithm’s basic operation. Note:The comparisons is made for each value of n there is no need to find worst, average, and best cases analysis here. C(n) the number of times this comparison is executed The algorithm makes one comparison on each execution of the loop, which is repeated for each value of the loop’s variable i within the bounds 1 and n − 1, inclusive.

47. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..)

48. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) EXAMPLE 2 Consider the element uniqueness problem: check whether all the elements in a given array of n elements are distinct. This problem can be solved by the following straightforward algorithm. ALGORITHM UniqueElements (A[0..n − 1]) //Determines whether all the elements in a given array are distinct //Input: An array A[0..n − 1] //Output: Returns “true” if all the elements in A are distinct // and “false” otherwise for i ←0 to n − 2 do for j ← i + 1 to n − 1 do if A[ i ]= A[j ] return false //if any two elmts in the array are similar then return false indicating that the array elmts are not distinct return true

49. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) input’s size : n, the number of elements in the array. basic operation: innermost loop contains a single operation (the comparison of two elements) the worst case input is an array for which the number of element comparisons Cworst (n) is the largest among all arrays of size n. there are two kinds of worst-case i / ps:they are arrays with no equal elements arrays in which the last two elements are the only pair of equal elements. For such inputs, one comparison is made for each repetition of the innermost loop, i.e., for each value of the loop variable j between its limits i + 1 and n − 1; this is repeated for each value of the outer loop, i.e., for each value of the loop variable i between its limits 0 and n − 2.

50. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..)

51. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) ALGORITHM MatrixMultiplication(A[0..n − 1, 0..n − 1], B[0..n − 1, 0..n − 1]) //Multiplies two square matrices of order n by the definition-based algorithm //Input: Two n × n matrices A and B //Output: Matrix C = AB for i ←0 to n − 1 do for j ←0 to n − 1 do C[ i , j ]←0.0 for k←0 to n − 1 do C[i, j ]←C[i, j ]+ A[i, k] ∗ B[k, j] return C

52. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) input’s size by matrix order n. multiplication as the basic operation set up a sum for the total number of multiplications M(n) executed by the algm . one multiplication executed on each repetition of the algorithm’s innermost loop, which is governed by the variable k ranging from the lower bound 0 to the upper bound n − 1. Therefore, the number of multiplications made for every pair of specific values of variables i and j is

53. Mathematical Analysis for Recursive and Non-Recursive Algorithms (Cont..) the total number of multiplications M(n) is expressed by the following triple sum : Time complexity= Θ ( n 3 )

54. Mathematical Analysis for Non-Recursive Algorithms (Cont..) EXAMPLE 4 The following algorithm finds the number of binary digits in the binary representation of a positive decimal integer. ALGORITHM Binary(n) //Input: A positive decimal integer n //Output: The number of binary digits in n’s binary representation count ←1 while n > 1 do count ←count + 1 n←floor (n/2) return count

55. Mathematical Analysis for Non-Recursive Algorithms (Cont..) While loop(execution) eg : n=5 Count=1 1) While(n>1){-------- 5>1 Count=count+1-- 1+1=2 n=floor(n/2)-5/2=2.5=2-n=2 count=2 2) While(n>1){-------- 2>1 Count=count+1-- 2+1=3 n=floor(n/2)-2/2= 1 count=3 3) While(n>1){-------- 1>1--false Analysis i /p size : n Basic operation : while loop value of n is about halved on each repetition of the loop. hence the efficiency is log 2 n. Floor( log 2 n) = Floor( log 2 5)= Floor( 2.5)  2 Floor( log 2 n) + 1 --------------- (since 1 for While(1>1)-------- for false condition) No.of times while loop executes is Floor( log 2 n) + 1 Time complexity= Θ ( log 2 n )

56. Mathematical Analysis of Recursive Algorithms General Plan for Analyzing the Time Efficiency of Recursive Algorithms 1. Decide on a parameter (or parameters) indicating an input’s size. 2. Identify the algorithm’s basic operation. Check whether the number of times the basic operation is executed can vary on different inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately. 4. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed. 5. Solve the recurrence or, at least, ascertain the order of growth of its solution.

57. Mathematical Analysis of Recursive Algorithms ALGORITHM F(n) //Computes n! recursively //Input: A nonnegative integer n //Output: The value of n! if n = 0 return 1 else return F(n − 1) ∗ n input size: n The basic operation of the algorithm is multiplication, whose number of executions we denote M(n). Since the function F(n) is computed according to the formula F(n) = F(n − 1) * n for n > 0 the number of multiplications M(n) needed to compute it must satisfy the equality M(n) = M(n − 1) + 1 for n > 0 M(n − 1)--  to compute F(n−1) +1-------  to multiply F(n−1) by n

58. Mathematical Analysis of Recursive Algorithms M(n − 1) multiplications are spent to compute F(n − 1). eg .n=5 5-1=4!0!*1*2*3*4--n-1 multiplications. one more multiplication is needed to multiply the result by n.( 0!*1*2*3*4) * 5 if n = 0 return 1. when n = 0, the algorithm performs no multiplications. Therefore, the initial condition M(0) =0. M(0) ---  the calls stop when n = 0 0---  no multiplications when n = 0 the recurrence relation and initial condition for the algorithm’s number of multiplications M(n) = M(n − 1) + 1 for n > 0, M(0) = 0. backward substitutions: M(n) = M(n − 1) + 1 (substitute M(n − 1) = M(n − 2) + 1) = [M(n − 2) + 1]+ 1= M(n − 2) + 2 (substitute M(n − 2) = M(n− 3) + 1) = [M(n − 3) + 1]+ 2 = M(n − 3) + 3. General formula for the pattern: M(n) = M(n − i ) + i . substitute i = n in the pattern’s formula to get the ultimate result of our backward substitutions: M(n) = M(n − 1) + 1= . . . = M(n − i) + i = . . . = M(n − n) + n = n .

59. Tower of Hanoi puzzle n disks of different sizes that can slide onto any of three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The goal is to move all the disks to the third peg, using the second one as an auxiliary, if necessary. We can move only one disk at a time, and it is forbidden to place a larger disk on top of a smaller one. To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary), we first move recursively n − 1 disks from peg 1 to peg 2 (with peg 3 as auxiliary), Then move the largest disk directly from peg 1 to peg 3, and, finally, move recursively n − 1 disks from peg 2 to peg 3 (using peg 1 as auxiliary). Of course, if n = 1, we simply move the single disk directly from the source peg to the destination peg .

60. Tower of Hanoi puzzle input’s size : number of disks n moving one disk as the algorithm’s basic operation. the number of moves M(n) depends on n only, and we get the following recurrence equation for it: M(n) = M(n − 1) + 1+ M(n − 1) for n > 1. initial condition M(1) = 1

61. Divide-and-Conquer General Method The most-well known algorithm design strategy: Divide instance of problem into two or more smaller instances Solve smaller instances recursively Obtain solution to original (larger) instance by combining these solutions A control abstraction for divide and conquer is as given below-using control abstraction a flow of control of a procedure is given.

62. Divide-and-Conquer General Method The Computing time of above procedure of divide and conquer is given by the recurrence and relation. a problem of size n a problem of size n/2 a problem of size n/2 a solution to subproblem 1 a solution to Subproblem 2 a solution to the original problem

63. Divide-and-Conquer General Method For example ,if we want to compute sum of n numbers then by divide and conquer we can solve the problem as

64. Divide-and-Conquer General Method If we want to divide a problem of size n into size of n/b taking f(n) time to divide and combine, then we can set up recurrence relation for obtaining time for size n is -

65. General Divide-and-Conquer Recurrence T ( n ) = aT ( n/b ) + f ( n ) where f ( n )   ( n d ), d  Master Theorem : If a < b d , T ( n )   ( n d ) If a = b d , T ( n )   ( n d log n ) If a > b d , T ( n )   ( n log b a ) Note: The same results hold with O instead of  . Examples: T ( n ) = 4 T ( n /2) + n  T ( n )  ? T ( n ) = 4 T ( n /2) + n 2  T ( n )  ? T ( n ) = 4 T ( n /2) + n 3  T ( n )  ?  ( n^2 )  ( n^2log n )  ( n^3 )

66. Efficiency Analysis of divide and conquer

67. Efficiency Analysis of divide and conquer (Cont…)

68. Efficiency Analysis of divide and conquer (Cont…)

69. Binary Search A binary search looks for an item in a list using a divide-and conquer strategy. Very efficient algorithm for searching in sorted array : Binary search algorithm assumes that the items in the array being searched are sorted The algorithm begins at the middle of the array in a binary search If the item for which we are searching is less than the item in the middle , we know that the item won’t be in the second half of the array Once again we examine the “middle” element The process continues with each comparison cutting in half the portion of the array where the item might be Binary Search: middle element. An element which is to be searched from the list of elements sorted in array A[0…n-1] is called KEY element. mid = left + right 2

70. Binary Search

71. Example Consider a list of elements sorted in array A as The Key element (i.e. the element to be searched) is 60. Now to obtain middle element we will apply formula. m=(0+6)/2 =3 left + right 2 mid =

72. Binary Search Yes,i.e . the number is present in the list. Thus we can search the desired number from the list of elements.

73. Algorithm for Binary Search

74. Analysis The Basic operation in binary search is comparison of search key (i.e. KEY) with the array elements. To analyze the efficiency of binary search we must count the number of times the search keys compared with the array elements. The comparison is also called a three way comparison because algorithm makes the comparison to determine whether KEY is smaller, equal to or greater than A[m]. In this algorithm after one comparison the list of n elements is divided into n/2 sub lists.

75. Analysis The worst case efficiency is that the algorithm compares all the array elements for searching the desired element.. One comparison is made and based on this comparison array is divided each time in n/2 sub lists. Hence the time complexity is given by But as we consider the rounded down value when array gets divided the above equations can be written as The above recurrence relation can be solved further. Assume n = 2 k the equation (1) becomes,

76. Analysis-Backward substitution Method

77. Backward substitution Method

78. Backward substitution Method

79. Average Case To obtain average case efficiency of binary search, consider some samples of input n. Again A[2]=33 and 33<44 we divide list. In right sub list A[4]=44 and key is 44. thus total 3 comparisons are made to search 44.

80. To Summarize the above operations. To Summarize the above operations. Observing the above given table we can write

81. For instance if n=2 then,,,Similarly if n=8, then……Thus we can write that, Advantage of binary search Binary search is an optimal searching algorithm using which we can search the derired element very efficiently. Disadvantage of binary search This algorithm requires the list to be sorted. Then only this method is applicable. Applications of binary search efficient searching method and is used to search desired record from database. For solving nonlinear equation with one unknown this method is used.

82. Implementation of recursive Binary Search algorithm

83. Implementation of recursive Binary Search algorithm

84. Merge sort The Merge sort is a sorting algorithm that uses the divide and conquer strategy. In this method division is dynamically carried out. Divide: divide the n -element sequence into two sub problems of n /2 elements each. Conquer : sort the two subsequences recursively using merge sort. If the length of a sequence is 1, do nothing since it is already in order. Combine : merge the two sorted subsequences to produce the sorted answer.

85. Merge sort Consider the elements as 70,20,30,40,10,50,60

86. Merge sort Sort the following elements using merge sort 10,5,7,6,1,4,8,3,2,9.

87. Merge sort

88. Merge sort

89. Logic Explanation

90. Logic Explanation First Make two sub lists as

91. Logic Explanation Consider that at some instance we have got two sub list 20,30,40,70 and 10,50,60 then

92. Logic Explanation

93. Logic Explanation

94. Logic Explanation

95. Logic Explanation

96. Logic Explanation

97. Logic Explanation

98. Logic Explanation

99. Analysis In Merge sort algorithm the two recursive calls are made. Each recursive call focuses on n/2 elements of the list. After two recursive call is made to combine two sub lists i.e. to merge all n elements. Hence we can write recurrence relation as We can obtain the time complexity of merge sort using two methods Master Theorem Substitution method Master Theorem

100. Master Theorem

101. Substitution Method

102. Logic Explanation

103. Logic Explanation

104. Selection Sort-brute force technique We start selection sort by scanning the entire given list to find its smallest element and exchange it with the first element, putting the smallest element in its final position in the sorted list. Then we scan the list, starting with the second element, to find the smallest among the last n − 1 elements and exchange it with the second element, putting the second smallest element in its final position. Generally, on the ith pass through the list, which we number from 0 to n − 2, the algorithm searches for the smallest item among the last n − i elements and swaps it with Ai .After n − 1 passes, the list is sorted.

105. Eg. An array A[5]={64,25,12,22,11} 0 , 1 , 2, 3, 4 PASS 1: i=0 // range of i={0,1,2,3} // for i=0 to n-2 min 0 //min=i j1 //range of j={1,2,3,4} //for j=i+1 to n-1 25< 64 min 1 //if A[j]<A[min] minj j 2 , 12<25 min2 j 3 , 22<12 j 4 , 11<12 //end of j Swap 64 and 11 // swap A[i] and A[min] // Now list becomes 11,25,12,22,64 // Now list is 11,25,12,22,64 PASS 2: i=1 min 1 j2 12< 25 min 2 j 3 , 22<12

106. j 4 , 64<12 //end of j Swap 25 and 12 // Now list becomes 11,12,25,22,64 PASS 3: i=2 min 2 j 3 , 22<25 min3 j 4 , 64<22 //end of j Swap 25 and 22 // Now list becomes 11,12,22,25,64 // Now list is 11,12,22,25,64 PASS 4: i=3 min 3 j 4 , 64<25 //end of j Swap 25 and 64 // Now list becomes 11,12,22,25,64 Output array A[5]={11,12,22,25,64}

107. Analysis The input size is given by the number of elements n. basic operation is the key comparison A[j ]<A[min]. The number of times it is executed depends only on the array size and is given by the following sum: Thus, selection sort is a (n 2 ) algorithm on all inputs.

108. Bubble sort brute-force application to the sorting problem is to compare adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up “bubbling up” the largest element to the last position on the list. The next pass bubbles up the second largest element, and so on, until after n − 1 passes the list is sorted.

109. Eg.an array A[5]={5,1,4,2,8} 0,1,2,3,4 PASS 1: i=0 //range of i={0,1,2,3} //for i=0 to n-2 j=0 //range of j={0,1,2,3} //for j=0 to n-2-i 1<5 //A[j+1]<A[j] Swap 1 and 5, //swap A[j] and A[j+1] //List becomes 1,5,4,2,8 j=1 , 4<5 ,swap 4 and 5 // list becomes 1,4,5,2,8 j=2 , 2<5 ,swap 2 and 5 // list becomes 1,4,2,5,8 j=3, 8<5 // list remains 1,4,2,5,8

110. Now the list is 1,4,2,5,8 PASS 2: i=1 j=0 //range of j={0,1,2} //for j=0 to n-2-i 4<1 //A[j+1]<A[j] //List remains 1,4,2,5,8 j=1 , 2<4 , swap 2 and 4 // list becomes 1,2,4,5,8 j=2 , 5<4 // list remains 1,2,4,5,8 PASS 3: Now the list is1,2,4,5,8 i=2 j=0 //range of j={0,1} //for j=0 to n-2-i 2<1 // list remains 1,2,4,5,8 j=1 , 4<2 // list remains 1,2,4,5,8

111. PASS 4: Now the list is1,2,4,5,8 i=3 j=0 //range of j={0} //for j=0 to n-2-i 2<1 // list remains 1,2,4,5,8 Output array A[5]={1,2,4,5,8} Analysis: The number of key comparisons for the bubble-sort is the same for all arrays of size n; it is obtained by a sum that is almost identical to the sum for selection sort:

112. sequential search This is a straightforward algorithm that searches for a given item (some search key K) in a list of n elements by checking successive elements of the list until either a match with the search key is found or the list is exhausted.

113. In the worst case, when there are no matching elements or the first matching element happens to be the last one on the list, the algorithm makes the largest number of key comparisons among all possible inputs of size n . Cworst(n) = n The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size. Cbest(n) = 1 Average case:

114. For example, if p = 1 (the search must be successful), the average number of key comparisons made by sequential search is (n + 1)/2; that is, the algorithm will inspect, on average, about half of the list’s elements. If p = 0 (the search must be unsuccessful), the average number of key comparisons will be n because the algorithm will inspect all n elements on all such inputs. Cavg(n)=n

115. Closest-Pair Problem And Convex-Hull Problems Step 1 : Divide the points given into two subsets S 1 and S 2 by a vertical line x = c so that half the points lie to the left or on the line and half the points lie to the right or on the line. Step 2 : Find recursively the closest pairs for the left and right subsets. Step 3 : Set d = min{ d 1 , d 2 }.We can limit our attention to the points in the symmetric vertical strip of width 2 d as possible closest pair. Let C 1 and C 2 be the subsets of points in the left subset S 1 and of the right subset S 2 , respectively, that lie in this vertical strip. The points in C 1 and C 2 are stored in increasing order of their y coordinates, which is maintained by merging during the execution of the next step. Step 4 For every point P ( x , y ) in C 1 , we inspect points in C 2 that may be closer to P than d . There can be no more than 6 such points (because d ≤ d 2 )!

116. Quick Sort Select a pivot (partitioning element) – here, the first element Rearrange the list so that all the elements in the first s positions are smaller than or equal to the pivot and all the elements in the remaining n-s positions are larger than or equal to the pivot (see next slide for an algorithm) Exchange the pivot with the last element in the first (i.e., ) subarray — the pivot is now in its final position Sort the two subarrays recursively. p A[ i ]  p A[ i ]  p

117. Quick Sort Algorithm Quick (A[0……n-1], low,high ) Pblm : sorting of array A[0…n-1] i/p: An array A[0….n-1]in which unsorted elmts are given.low indicates leftmost elmt in the list and high indicates the rightmost elmt in the list. o/p: sorted in ascending order. If(low<high)then //split the array into two sub arrays m partition(A[low…high])//m is mid of the array. Quick(A[low…m-1]) Quick(A[mid+1….high])

118. Quick Sort Algorithm partition(A[low…high]) Pblm : partition the subarray using the first element as pivot element. i/ p: subarray A with low as lower most index of the array and high as higher most index of the array. o/p: partitioning of array A is done and pivot occupies its proper position. And the rightmost index of the list is returned. pivot A [low] ilow jhigh+1

119. While(i<=j)do { While(A[i]<=pivot) do i  i+1 While(A[j]>=pivot) do j j-1 If(i<=j)then Swap(A[i],A[j]) / /swap A[i] and A[j] } Swap(A[low],A[j] ) //when i crosses j swap A[low] and A[j] Return j //rightmost index of the list

120. o/p array is 1 2 3 4 5 7 8 9

121. Best Case-split in the middle Recurrence relation C(n)=C(n/2)+C(n/2) + n for n>1 C(n/2)  time required to sort left and right subarray . n time required for partitioning the subarray . With initial condition: C(1)=0 Analysis

122. In the worst case, one of the two subarrays will be empty arrays , i.e., for inputs for which the problem is already solved if A [0 ..n − 1] is a strictly increasing array and we use A [0] as the pivot , the left-to-right scan will stop on A [1] while the right-to-left scan will go all the way to reach A [0] , indicating the split at position 0. So , after making n + 1 comparisons to get to this partition and exchanging the pivot A [0] with itself, the algorithm will be left with the strictly increasing array A [1 ..n − 1] to sort.

123. The total number of key comparisons made will be equal to Cworst (n)=(n+1)+n+(n-1)+(n-2)+….2+1

124. Let Cavg (n) be the average number of key comparisons made by quicksort on a randomly ordered array of size n . A partition can happen in any position s ( 0 ≤ s ≤ n −1 ) after n +1comparisons are made to achieve the partition. After the partition, the left and right subarrays will have s and n − 1− s elements, respectively. Assuming that the partition split can happen in each position s with the same probability 1 /n, we get the following recurrence relation:

125. we get the following recurrence relation: m

126. Dynamic programming Invented by a U.S. mathematician, Richard Bellman in the 1950s. Dynamic programming is a technique for solving problems with overlapping subproblems . a given problem’s solution to solutions of its smaller subproblems . Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller subproblems only once and recording the results in a table from which a solution to the original problem can then be obtained. Eg : The Fibonacci numbers are the elements of the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . , which can be defined by the simple recurrence F(n) = F(n − 1) + F(n − 2) for n > 1 Two initial conditions are F(0)=0, F(1)=1

127. dynamic programming  is a method for solving a complex problem by breaking it down into a collection of simpler subproblems , solving each of those subproblems just once, and storing their solutions - using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a modest expenditure in storage space. The technique of storing solutions to subproblems instead of recomputing them is called " memorization ".

128. DIFFERENCE BETWEEN DC & DP DIVIDE AND CONQUER DYNAMIC PROGRAMMING 1. Divide the given problem into many   Subproblems . Find the individual  solutions and combine them to get the  solution for the main problem. 1. Many decisions and sequences  are guaranteed and all the  overlapping  subinstances are considered. 2. Follows top down technique. (recursive) 2. Follows bottom up technique. (iterative) 3. Split the input only at specific points  (midpoint). 3. Split the input at every possible  Points rather than at a  particular  point.After trying all split points it determines which split point is optimal. 4. Each problem is independent. 4. Sub-problems are dependent on the  main problem.

129. DIFFERENCE BETWEEN DC & DP DIVIDE AND CONQUER DYNAMIC PROGRAMMING Less efficient because of rework on solutions Efficient than Divide & conquer Duplicate sub solutions may be obtained(duplications are neglected) Duplications in solutions is avoided totally. principle of optimality an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances . an  optimization problem  is the  problem  of finding the  best  solution from all  feasible solutions . Two major types of optimization problems: minimization or maximization

130. Floyd’ algorithm Floyd’s algorithm is for finding the shortest path between every pair of vertices of a graph. The algorithm works for both directed and undirected graphs. The graph may contain negative edges but it should not contain negative cycles.

131. Knapsack Problem and Memory Functions dynamic programming algorithm for the knapsack problem: given n items of known weights w1, . . . , wn and values v1, . . . , vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. Let us consider an instance defined by the first i items, 1≤ i ≤ n, with weights w1, . . . , wi , values v1, . . . , vi , and knapsack capacity j, 1 ≤ j ≤ W. Let F( i , j) be the value of an optimal solution to this instance, i.e., the value of the most valuable subset of the first i items that fit into the knapsack of capacity j.

132. We can divide all the subsets of the first i items that fit the knapsack of capacity j into two categories: those that do not include the ith item and those that do. Note the following: 1. Among the subsets that do not include the ith item, the value of an optimal subset is, by definition, F( i − 1, j). 2. Among the subsets that do include the ith item (hence, j − w ≥ 0), an optimal subset is made up of this item and an optimal subset of the first i − 1 items that fits into the knapsack of capacity j − wi . The value of such an optimal subset is vi + F( i − 1, j − wi ).

133. i j 1 2 3 4 5 1 2 3 4

134. Knapsack Problem and Memory Functions Steps to select actual knapsack item: Let i = n and k = W then while (i>0 and k>0) { if(table [ i,k ] table[i-1,k]) then mark i th item as in knapsack

135. Knapsack Problem and Memory Functions (Cont.…) i = i-1 and k=k- w i // selection of i th item. else i = i-1 // do not select of i th item. }

136. Knapsack Problem and Memory Functions (Cont.…) Example:

137. Greedy Technique The greedy method uses the subset paradigm or ordering paradigm to obtain the solution. In subset paradigm, at each stage the decision is made based on whether a particular input is in optimal solution or not . Prim’s Algorithm Minimum Spanning Tree: A minimum spanning tree of a weighted connected graph G is a minimum tree with minimum or smallest weight. Spanning tree: A spanning tree of a graph G is a sub graph which is basically a tree and it contains all the vertices of G containing no circuit

138. Prim’s Algorithm (Cont.….) ALGORITHM Prim (G) //Prim’s algorithm for constructing a minimum spanning tree //Input: A weighted connected graph G = (V, E) //Output: ET, the set of edges composing a minimum spanning tree of G V T ← {v } //the set of tree vertices can be initialized with any vertex E T ←∅ for i ←1 to |V| − 1 do find a minimum-weight edge e ∗ = (v ∗ , u ∗ ) among all the edges (v, u) such that v is in V T and u is in V − V T V T ←V T ∪ {u ∗ } E T ←ET∪ {e ∗ }

139. Kruskal’s Algorithm Kruskal’s algorithm looks at a minimum spanning tree of a weighted connected graph G = ( V, E ) as an acyclic sub graph with | V | − 1 edges for which the sum of the edge weights is the smallest. Kruskal’s Algorithm Prim’s algorithm This algorithm is for obtaining minimum spanning tree by selecting the adjacent vertices of already selected vertices.   This algorithm is for obtaining minimum spanning tree but it is not necessary to choose adjacent vertices of already selected vertices.  

140. D ijkstra’s A lgorithm Dijkstra’s algorithm is used to find shortest path. This algorithm is also known as single source shortest path algorithm. In this algorithm, for a given vertex called source the shortest path to all other vertices is obtained. In this algorithm the main focus is not to find only one single path but to find the shortest paths from any vertex to all other remaining vertices. This algorithm is applicable to graphs with non-negative weights only. Algorithm DagShortestPaths (G, s) //Solves the single-source shortest paths problem for a dag //Input: A weighted dag G = [V,E] and its vertex s //Output: The length dv of a shortest path from s to v and // its ultimate vertex pv for every vertex v in V topologically sort the vertices of G

141. D ijkstra’s Algorithm ( Cont …) for every vertex v do d v ←∞; p v ← null d s ← 0 for every vertex v taken in topological order do for every vertex u adjacent to v do if d v + w(v, u) < d u

142. Graph coloring Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color . Here coloring of a graph means assignment of colors to all vertices or vertex coloring . The smallest number of colors needed to color a graph G is called its chromatic number.

143. Limitations of Algorithm Power we studied dozens of algorithms for solving a variety of different problems . But the power of algorithms is limited , because of following reasons, There are some problems cannot be solved by any algorithm. Other problems can be solved algorithmically but not in polynomial time. when a problem can be solved in polynomial time by some algorithms, there are usually lower bounds on their efficiency Lower bound Arguments Lower bound- Estimating minimum amount of work needed to solve a given problem. Eg . Examples: number of comparisons needed to find the largest element in a set of n numbers number of comparisons needed to sort an array of size n

144. number of comparisons necessary for searching in a sorted array number of multiplications needed to multiply two n -by- n matrices To obtain efficiency of particular algorithm there are 2 ways. Establish the asymptotic efficiency class for the given pblm . What is the asymptotic efficiency class for finding lower bounds? Check whether the pblm lies in linear, quadratic, logarithmic/exponential category of efficiency class. Whenever we need to find an efficiency of an algm , it is better to compare one algm with other algms that are used to solve same type of pblms . Eg.sorting of elmts . Insertion sort efficiency n 2 (slower algm ) Quick sort, heap sort nlogn (faster algm )

145. Contd.. Lower bound can be an exact count an efficiency class ( ) Tight lower bound: there exists an algorithm with the same efficiency as the lower bound. Problem Lower bound Tightness sorting ( comparison-based ) ( n log n ) yes searching in a sorted array (log n ) yes element uniqueness ( n log n ) yes n -digit integer multiplication ( n ) unknown multiplication of n -by- n matrices ( n 2 ) unknown Methods for Establishing Lower Bounds trivial lower bounds information-theoretic arguments (decision trees) adversary arguments problem reduction

146. Trivial Lower Bounds Trivial lower bounds : based on counting the number of items that must be processed in input and generated as output. Examples: Trivial lower bound for generating all permutations of n number will be O(n!)..size of output is n! Product of 2 n x n matrices the trivial lower bound is O(n 2 ).Here 2n 2 elements input are to be processed and n 2 elements get produced as an output. TSP- the trivial lower bound is (n 2 ). Here n(n-1)/2 distances( input ) and n+1 cities as output. Binary search. Conclusions may and may not be useful be careful in deciding how many elements must be processed.

147. Information-theoretic arguments(decision trees) Decision tree — a convenient model of algorithms involving comparisons in which: internal nodes represent comparisons leaves represent outcomes (or input cases) Decision tree for 3-element insertion sort

148. Decision Trees and Sorting Algorithms Any comparison-based sorting algorithm can be represented by a decision tree ( for each fixed n ) Number of leaves (outcomes)  n ! Height of binary tree with n ! leaves   log 2 n !  Minimum number of comparisons in the worst case   log 2 n !  for any comparison-based sorting algorithm, since the longest path represents the worst case and its length is the height.  log 2 n !   n log 2 n ( by Sterling approximation )

149. Decision Trees and Sorting Algorithms This lower bound is tight ( mergesort or heapsort ) Ex. Prove that 5 (or 7) comparisons are necessary and sufficient for sorting 4 keys (or 5 keys, respectively). Adversary Arguments It’s a game between the adversary and the unknown algorithm. The adversary has the input and the algorithm asks questions to the adversary about the input. The adversary tries to make the algorithm work the hardest by adjusting the input (consistently). It wins the “game” after the lower bound time (lower bound proven) if it is able to come up with two different inputs. Example 1: “Guessing” a number between 1 and n using yes/no questions (Is it larger than x ?) Adversary: Puts the number in a larger of the two subsets generated by last question.

150. Example 2: Merging two sorted lists of size n a 1 < a 2 < … < a n and b 1 < b 2 < … < b n Adversary: Keep the ordering b 1 < a 1 < b 2 < a 2 < … < b n < a n in mind and answer comparisons consistently. Claim: Any algorithm requires at least 2 n -1 comparisons to output the above ordering (because it has to compare each pair of adjacent elements in the ordering) Ex: Design an adversary to prove that finding the smallest element in a set of n elements requires at least n-1 comparisons. Problem Reduction A is a difficult unsolvable pblm is to be reduced to another solvable pblm B with known algm . If pblm A is at least as hard as pblm as pblm B, then a LB for B is also lower bound for A. Hence we have to find pblm B with a known LB which is further used for finding LB of pblm A. This technique is called as Reduction.

151. Strassen’s Matrix Multiplication An algorithm was published by V. Strassen in 1969. The principal of the algorithm lies in the discovery that we can find the product C of two 2 × 2 matrices A and B with just seven multiplications as opposed to the eight required by the brute-force algorithm . This is accomplished by using the following formulas:

152. Thus, to multiply two 2 × 2 matrices, Strassen’s algorithm makes seven multiplications and 18 additions/subtractions, whereas the brute-force algorithm requires eight multiplications and four additions. These numbers should not lead us to multiplying 2 × 2 matrices by Strassen’s algorithm. Let A and B be two n × n matrices where n is a power of 2. (If n is not a power of 2, matrices can be padded with rows and columns of zeros.)

153. We can divide A,B , and their product C into four n/2 × n/2 submatrices each as follows : For example, C00 can be computed either as A00 ∗ B00 +A01 ∗ B10 or as M1 + M4 − M5 + M7 where M1, M4, M5, and M7 are found by Strassen’s formulas, with the numbers replaced by the corresponding submatrices . If the seven products of n/2 × n/2 matrices are computed recursively by the same method, we have Strassen’s algorithm for matrix multiplication. asymptotic efficiency of this algorithm . If M(n) is the number of multiplications made by Strassen’s algorithm in multiplying two n × n matrices (where n is a power of 2), we get the following recurrence relation for it:

154. Since this savings in the number of multiplications was achieved at the expense of making extra additions. To multiply two matrices of order n>1 , the algorithm needs to multiply seven , matrices of order n/2 and make 18 additions/subtractions of matrices of size n/2; when n = 1, no additions are made since two numbers are simply multiplied . Strassen ’ s algorithm efficiency is θ ( n log 2 7 ) , which is a better efficiency class than θ (n 3 ) of the brute-force method .

155. Travelling Salesman Problem Using Branch and Bound TSP can be stated as follows, consider that there are n cities and travelling salesman has to visit each city exactly once and has to return to the city from where he has started. Finding shortest hamiltonian circuit of a graph. Computing lower bounds using the formula. LB= ∑ (sum of costs of the two least cost edges v ε V adjacent to v) / 2

156. a b c d e LB = [(1+ 3) + (3 + 6) + (1+ 2) + (3 + 4) + (2 + 3)]/2 = 28/2=14.(this is the root of the state space tree) Compute the distances at level 1 a-b,a-c,a-d,a-e. Compute the distances at level 2 a-b-c,a-b-d, a-b-e. Compute the distances at level 3 a-b-c-d,a-b-c-e and a-b-d- c,a -b-d-e. Thus the state space tree can be

157. LB = [(1+ 3) + (3 + 6) + (1+ 2) + (3 + 4) + (2 + 3)]/2 = 28/2=14.(this is the root of the state space tree) Node 1:consider distance a-b in computation of the corresponding vertices along with 1 minimum distance. Find 2 least cost edges adjacent to V/2. a=a-b + a-c=3+1=4 (consider a-b here) b=a-b+b-c=3+6=9 (consider a-b here) c=a-c+c-e=1+2=3 LB=4+9+3+7+5=28/2=14 d=d-e+c-d=3+4=7 e=c-e+d-e=2+3=5

158. Node 2:consider distance a-c in computation of the corresponding vertices along with 1 minimum distance. Find 2 least cost edges adjacent to V/2. a=a-b + a-c=3+1=4 (consider a-c here) b=a-b+b-c=3+6=9 c=a-c+c-e=1+2=3 (consider a-c here) d=d-e+c-d=3+4=7 e=c-e+d-e=2+3=5 LB=4+9+3+7+5=28/2=14

159. Node 3:consider distance a-d in computation of the corresponding vertices along with 1 minimum distance. Find 2 least cost edges adjacent to V/2. a=a-c + a-d=1+5=6 (consider a-d here) b=a-b+b-c=3+6=9 c=a-c+c-e=1+2=3 d=d-e+a-d=3+5=8 (consider a-d here) e=c-e+d-e=2+3=5 LB=6+9+3+8+5=31/2=15.5=16

160. Node 4:consider distance a-e in computation of the corresponding vertices along with 1 minimum distance. Find 2 least cost edges adjacent to V/2. a=a-c + a-e=1+8=9 (consider a-e here) b=a-b+b-c=3+6=9 c=a-c+c-e=1+2=3 d=c-d+d-e=4+3=7 e=c-e+a-e=2+8=10 (consider a-e here) LB=9+9+3+7+10=38/2=19

161. Node 5:consider distance a-b-c .including edges (a-b),(b-c) wherever possible. Find 2 least cost edges adjacent to V/2. a=a-b + a-c=3+1=4 (consider a-b here) b=a-b+b-c=3+6=9 c=a-c+b-c=1+6=7 (consider b-c here) d=d-c+d-e=4+3=7 e=c-e+d-e=2+3=5 LB=4+9+7+7+5=32/2=16 Same as node 6 (a-b-d),node 7 (a-b-e)

162. Node 8:consider distance a-b-c-d (e,a).including edges (a-b),(b-c) ,(c-d) (e,a)wherever possible. Find 2 least cost edges adjacent to V/2. a=a-b + a-e=3+8=11 (consider a-b & e,ahere) b=a-b+b-c=3+6=9 (consider a-b,b-c here) c=b-c+c-d=6+4=10 (consider b-c,c-d here) d=c-d+d-e=4+3=7 (consider c-d here) e=a-e+d-e=8+3=11(consider a-e here) LB=11+9+10+7+11=48/2=24 Same as node 9 a-b-c-e( d,a ) Same as node 10 a-b-d-c ( e,a )

163. Node 11:consider distance a-b-d-e (c,a).including edges (a-b),(b-d) ,(d-e) (c,a)wherever possible. Find 2 least cost edges adjacent to V/2. a=a-b + a-c=3+1=4 (consider a-b & e,ahere) b=a-b+b-d=3+7=10 (consider a-b,b-c here) c=a-c+c-e=1+2=3 (consider b-c,c-d here) d=b-d+d-e=7+3=10 (consider c-d here) e=c-e+d-e=2+3=5(consider a-e here) LB=4+10+3+10+5=32/2=16 At node 11 we get optimum tour . Hence the optimal tour of TSP is a-b-d-e-c-a with cost 16.

164. Approximation Algorithm for NP-Hard Problems If an NP hard pblm can be solved in polynomial time then all NP-complete pblms can also be solved in polynomial time. All NP-complete pblms are NP-hard but all NP-hard pblms cannot be NP-complete. A pblm is NP-complete if it belongs to NP-class and also every pblm in NP can also be solved in polynomial time. The Np class pblms are the decision pblms that can be solved by non-deterministic polynomial algorithms. non-deterministic-no particular rule is defined. Approximation Algorithm for TSP Decision version of this algm belongs to NP complete pblm . Optimization version of this algm belongs to NP-hard pblms . 2 Approximation algms are used for TSP.A NP-hard class of pblms and those are

165. Approximation algms for TSP. Nearest Neighbour algm . Twice around the tree algm . Nearest Neighbour algm Idea-choose nearest neighbour while traversing from one city to another. Q1.using nearest neighbour algm,obtain the optimal solution for given travelling salesman pblm and also find the accuracy ratio for the same. Accuracy ratio r(S a ) = f(S a )/f(S*) Where, S a  approximate solution f(S a )  value of objective function for soln given by approximation algm . f(S*)  value of objective function Generally r(S a ) >=1. When r(S a ) reaches close to 1 then it is a better approximate solution.

166. Nearest Neighbour algm We will apply Nearest Neighbour algm for the tour for given TSP. The output is a-b-c-d-a.., S a =2+3+2+7=14. Now the optimal solution is a-b-d-c -a S*=2+4+2+4=12. Accuracy ratio r(S a ) = f(S a )/f(S*)=14/12=1.16 Hence the tour S a is 16% longer than optimal tour S*. Drawback: long path. Important role is the distance d-a=7 r(S a ) = f(S a )/f(S*) = 7+w/12 ( i.e w is the edge d-a) As ‘w’ increases, r(S a ) increases.For longer value of w, r(S a ) tends to infinity.Hence our AA will fail to obtain the optimal soln. Twice around the tree algorithm- Algm : Compute MST from the graph. Start at any arbitrary city and walk around the tree and record nodes visited. Eliminate duplicates from the generated node list

167. Christofides Algorithm There is an approximation algorithm with a better performance ratio for the Euclidean traveling salesman problem. The tour yields a − b − c − e − d − a of length 37.