Design and analysis of algorithms Module-I.pptx

Ada

1. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

2. Module I INTRODUCTION

3. AGENDA What is an Algorithm? Formal and Informal Definition Properties of an Algorithm Fundamentals Of Algorithmic Problem Solving Example Assignment

4. An algorithm is a step by step procedure for solving the given problem/task. An algorithm is independent of any programming language and machine. What is an algorithm?

5. Algorithms are used in our day to day activities Example: What is an algorithm?

6. Informal definition An Algorithm is any well-defined computational procedure that takes some value or set of values as input and produces a set of values or some value as output. Thus algorithm is a sequence of computational steps that transforms the input into the output.

7. Formal definition 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. This definition can be illustrated by a simple diagram:

8. Properties of an algorithm

9. INPUT : An algorithm must have zero or more but must be finite number of inputs. Example of zero input algorithm. Print the ASCII code of each of the letter in the alphabet of the computer system. OUTPUT : An algorithm must have at-least one desirable outcome, i.e., output. Properties of an algorithm

10. DEFINITENESS: Each instruction should be clear and unambiguous. It must be perfectly clear what should be done. Example Directions which are ambiguous “add 6 or 7 to x” compute x/0 It is not clear which of the 2 possibilities should be done Properties of an algorithm

11. FINITENESS: The algorithm should terminate after a finite number of steps in all the cases, if we trace the algorithm. The time for termination should be reasonably short Properties of an algorithm

12. EFFECTIVENESS: Every instruction must very basic so that it can be carried out, in principle, by a person using only pencil & paper in a finite amount of time. Example -Effective Performing arithmetic on integers Example of not effectiveness. Properties of an algorithm

13. Fundamentals Of Algorithmic Problem Solving Algorithms are procedural solutions to problems. These solutions are not answers but specific instructions for getting answers. The following diagram briefly illustrates the sequence of steps one typically goes through in designing and analyzing an algorithm.

14. Fundamentals Of Algorithmic Problem Solving

15. Example Write an algorithm to add two integer numbers entered by user. Step 1: Start Step 2: Declare variables num1, num2 and sum. Step 3: Read integer values num1 and num2. Step 4: Add num1 and num2 and assign the result to sum. sum←num1+num2 Step 5: Display sum Step 6: Stop

16. assignment Write an Algorithm To Find factorial of a number To Find Roots of the quadratic equation ax 2  + bx + c = 0

17. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

18. Module I INTRODUCTION

19. Recap… What is an Algorithm? Formal and Informal Definition Properties of an Algorithm Fundamentals Of Algorithmic Problem Solving Example Assignment

20. AGENDA Fundamentals Of Algorithmic Problem Solving

21. Fundamentals Of Algorithmic Problem Solving

22. Understand the problem Before designing an algorithm the most important thing is to understand the problem given. Asking questions, doing a few examples by hand, thinking about special cases, etc. An Input to an algorithm specifies an instance of the problem the algorithm that it solves. Important to specify exactly the range of instances the algorithm needs to handle. Else it will work correctly for majority of inputs but crash on some ―boundary‖ value. A correct algorithm is not one that works most of the time, but one that works correctly for all legitimate inputs.

23. Decide on: Ascertaining the capabilities of a computational device The vast majority of algorithms in use today are still destined to be programmed for a computer closely resembling the von Neumann machine—a computer architecture. Von Neumann architectures are sequential and the algorithms implemented on them are called sequential algorithms. Algorithms which designed to be executed on parallel computers called parallel algorithms. For very complex algorithms concentrate on a machine with high speed and more memory where time is critical.

24. Decide on: Deciding on appropriate data structures Algorithms may or may not demand ingenuity in representing their inputs. Inputs are represented using various data structures. Algorithm + data structures=program. Algorithm Design Techniques and Methods of Specifying an Algorithm 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. The different algorithm design techniques are: brute force approach, divide and conquer, greedy method, decrease and conquer, dynamic programming, transform and conquer and back tracking.  

25. Decide on: Methods of specifying an algorithm : Using natural language, in this method ambiguity problem will be there. The next 2 options are : pseudo code and flowchart. Pseudo code: mix of natural and programming language. More precise than NL Flow chart: method of expressing an algorithm by collection of connected geometric shapes containing descriptions of the algorithm‘s steps. This representation technique has proved to be inconvenient for large problems. Algorithm needs to be converted into a computer program written in a particular computer language. Hence program as yet another way of specifying the algorithm, although it is preferable to consider it as the algorithm‘s implementation.

26. Decide on: Choosing between exact and approximate problem solving For exact result->exact algorithm For approximate result->approximation algorithm. Examples of exact algorithms: Obtaining square roots for numbers and solving non- linear equations. An approximation algorithm can be a part of a more sophisticated algorithm that solves a problem exactly.

27. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

28. Module I INTRODUCTION

29. RECAP… Fundamentals Of Algorithmic Problem Solving

30. AGENDA Type of Algorithm Specification Pseudocode Conventions Example Assignment

31. Types of algorithm specification Algorithm can be described in three ways. Natural language like English : When this way is choosed care should be taken, we should ensure that each & every statement is definite and unambigious .

