## Exercises #### Section 3.1 1. Establish Equality 3.1 given in this section. 2. Use induction on *n* to show that the divide-and-conquer algorithm for the Binomial Coefficient problem ([Algorithm 3.1](LiB0025.html#258)), based on Equality 3.1, computes 2  − 1 terms to determine . 3. Implement both algorithms for the Binomial Coefficient problem ([Algorithm 3.1](LiB0025.html#258) and [Algorithm 3.2](LiB0025.html#263)) on your system and study their performances using different problem instances. 4. Modify [Algorithm 3.2](LiB0025.html#263) (Binomial Coefficient Using Dynamic Programming) so that it uses only a one-dimensional array indexed from 0 to *k*. #### Section 3.2 1. Use Floyd's algorithm for the Shortest Paths problem 2 ([Algorithm 3.4](LiB0026.html#280)) to construct the matrix *D*, which contains the lengths of the shortest paths, and the matrix *P*, which contains the highest indices of the intermediate vertices on the shortest paths, for the following graph. Show the actions step by step. [](figu133_3_0.jpg) 2. Use the Print Shortest Path algorithm ([Algorithm 3.5](LiB0026.html#283)) to find the shortest path from vertex *v*7 to vertex *v*3, in the graph of Exercise 5, using the matrix *P* found in that exercise. Show the actions step by step. 3. Analyze the Print Shortest Path algorithm ([Algorithm 3.5](LiB0026.html#283)) and show that it has a linear time complexity. 4. Implement Floyd's algorithm for the Shortest Paths problem 2 ([Algorithm 3.4](LiB0026.html#280)) on your system, and study its performance using different graphs. 5. Can Floyd's algorithm for the Shortest Paths problem 2 ([Algorithm 3.4](LiB0026.html#280)) be modified to give just the shortest path from a given vertex to another specified vertex in a graph? Justify your answer. 6. Can Floyd's algorithm for the Shortest Paths problem 2 ([Algorithm 3.4](LiB0026.html#280)) be used to find the shortest paths in a graph with some negative weights? Justify your answer. #### Section 3.3 1. Find an optimization problem in which the principle of optimality does not apply and therefore that the optimal solution cannot be obtained using dynamic programming. Justify your answer. #### Section 3.4 1. Find the optimal order, and its cost, for evaluating the product *A*1 × *A*2 × *A*3 × *A*4 × *A*5, where  2. Implement the Minimum Multiplications algorithm ([Algorithm 3.6](LiB0028.html#301)) and the Print Optimal Order algorithm ([Algorithm 3.7](LiB0028.html#306)) on your system, and study their performances using different problem instances. 3. Show that a divide-and-conquer algorithm based on Equality 3.5 has an exponential time complexity. 4. Establish the equality  This is used in the every-case time complexity analysis of [Algorithm 3.6](LiB0028.html#301). 5. Show that to fully parenthesize an expression having *n* matrices we need *n* − 1 pairs of parentheses. 6. Analyze [Algorithm 3.7](LiB0028.html#306) and show that it has a linear time complexity. 7. Write an efficient algorithm that will find an optimal order for multiplying *n* matrices *A*1 x *A*2 x … x *An*, where the dimension of each matrix is 1 × 1, 1 × *d, d* × 1, or *d* × *d* for some positive integer *d.* Analyze your algorithm and show the results using order notation. #### Section 3.5 1. How many different binary search trees can be constructed using six distinct keys? 2. Create the optimal binary search tree for the following items, where the probability occurrence of each word is given in parentheses: CASE (.05), ELSE (.15), END (.05), IF (.35), OF (.05), THEN (.35). 3. Find an efficient way to compute , which is used in the Optimal Binary Search Tree algorithm ([Algorithm 3.9](LiB0029.html#322)). 4. Implement the Optimal Binary Search Tree algorithm ([Algorithm 3.9](LiB0029.html#322)) and the Build Optimal Binary Search Tree algorithm ([Algorithm 3.10](LiB0029.html#325)) on your system, and study their performances using different problem instances. 5. Analyze [Algorithm 3.10](LiB0029.html#325), and show its time complexity using order notation. 6. Generalize the Optimal Binary Search Tree algorithm ([Algorithm 3.9](LiB0029.html#322)) to the case in which the search key may not be in the tree. That is, you should let *q**i*, in which *i* = 0, 1, 2, …, *n*, be the probability that a missing search key can be situated between *Key**i* and *Key**i*+1. Analyze your generalized algorithm and show the results using order notation. 7. Show that a divide-and-conquer algorithm based on Equality 3.6 has an exponential time complexity. #### Section 3.6 1. Find an optimal circuit for the weighted, direct graph represented by the following matrix *W.* Show the actions step by step.  2. Write a more detailed version of the Dynamic Programming algorithm for the Traveling Salesperson problem ([Algorithm 3.11](LiB0030.html#340)). 3. Implement your detailed version of [Algorithm 3.11](LiB0030.html#340) from Exercise 27 on your system and study its performance using several problem instances. #### Additional Exercises 1. Like algorithms for computing the *n*th Fibonacci term (see Exercise 34 in [Chapter 1](LiB0008.html#16)), the input size in [Algorithm 3.2](LiB0025.html#263) (Binomial Coefficient Using Dynamic Programming) is the number of symbols it takes to encode the numbers *n* and *k.* Analyze the algorithm in terms of its input size. 2. Determine the number of possible orders for multiplying *n* matrices *A*1, *A*2, …, *An.* 3. Show that the number of binary search trees with *n* keys is given by the formula  4. Can you develop a quadratic-time algorithm for the Optimal Binary Search Tree problem ([Algorithm 3.9](LiB0029.html#322))? 5. Use the dynamic programming approach to write an algorithm to find the maximum sum in any contiguous sublist of a given list of *n* real values. Analyze your algorithm, and show the results using order notation. 6. Let us consider two sequences of characters *S*1 and *S*2. For example, we could have *S*1− A$CMA\*MN and *S*2 = AXMC4ANB. Assuming that a subsequence of a sequence can be constructed by deleting any number of characters from any positions, use the dynamic programming approach to create an algorithm that finds the longest common subsequence of *S*1 and *S*2. This algorithm returns the maximum-length common subsequence of each sequence.