HW6

Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)

(1) Please show ALL of your work (Step by Step).

(2) Provide as many details as possible for the designed algorithms (exact pseudocode) from now on. 

1. [Written 10pt] Solve the instance 5, 1, 2, 10, 6 of the coin-row problem. Show your step by creating the Table similar to Figure 8.1. 

2. [Written 10pt] Apply the dynamic programming algorithm to find all the solutions to the change-making problem for the denominations 1, 3, 5 and the amount n=9. Show your step by creating the Table similar to Figure 8.2. 

3. [Written and Coding 10pt] Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that can be obtained by cutting a rod of n units long into integer-length pieces if the sale price of a piece i units long is pi for i=1,2,...,n. What are the time and space efficiencies of your algorithm? (Hints: Look at the coin-change problem.)

4. [Written and Coding 10pt] A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard. Find the number of shortest paths by which a rook can move from one corner of a chessboard 8 by 8 to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares. Solve the problem using a dynamic programming algorithm. (Hints: Look at the coin-collection problem.)

5. [Written and Coding 10pt] Some positive integers are arranged in an equilateral triangle with n numbers in its base like the one shown in the figure below for n = 4. The problem is to find the largest sum in a descent from the triangle apex to its base through a sequence of adjacent numbers (shown in the figure by the circles). Design a dynamic programming algorithm for this problem and indicate its time efficiency.

You could assume each row is represented by a matrix of n by n (e.g., A = [2 0 0 0; 5 4 0 0; 1 4 7 0; 8 6 9 6]). 

6. [Written and Coding 10pt] Design an efficient algorithm for computing the binomial coefficient C(n, k) that uses no multiplications. What are the time and space efficiencies of your algorithm? (Hint: C(n, k) = C(n-1, k-1) + C(n-1, k). )

7. [Written 10pt]  Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack problem (see below).

8. [Written and Coding 10pt] Design a dynamic programming algorithm for the knapsack problem. 

9. [Written 10pt] Apply Warshall’s algorithm to find the transitive closure of the digraph a -> b -> c -> d. (Show all of the matrices.)

10. [Written 10pt] Explain why the time efficiency class of Warshall’s algorithm is inferior to that of the traversal-based algorithm for sparse graphs (where m \in O(n)) represented by their adjacency lists.

11. [Written 10pt] Explain how Warshall’s algorithm can be used to determine whether a given digraph is a dag (directed acyclic graph). Is it a good algorithm for this problem?

12. [Written 10pt] In the game of Jack Straws, a number of plastic or wooden “straws” are dumped on the table and players try to remove them one by one without disturbing the other straws. Here, we are only concerned with whether various pairs of straws are connected by a path of touching straws. Given a list of the endpoints for n > 1 straws (as if they were dumped on a large piece of graph paper), determine all the pairs of straws that are connected. Note that touching is connecting, but also that two straws can be connected indirectly via other connected straws. 

13. [Written 10pt] Solve the all-pairs shortest-path problem for the digraph with the following weight matrix.