32. Types of algorithm specification Graphic representation called flowchart : This method will work well when the algorithm is small& simple.

33. Types of algorithm specification Pseudo-code Method : In this method, we typically describe algorithms as program, which resembles programming language constructs

34. Pseudo-Code Conventions Comments begin with // and continue until the end of line. Blocks are indicated with matching braces { and }. A compound statement ( i.e.,a collection of simple statements)can be represented as a block . The body of a procedure also forms a block . Statements are delimited by ; .

35. Pseudo-Code Conventions An identifier begins with a letter. The data types of variables are not explicitly declared. Compound data types can be formed with records. Here is an example, node = record { data type – 1 data-1; . . . data type – n data – n; node * link; } Here link is a pointer to the record type node. Individual data items of a record can be accessed with → and period (.)

36. Pseudo-Code Conventions Assignment of values to variables is done using the assignment statement. <Variable>:= <expression>; There are two Boolean values TRUE and FALSE. Logical Operators AND, OR, NOT Relational Operators <, <=,>,>=, =, != Elements of multidimensional arrays are accessed using [ and ]. For example, if A is a two dimensional array, the ( i,j ) th element of the array is denoted as A[ i , j]. Array indices start at zero.

37. Pseudo-Code Conventions The following looping statements are employed:for , while and repeat-until While Loop: while < condition > do { <statement-1> . . . <statement-n> }

38. Pseudo-Code Conventions For Loop: for variable: = value-1 to value-2 step step do { <statement-1> . . . <statement-n> } The clause “ step step ” is optional and taken as +1 if it does not occur, step could either be positive or negative.

39. Pseudo-Code Conventions repeat-until: repeat <statement-1> . . . <statement-n> until <condition>

40. Pseudo-Code Conventions A conditional statement has the following forms. if <condition> then <statement> if <condition> then <statement-1> else <statement-1>

41. Pseudo-Code Conventions Input and output are done using the instructions read & write. Algorithm, the heading takes the form, Algorithm Name (Parameter lists) where Name is the name of the procedure and (<parameter list>) is a listing of the procedure parameters. The body has one or more (simple or compound) statements enclosed within braces { and }. An algorithm may or may not return any values. Simple variables to procedures are passed by value. Arrays and records are passed by reference. An array name or a record name is treated as a pointer to the respective datatype .

42. Example As an example, the following algorithm finds and returns the maximum of n given numbers. Algorithm Max(A , n) // Purpose: To find Max in an array A[1:n] // Input: A is an array of size n // Output: Returns the max value in A[1:n] { Result := A[1]; for i := 2 to n do if A[ i ] > Result then Result :=A[ i ]; return Result; }

43. Assignment Write an Algorithm to find sum of ‘n’ numbers Write an Algorithm that performs linear search

44. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

45. Module I INTRODUCTION

46. RECAP…. Type of Algorithm Specification Pseudocode Conventions Example Assignment

47. AGENDA Need for Algorithm Analysis Analysis Framework Kinds of Efficiency Measuring An Input Size Units For Measuring Run Time Orders Of Growth Worst-Case, Best-Case, Average Case Efficiencies Example

48. Need for algorithm analysis An algorithm is a clearly specified set of simple instructions to be followed to solve a problem. Three questions for algorithm analysis What: What to analyze? How: How to analyze? Why: Why we need to do algorithm analysis? Judge an algorithm is “good” or “bad”. An algorithm with one year running time is hardly useful. An algorithm that requires tens gigabytes of main memory is not (currently) useful on most machines.

49. Types of efficiency Time efficiency - Indicates how fast an algorithm in question runs, i.e., running time Space efficiency - Deals with the extra space the algorithm requires.

50. How to analyze??? Measuring An Input Size Units For Measuring Run Time Orders Of Growth Worst-Case, Best-Case, Average Case Efficiencies

51. Measuring An Input Size An algorithm's efficiency is investigated as a function of some parameter ‘n’ indicating the algorithm's input size. Time Efficiency T(n)  where ‘n’ is the input size In most cases, selecting such a parameter is quite straightforward. For example, What will be the size for problems of sorting list , searching, finding the list's smallest element, and most other problems dealing with lists ??  # of elements in the list For the problem of evaluating a polynomial p(x) of degree n???  it will be the polynomial's degree or the number of its coefficients, which is larger by one than its degree .

52. Measuring An Input Size Computing the product of two n-by-n matrices.There are two natural measures of size for this problem. The matrix order n. The total number of elements N in the matrices being multiplied. The choice of an appropriate size metric can be influenced by operations of the algorithm in question.

53. Measuring An Input Size For example, how should we measure an input's size for a spell-checking algorithm? If the algorithm examines individual characters of its input, then we should measure the size by the number of characters; If it works by processing words, we should count their number as the input size. We should make a special note about measuring size of inputs for algorithms involving properties of numbers (e.g., checking whether a given integer n is prime).

54. Units For Measuring Run Time We can simply use some standard unit of time measurement-a second, a millisecond, and so on-to measure the running time of a program implementing the algorithm. There are obvious drawbacks to such an approach. They are Dependence on the speed of a particular computer Dependence on the quality of a program implementing the algorithm The compiler used in generating the machine code The difficulty of clocking the actual running time of the program.

