This chapter presents the following content: Introduction to algorithm analysis, different functions, function’s growth rate, three problems related to algorithm running time, maximum contiguous subsequence sum problem. | Lecture 16 Recap Introduction to Algorithm Analysis Different Functions Function’s Growth Rate Three Problems Related to Algorithm Running Time Find Minimum in an Array Find Closest Point in a Plane Find Collinear Points in a Plane Maximum Contiguous Subsequence Sum Problem Theorem Proof Place the following N + 2 balls in a box: N balls numbered 1 through N, one unnumbered red ball and one unnumbered blue ball. Remove three balls from the box. If a red ball is drawn, number it as the lowest of the numbered balls drawn. If a blue ball is drawn , number it as highest of the numbered balls drawn. Note that if you draw both a red and a blue ball, then the effect is to have three balls identical numbered. Order the three balls. Each such order corresponds to a triplet solution to the equation in Theorem . The number of possible orders is the number of distinct ways to draw three balls without replacement from collection of N + 2 balls. This problem is similar to that of selecting three points from a group of N so we immediately obtain the stated result. Conclusion of O() Algorithm Improved O() Algorithm 1 // Quadratic maximum contiguous subsequence sum algorithm. 2 // seqStart and seqEnd represent the actual best sequence. 3 template 4 Comparable maxSubsequenceSum( const vector & a, 5 int & seqstart, int & seqEnd ) 6 ( 7 int n = ( ); 8 Comparable maxSum = 0; 9 10 for( int i = 0; i maxSum ) 18 { 19 maxSum = thisSum; 20 seqStart = i; 21 seqEnd = j ; 22 } 23 } 24 } 25 26 return maxSum; 27 } Linear Algorithm To move from a quadratic algorithm to a linear algorithm, we need to remove yet another loop The problem is that the quadratic algorithm is still an exhaustive search; that is, we are trying all possible subsequences The only difference between the quadratic and cubic algorithms is that the cost of | Lecture 16 Recap Introduction to Algorithm Analysis Different Functions Function’s Growth Rate Three Problems Related to Algorithm Running Time Find Minimum in an Array Find Closest Point in a Plane Find Collinear Points in a Plane Maximum Contiguous Subsequence Sum Problem Theorem Proof Place the following N + 2 balls in a box: N balls numbered 1 through N, one unnumbered red ball and one unnumbered blue ball. Remove three balls from the box. If a red ball is drawn, number it as the lowest of the numbered balls drawn. If a blue ball is drawn , number it as highest of the numbered balls drawn. Note that if you draw both a red and a blue ball, then the effect is to have three balls identical numbered. Order the three balls. Each such order corresponds to a triplet solution to the equation in Theorem . The number of possible orders is the number of distinct ways to draw three balls without replacement from collection of N + 2 balls. This problem is similar to that of selecting