55. Units For Measuring Run Time We need to measure algorithm efficiency, we should have a metric that does not depend on these extraneous factors. One possible approach is to count the number of times each of the algorithm's operations is executed. This approach is both difficult and unnecessary. The main objective is to identify the most important operation of the algorithm, called the basic operation , the operation contributing the most to the total running time, and compute the number of times the basic operation is executed. As a rule, it is not difficult to identify the basic operation of an algorithm.

56. Units For Measuring Run Time Problem Input Size Basic Operation Search for a key in a list of ‘n’ items # of items in the list Key Comparison Addition of 2 n x n matrices Dimensions of the matrices, n Addition Polynomial Evaluation Order of the polynomial Multiplication

57. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

58. Module I INTRODUCTION

59. RECAP…. Algorithm –Definition, Example Fundamentals of Algorithmic Problem Solving Type of Algorithm Specification Pseudocode Conventions Need for Algorithm Analysis Analysis Framework Kinds of Efficiency Measuring An Input Size

60. AGENDA Analysis Framework Kinds of Efficiency Measuring An Input Size Units For Measuring Run Time Orders Of Growth Basic Efficiency Classes

61. Types of efficiency Time efficiency - Indicates how fast an algorithm in question runs, i.e., running time Space efficiency - Deals with the extra space the algorithm requires.

62. How to analyze??? Measuring An Input Size Units For Measuring Run Time Orders Of Growth Worst-Case, Best-Case, Average Case Efficiencies

63. Measuring An Input Size An algorithm's efficiency is investigated as a function of some parameter ‘n’ indicating the algorithm's input size. Time Efficiency T(n)  where ‘n’ is the input size In most cases, selecting such a parameter is quite straightforward. For example, What will be the size for problems of sorting list , searching, finding the list's smallest element, and most other problems dealing with lists ??  # of elements in the list

64. Measuring An Input Size Computing the product of two n-by-n matrices.There are two natural measures of size for this problem. The matrix order n. The total number of elements N in the matrices being multiplied. The choice of an appropriate size metric can be influenced by operations of the algorithm in question.

65. Units For Measuring Run Time We can simply use some standard unit of time measurement-a second, a millisecond, and so on-to measure the running time of a program implementing the algorithm. There are obvious drawbacks to such an approach. They are Dependence on the speed of a particular computer Dependence on the quality of a program implementing the algorithm The compiler used in generating the machine code The difficulty of clocking the actual running time of the program.

66. Units For Measuring Run Time We need to measure algorithm efficiency, we should have a metric that does not depend on these extraneous factors. One possible approach is to count the number of times each of the algorithm's operations is executed. This approach is both difficult and unnecessary. The main objective is to identify the most important operation of the algorithm, called the basic operation , the operation contributing the most to the total running time, and compute the number of times the basic operation is executed. As a rule, it is not difficult to identify the basic operation of an algorithm.

67. Units For Measuring Run Time Example: Algorithm to find sum of n numbers Step 1: Identify input size: n – number of elements in the array Step 2: Identify the Basic Operation: Addition operation sum <- sum+A [ i ] Step 3: How many times the basic operation is executed For example we have 4 elements- it will be executed for i =0,1,2,3  4 times, Hence in general for n elements it will be executed n times n

68. Units For Measuring Run Time Let c op be the execution time of an algorithm‘s basic operation on a particular computer, and let C(n) be the number of times this operation needs to be executed for this algorithm. Then we can estimate the running time T (n) of a program implementing this algorithm on that computer by the formula T (n) ≈ c op C (n). Total number of steps for basic operation execution, C (n) = n

69. Orders of growth Measuring the performance of an algorithm in relation with the input size is called order of growth Example:

70. BASIC EFFICIENCY CLASSES

71. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

72. Module I INTRODUCTION

73. Recap…. Analysis Framework Kinds of Efficiency Measuring An Input Size Units For Measuring Run Time Orders Of Growth Basic Efficiency Classes

74. AGENDA Analysis Framework Worst-Case, Best-Case, Average Case Efficiencies Example Introduction to Asymptotic Notations

75. Time Complexity- running time We can estimate the running time T (n) of a program implementing the algorithm on the computer by the formula T (n) ≈ c op C (n). Where c op be the execution time of an algorithm‘s basic operation on a particular computer, and C(n) be the number of times this operation needs to be executed for this algorithm. T (n) ≈ C(n).

76. Worst-Case, Best-Case, Average Case Efficiencies Algorithm efficiency depends on the input size n. And for some algorithms efficiency not only on input size but also on the specifics of particular or type of input. Here in this case, We have 3 types of efficiencies: Best Case Efficiency Worst Case Efficiency Average Case Efficiency

77. Worst-Case, Best-Case, Average Case Efficiencies Worst-case efficiency: Efficiency (number of times the basic operation will be executed) for the worst case input of size n. i.e. The algorithm runs the longest among all possible inputs of size n. Best-case efficiency: Efficiency (number of times the basic operation will be executed) for the best case input of size n. i .e. The algorithm runs the fastest among all possible inputs of size n. Average-case efficiency: Average time taken (number of times the basic operation will be executed) to solve all the possible instances (random) of the input.

78. Example-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. Input size: n  no of elements in the list Basic Operation: Comparison Operation Does the Basic Operation depends only on input size or also on type of input????

79. Example-sequential search

80. Example-sequential search Worst case efficiency The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size. In the worst case the input might be in such a way that there are no matching elements or the first matching element happens to be the last one on the list, in this case the algorithm makes the largest number of key comparisons among all possible inputs of size n: C worst (n) = n. Hence T worst (n) = C worst (n) = n. The worst-case analysis provides very important information about an algorithm's efficiency by bounding its running time from above. In other words, it guarantees that for any instance of size n, the running time will not exceed C worst (n)

81. Example-sequential search best case efficiency 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. First, determine the kind of inputs for which the count C (n) will be the smallest among all possible inputs of size n. In sequential search, best-case inputs will be lists of size n with their first element equal to a search key; accordingly, C best (n) = 1. Hence T best (n) = C best (n) = 1.

82. Example-sequential search average case efficiency Average time taken (number of times the basic operation will be executed) to solve all the possible instances (random) of the input. To analyze the algorithm's average-case efficiency, we must make some assumptions about possible inputs of size n. It involves dividing all instances of size n into several classes so that for each instance of the class the number of times the algorithm's basic operation is executed is the same. Then a probability distribution of inputs needs to be obtained or assumed so that the expected value of the basic operation's count can then be derived.

83. Example-sequential search average case efficiency For sequential search: The average number of key comparisons C avg (n) can be computed as follows, The standard assumptions are, Let p be the probability of successful search. In the case of a successful search, the probability of the first match occurring in the i th position of the list is p/n for every i , where 1<= i <=n The number of comparisons made by the algorithm in such a situation is obviously i . In the case of an unsuccessful search, the number of comparisons is n with the probability of such a search being (1 - p).

84. Example-sequential search average case efficiency Therefore C avg (n) = Probability of succesful search + Probabiltiy of unsuccesful search C avg (n) = [1.p/n+2.p/n+3.p/n+…+ i.p /n……… n.p /n]+n.(1-p) =p/n[1+2+3…+ i +…..+n]+n(1-p) Example, if p = 1 (i.e., the search must be successful), the average number of key comparisons made by sequential search is (n + 1) /2. If p = 0 (i.e., 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.

85. ASYMPTOTIC NOTATIONS The efficiency analysis framework concentrates on 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).

86. ASYMPTOTIC NOTATIONS Three Asymptotic Notations:

87. ASYMPTOTIC NOTATIONS Three Asymptotic Notations:

88. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

89. Module I INTRODUCTION

90. Recap… Analysis Framework Worst-Case, Best-Case, Average Case Efficiencies Example Introduction to Asymptotic Notations

91. AGENDA Types of Asymptotic Notations Informal Definition of Asymptotic Notations Formal Definition of Asymptotic Notations

92. ASYMPTOTIC NOTATIONS Three Asymptotic Notations:

93. BASIC EFFICIENCY CLASSES

94. ASYMPTOTIC NOTATIONS Informal Definition: Informally, O(g(n)) is the set of all functions with a lower or same order of growth as g(n) (to within a constant multiple, as n goes to infinity). Examples: The second notation, Ω (g(n)), stands for the set of all functions with a higher or same order of growth as g(n) (to within a constant multiple, as n goes to infinity). Examples: Finally, Θ (g(n)) is the set of all functions that have the same order of growth as g(n).

95. The definition is illustrated in the following figure.

96. The definition is illustrated in the following figure.

97. The definition is illustrated in the following figure.

98. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

99. Module I INTRODUCTION

100. Recap… Types of Asymptotic Notations Informal Definition of Asymptotic Notations Formal Definition of Asymptotic Notations

101. AGENDA Useful Property Involving the Asymptotic Notations Theorem Example Problems on Asymptotic Notations Assignment

102. Theorem: If t 1 (n) ∈ O(g 1 (n)) and t 2 (n) ∈ O(g 2 (n)), then t 1 (n) + t 2 (n) ∈ O(max{g 1 (n), g 2 (n)}) Proof: For any four arbitrary real numbers a 1 , b 1 , a 2 , b 2 : if a 1 ≤ b 1 and a 2 ≤ b 2 , then a 1 + a 2 ≤ 2 max{b 1 , b 2 }. Since t 1 (n) ∈ O(g 1 (n)), there exist some positive constant c 1 and some non negative integer n 1 such that t 1 (n) ≤ c 1 g 1 (n) for all n ≥ n 1  Eqn 1 Similarly, since t 2 (n) ∈ O(g 2 (n)), t 2 (n) ≤ c 2 g 2 (n) for all n ≥ n 2  Eqn 2 Useful property involving the asymptotic notations

103. Let us denote c 3 = max{c 1 , c 2 } and consider n ≥ max{n 1 , n 2 } so that we can use both inequalities. Adding them i.e.., Eqn 1 and Eqn 2 yields the following: t 1 (n) + t 2 (n) ≤ c 1 g 1 (n) + c 2 g 2 (n) ≤ c 3 g 1 (n) + c 3 g 2 (n) = c 3 [g 1 (n) + g 2 (n)] ≤ c 3 2 max{g 1 (n), g 2 (n)}. Hence, t 1 (n) + t 2 (n) ∈ O( max{g 1 (n), g 2 (n)} ), with the constants c and n required by the O(Big Oh) definition being 2c 3 = 2 max{c 1 , c 2 } and max{n 1 , n 2 }, respectively. Useful property involving the asymptotic notations

104. So what does this property imply for an algorithm that comprises two consecutively executed parts? It implies that the algorithm’s overall efficiency is determined by the part with a higher order of growth, i.e., its least efficient part Useful property involving the asymptotic notations

105. For example, we can check whether an array has equal elements by the following two-part algorithm: First, sort the array by applying some known sorting algorithm; Second, scan the sorted array to check its consecutive elements for equality. If, for example, a sorting algorithm used in the first part makes no more than  1/2  n(n  − 1 )  comparisons and hence its order of growth is  O(n 2 )   While the second part makes no more than  n  −   1 comparisons (and hence is in  O(n)),  the efficiency of the entire algorithm   will be in  O( max{ n 2 , n } )  =  O(n 2 ). Useful property involving the asymptotic notations

106. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

107. Module I INTRODUCTION

108. Recap… Types of Asymptotic Notations Informal Definition of Asymptotic Notations Formal Definition of Asymptotic Notations

109. AGENDA Useful Property Involving the Asymptotic Notations Theorem Example Problems on Asymptotic Notations Assignment

110. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

111. Module I INTRODUCTION

112. Recap… Useful Property Involving the Asymptotic Notations Theorem Example Problems on Asymptotic Notations

113. AGENDA Problems on Asymptotic Notations Mathematical Analysis of Non Recursive Algorithms General Plan Example 1: Finding the largest element in a given array Assignment

114. Problem 1: Consider f(n)=100n+5, Express f(n) using Big-Oh Solution: It is given that f(n)=100n+5. Replacing 5 with n(so that next higher order term is obtained), we get 100n+n=101n and call it cg(n) i.e., c(g(n))=101n Now, the following constraint is satisfied: f(n) ≤ cg(n) for all n ≥ n i.e., 100n+5 ≤ 101n for n ≥ 5 It is clear from above, that c=101, g(n)=n and n =5 So, by definition f(n) ∈ O(g(n)) i.e., f(n) ∈ O(n), Problems on Asymptotic Notations

115. Problem 2: Prove that: 100 n  + 5 ∈  O(n 2 ) Solution: Easiest way to prove that f(n) ∈ O(g(n)), we need to consider according to definition f(n) ≤ cg(n), Here f(n)=100n+5, g(n)= n 2 and to find c, is to take c to be the sum of the positive coefficients of f(n) Hence, 100n+5 ≤ 105 n 2 for all n ≥ 1 As per the Big-Oh definition, we have c=105 and n = 1 Hence proved, 100 n  + 5 ∈  O(n 2 ) Problems on Asymptotic Notations

116. Problem 3: Consider f(n)=100n+5, Express f(n) using Big-Omega Solution: It is given that f(n)=100n+5. we consider c(g(n))=100n Now, the following constraint is satisfied: f(n) ≥ cg (n) for all n ≥ n i.e., 100n+5 ≥ 100n for n ≥ 0 It is clear from above, that c=100, g(n)=n and n =0 So, by definition f(n) ∈  (g(n)) i.e., f(n) ∈  ( n) Problems on Asymptotic Notations

117. General plan for analyzing efficiency of non-recursive algorithms:   Decide on parameter n indicating the input size of the algorithm. Identify algorithm‘s basic operation . Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input, then investigate worst, average, and best case efficiency separately. Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Simplify summation using standard formulas and express C(n) using orders of growth . MATHEMATICAL ANALYSIS OF NON-RECURSIVE ALGORITHMS

118. Algorithm : Example 1: Finding the largest element in a given array

119. Analysis: Step 1: Identify Input size ‘n’: The number of elements = n (size of the array) Step 2: Identify the basic operation: Two operations can be considered to be as basic operation i.e., Comparison ::A[ i ]> maxval . Assignment : : maxval←A [ i ]. Here the comparison statement is considered to be the basic operation of the algorithm. Example 1: Finding the largest element in a given array

120. Analysis: Step 3: Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input then investigate worst, average, and best case efficiency separately. No best, worst, average cases- because the number of comparisons will be same for all arrays of size n and it is not dependent on type of input. Example 1: Finding the largest element in a given array

121. Analysis: Step 4: Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Let C(n) denotes number of comparisons made. Algorithm makes one comparison on each execution of the loop, which is repeated for each value of the loop‘s variable i within the bound between 1 and n – 1.               Example 1: Finding the largest element in a given array

122. Analysis: Step 5: Simplify summation using standard formulas and express C(n) using orders of growth . we have,               Example 1: Finding the largest element in a given array Standard Formula to be used: C(n)= C(n)  (n)

123. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

124. Module I INTRODUCTION

125. Recap… Problems on Asymptotic Notations Mathematical Analysis of Non Recursive Algorithms General Plan Example 1: Finding the largest element in a given array Assignment

126. AGENDA Mathematical Analysis of Non Recursive Algorithms General Plan Example 2: Element uniqueness problem Assignment

127. General plan for analyzing efficiency of non-recursive algorithms:   Decide on parameter n indicating the input size of the algorithm. Identify algorithm‘s basic operation . Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input, then investigate worst, average, and best case efficiency separately. Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Simplify summation using standard formulas and express C(n) using orders of growth . MATHEMATICAL ANALYSIS OF NON-RECURSIVE ALGORITHMS

128. Aim: Checks whether the elements in the array are distinct or not. It returns true if all the elements in the array are distinct or otherwise false Algorithm : Example 2: Element uniqueness problem

129. Example 2: Element uniqueness problem Analysis: Step 1: Identify Input size ‘n’: The number of elements = n (size of the array) Step 2: Identify the basic operation: Basic operation i s identified as , Comparison ::A[ i ]==A[j] Here the comparison statement is considered to be the basic operation of the algorithm.

130. Example 2: Element uniqueness problem Analysis: Step 3: Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input then investigate worst, average, and best case efficiency separately. Best, worst, average cases exist - because the number of comparisons will vary for the input of size n based on type of input.

131. Example 2: Element uniqueness problem Analysis: Step 4: Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Here, we need to consider both best and worst case efficiency Best Case Efficiency: Best Case occurs when the Array with first two elements are the pair of equal elements Let C best (n) denotes number of comparisons made in best case. Algorithm makes exactly one comparison for the best case input Therefore C best (n)=1 i.e., C best (n)   (1)              

132. Example 2: Element uniqueness problem Analysis: Worst Case Efficiency: Worst case input is an array giving largest comparisons. Array with no equal elements Array with last two elements are the only pair of equal elements Let C worst (n) denotes number of comparisons in worst case Algorithm makes one comparison for each repetition of the innermost loop i.e., for each value of the loop‘s variable j between its limits i + 1 and n – 1; and this is repeated for each value of the outer loop i.e , for each value of the loop‘s variable i between its limits 0 and n – 2.              

133. Example 2: Element uniqueness problem Analysis: Worst Case Efficiency: We need to set up the summation for C worst (n)              

134. Example 2: Element uniqueness problem Analysis: Step 5: Simplify summation using standard formulas and express C worst (n) using orders of growth . we have,               Let us Consider =n-1-i+1-1 =n-1-i [Obtained using the standard formula

135. Example 2: Element uniqueness problem Analysis: we have,               C worst (n)= (n-1-0)+(n-1-1)+(n-1-2)+…………………+(n-1-(n-3))+(n-1-(n-2)) =(n-1)+(n-2)+(n-3)+…………………………+2+1 =1+2+3+…….+(n-3)+(n-2)+(n-1) [Using the formula 1+2+3+….+n=n(n+1)/2] = = Therefore C worst (n)   (n 2 )

136. assignment

137. assignment

138. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

139. Module I INTRODUCTION

140. Recap… Mathematical Analysis of Non Recursive Algorithms General Plan Example 2: Element uniqueness problem Assignment

141. AGENDA Mathematical Analysis of Non Recursive Algorithms General Plan Example 3: Matrix Multiplication Example 4: Find number of digits in binary representation of a number Assignment

142. General plan for analyzing efficiency of non-recursive algorithms:   Decide on parameter n indicating the input size of the algorithm. Identify algorithm‘s basic operation . Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input, then investigate worst, average, and best case efficiency separately. Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Simplify summation using standard formulas and express C(n) using orders of growth . MATHEMATICAL ANALYSIS OF NON-RECURSIVE ALGORITHMS

143. Aim: Given two n × n matrices A and B, find the time efficiency of the definition-based algorithm for computing their product C = AB. By definition, C is an n × n matrix whose elements are computed as the scalar (dot) products of the rows of matrix A and the columns of matrix B : Example 3: matrix multiplication

144. Algorithm : Example 3: matrix multiplication

145. Example 3: matrix multiplication Analysis: Step 1: Identify Input size ‘n’: The order of the matrix= n Step 2: Identify the basic operation: There are two arithmetical operations in the innermost loop — multiplication and addition —that, in principle, can compete for designation as the algorithm‘s basic operation. Actually, we do not have to choose between them, because on each repetition of the innermost loop each of the two is executed exactly once. So by counting one we automatically count the other. Hence, first we consider multiplication as the basic operation .

146. Example 3: matrix multiplication Analysis: Step 3: Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input then investigate worst, average, and best case efficiency separately. We can observe that the total number of multiplications M(n) executed by the algorithm. depends only on the size of the input matrices, we do not have to investigate the worst-case, average-case, and best-case efficiencies separately.

147. Example 3: matrix multiplication Analysis: Step 4: Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. We can observe that there is just 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               Hence,

148. Example 3: matrix multiplication Analysis: Step 5: Simplify summation using standard formulas and express M (n) using orders of growth . we have,               Consider Now, Standard Formula to be used:

149. Example 3: matrix multiplication Analysis: Total running time:               Suppose if we take into account of addition; A(n) = n 3 Total running time: Hence T(n)  ( n 3 )

150. Example 4: finds the number of binary digits in the binary representation of a positive decimal integer

151. Example 4: finds the number of binary digits in the binary representation of a positive decimal integer Example, Consider n=5, count=1   5>1  True  count=2, n=  5/2  =  2.5  =2 2>1  True  count=3, n=  2/2  =  1  =1 1>1 False Hence count=3 (5=101 in base 2)

152. Example 4: finds the number of binary digits in the binary representation of a positive decimal integer Analysis: Step 1: Identify Input size ‘n’: The positive decimal integer = n Step 2: Identify the basic operation: First, notice that the most frequently executed operation here is not inside the while loop but rather the comparison n > 1 that determines whether the loop‘s body will be executed. Since the number of times the comparison will be executed is larger than the number of repetitions of the loop‘s body by exactly 1.

153. Example 4: finds the number of binary digits in the binary representation of a positive decimal integer Analysis: Step 3: Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input then investigate worst, average, and best case efficiency separately. We can observe that the comparison statement depends only on input size not on type of input , we do not have to investigate the worst-case, average-case, and best-case efficiencies separately.

154. Example 4: finds the number of binary digits in the binary representation of a positive decimal integer Analysis: Step 4: Set up summation for C(n) reflecting the number of times the algorithm‘s basic operation is executed. A more significant feature of this example is the fact that the loop variable takes on only a few values between its lower and upper limits; Therefore, we have to use an alternative way of computing the number of times the body of the loop is executed. Since the value of n is about halved on each repetition of the loop, the answer should be about  log 2 n               

155. Example 4: finds the number of binary digits in the binary representation of a positive decimal integer Analysis: Step 5: Simplify summation using standard formulas and express C (n) using orders of growth . We have, C(n) = number of times the comparison n>1 will be executed We know that the number of times the body of the loop will be executed is  log 2 n  Therefore the number of times the comparison n>1 will be executed will be one larger than the body of the loop Therefore C(n)=  log2 n +1, Hence C(n) ( log 2 n)              

156. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

157. Module I INTRODUCTION

158. Recap…. Mathematical Analysis of Non Recursive Algorithms General Plan Example 3: Matrix Multiplication Example 4: Find number of digits in binary representation of a number Assignment

159. AGENDA Mathematical Analysis of Recursive Algorithms General Plan Example 1: Factorial of a Number Assignment

160. General plan for analyzing efficiency of recursive algorithms:   Decide on parameter n indicating the input size of the algorithm. Identify algorithm‘s basic operation . Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input, then investigate worst, average, and best case efficiency separately. Set up recurrence relation , with an appropriate initial condition , for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Solve the recurrence relation using backward substitution method and express C(n) using orders of growth . MATHEMATICAL ANALYSIS OF RECURSIVE ALGORITHMS

161. Recurrence relations A recurrence relation, T(n), is a recursive function of an integer variable n. Like all recursive functions, it has one or more recursive cases and one or more base cases. Example: The portion of the definition that does not contain T is called the base case of the recurrence relation; the portion that contains T is called the recurrent or recursive case . Recurrence relations are useful for expressing the running times (i.e., the number of basic operations executed) of recursive algorithms

162. Recurrence relations - solving using backward substitution method Recurrence relation is solved using backward substitution method. Inorder to get, a solution in terms of n Example: T(n)=T(n-1)+1 for n>0, T(0)=0 for n=0

163. Example 1: factorial of a number Definition: n ! = 1 * 2 * … *( n- 1) * n for n ≥ 1 and 0! = 1 Recursive definition of n !: F ( n ) = F ( n- 1) * n for n ≥ 1 and F (0) = 1

164. Example 1: factorial of a number Algorithm: Algorithm Factorial(n) //Purpose – Computes n! factorial recursively //Input – A non negative integer n //Output – The value of n! { if (n==0) // base case return 1; else return Factorial(n-1)*n; }

165. Example 1: factorial of a number

166. Example 1: factorial of a number Analysis: Input size: A non negative number = n Basic operation: M ultiplication No best, worst, average cases. Let M( n ) denotes number of multiplications

167. Example 1: factorial of a number Analysis: Solve the recurrence relation using backward substitution method: M(n)=M(n-1)+1 for n>0 and M(0) =0- initial condition 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

168. Example 1: factorial of a number Analysis: Solve the recurrence relation using backward substitution method: M(n) = M(n-3) + 3 … The general formula for the above pattern for some ‘ i ’ is as follows: M(n)= M(n- i ) + i By taking the advantage of the initial condition given i.e., M(0)=0, we equate n- i =0, then i =n

169. Example 1: factorial of a number Analysis: Solve the recurrence relation using backward substitution method: We now substitute i =n in the patterns formula to get the ultimate result of the backward substitutions. M(n)=M(n-n)+n M(n)= M(0) + n M(n) = 0+n M(n)=n    The number of multiplications to compute the factorial of ‘n’ is n where the time complexity is linear.

170. DESIGN AND ANALYSIS OF ALGORITHMS 18CS42

171. Module I INTRODUCTION

172. Recap.. Mathematical Analysis of Recursive Algorithms General Plan Example 1: Factorial of a Number Assignment

173. AGENDA Mathematical Analysis of Recursive Algorithms General Plan Example 2: Tower of Hanoi Problem Assignment

174. General plan for analyzing efficiency of recursive algorithms:   Decide on parameter n indicating the input size of the algorithm. Identify algorithm‘s basic operation . Check whether the number of times the basic operation is executed depends only on the input size n. If it also depends on the type of input, then investigate worst, average, and best case efficiency separately. Set up recurrence relation , with an appropriate initial condition , for C(n) reflecting the number of times the algorithm‘s basic operation is executed. Solve the recurrence relation using backward substitution method and express C(n) using orders of growth . MATHEMATICAL ANALYSIS OF RECURSIVE ALGORITHMS

175. Example 2: Tower of hanoi probelm In this puzzle, we have 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.

176. Example 2: Tower of hanoi probelm The problem has an elegant recursive solution: To move n> 1 disks from peg 1 to peg 3 (with peg 2 as auxiliary): Step 1: We first move recursively n − 1 disks from peg 1 to peg 2 (with peg 3 as auxiliary ). Step 2: Then move the largest disk i.e., nth disk directly from peg 1 to peg 3. Step 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.

177. Example 2: Tower of hanoi probelm

178. Example 2: Tower of hanoi probelm Algorithm TowerHanoi ( n,src,aux,dest ) // Purpose: to Move n disks from source peg to destination peg recursively // Input: ‘n’ disks on source peg in order of size, the largest on the bottom and the smallest on top // Output: ‘n’ disks on destination peg in order of size, the largest on the bottom and the smallest on top { if (n = = 1) then move disk from src to dest else TowerHanoi (n- 1, src , dest , aux) // Step 1 move disk from source to dest // Step 2 Hanoi(disk - 1, aux, src,dest ) // Step 3 }

179. Example 2: Tower of hanoi probelm Analysis: 1.The number of disks n is the obvious choice for the input‘s size indicator. 2.Moving one disk is considered as the algorithm‘s basic operation. 3. Let us consider M(n) indicating the number of moves made for n disks. Clearly , the number of moves M(n) depends on n i.e., input size only 4. W e set the following recurrence equation for M(n): M( n ) = M( n -1)+ 1+M( n -1) for n>1 , Where M(n-1)= number of moves made to transfer (n-1) disks from src to aux(using dest ) 1  One Move to transfer nth disk from src to dest Where M(n-1)= number of moves made to transfer (n-1) disks from aux to dest (using src )

180. Example 2: Tower of hanoi probelm Analysis: 4. W e set the following recurrence equation for M(n): M( n ) = M( n -1)+ 1+M( n -1) for n>1 , The initial condition is: M(1) = 1 for n=1 Now, M(n ) = 2M(n-1) + 1, M(1) = 1 and    

181. Example 2: Tower of hanoi probelm Analysis: 5 . Solve the following recurrence equation for M(n) using backward substitution method: M(n ) = 2M(n-1) + 1 Substitute M(n − 1 ) = 2 M(n − 2 ) + 1 in above eqn M(n)= 2(2M(n-2) + 1) + 1 M(n)= 2 2 *M(n-2 ) + 2 1 + 2 Substitute M(n − 2 ) = 2 M(n − 3 ) + 1 in above eqn   M(n)= 2 2 *( 2M(n-3) + 1) + 2 1 + 2 M(n)= 2 3 *M(n-3 ) + 2 2 + 2 1 + 2 = …

182. Example 2: Tower of hanoi probelm Analysis: 5 . Solve the following recurrence equation for M(n) using backward substitution method: M(n)= 2 3 *M(n-3 ) + 2 2 + 2 1 + 2 = … The general formula for the above pattern for some ‘ i ’ is as follows : M(n )= 2 i *M(n- i ) + 2 i-1 +………..+ 2 2 + 2 1 + 2 By taking the advantage of the initial condition given i.e., M(1)=1, we equate n- i =1, then i =n-1 M(n )= 2 n-1 *M(n-(n-1)) + 2 (n-1)-1 +………..+ 2 2 + 2 1 + 2 M(n )= 2 n-1 *M(n-n+1) + 2 n-2 +………..+ 2 2 + 2 1 + 2 M(n )= 2 n-1 *M(1) + 2 n-2 +………..+ 2 2 + 2 1 + 2 M(n)= 2 n-1 + 2 n-2 +………..+ 2 2 + 2 1 + 2

183. Example 2: Tower of hanoi probelm Analysis: 5 . Solve the following recurrence equation for M(n) using backward substitution method: M(n)= 2 n-1 + 2 n-2 +………..+ 2 2 + 2 1 + 2 This is Geometric Progression Series with commom ratio r=2, a = 2 = 1, with number of terms = n, Wkt , Sum of Geometric Progression Series when r>1 = Hence M(n)= 1(2 n – 1) (2-1) M(n)= 2 n – 1 Hence M(n) ( 2 n )  Exponentially Order of Growth

184. assignment Solve the following recurrence relations: x(n)=x(n-1)+5 for n>1, x(0)=0 f(n) =f(n-1)+2 for n>1 , f(0)=1 x(n)=2x(n-1)+1 for n>1, x(1)=1 F(n ) = F(n-1) + n for n>0, F(0) = 0 X(n) = 3X(n-1) for n>1, X(1) = 4

185. “ ” Thank You! ANY QUESTIONS?