Dynamic Programming and Greedy Algorithms_Assignment 3

This assignment covers Chapters 15 (Dynamic Programming) and 16 (Greedy Algorithms) of the text [100 marks total].
1. Minimum-Sum Descent. [20 marks total] Positive integers are arranged in an equilateral triangle with n numbers in its base such as the one shown in Figure 1 for n = 4. The problem is to find the smallest sum in a descent from the apex of the triangle to its base through a sequence of adjacent numbers (shown in the figure by the circles).
(a) Give C/C++ pseudocode for a dynamic programming algorithm to solve this problem. (b) Apply your algorithm to the triangle in Figure 1. (c) What is the time and space efficiency of your algorithm?
7. Shortest-path counting 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 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
(a) by a dynamic programming algorithm.
(b) by using elementary combinatorics.
8. Minimum-sum descent Some positive integers are arranged in an equilateral triangle with q numbers in its base like the one shown in the figure below for q =4. The problem is to find the smallest 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.
9. Binomial coefficient Design an efficient algorithm for computing the binomial coefficient F(qn) that uses no multiplications. What are the time and space efficiencies of your algorithm? 10. Longest path in a dag a. Design an efficient algorithm for finding the length of a longest path in a dag. (This problem is important both as a prototype of many other dynamic programming applications and in its own right because it determines the minimal time needed for completing a project comprising precedence-constrained tasks.)
B b. Show how to reduce the coin-row problem discussed in this section to the problem of finding a longest path in a dag. 11. IMaximum square submatrix Given an p×q boolean matrix Efind its largest square submatrix whose elements are all zeros. Design a dynamic programming algorithm and indicate its time efficiency. (The algorithm may be useful for, say, finding the largest free square area on a computer screen or for selecting a construction site.)
2
Figure 1: Equilateral triangle with n = 4 numbers in its base.
2. World Series Odds. [20 marks total] Consider two teams, A and B, playing a series of games until one of the teams wins n games. Assume that the probability of A winning a game is the same for each game and equal to p and the probability of A losing a game is q = 1−p. (Hence, there are no ties.) Let P(i,j) be the probability of A winning the series if A needs i more games to win the series and B needs j more games to win the series.
(a) Set up a recurrence relation for P(i,j) that can be used by a dynamic programming algorithm. Hint: In the situation where teams A and B need i and j games, respectively, to win the series, consider the result of team A winning the game and the result of team A losing the game. (b) Find the probability of team A winning a seven-game series if the probability of it winning a game is 0.4. Hint: Set up a table with five rows (0 ≤ i ≤ 4) and five columns (0 ≤ j ≤ 4) and fill it by using the recurrence derived in part (a). (c) Write C/C++ pseudocode for a dynamic programming algorithm to solve this problem and determine its time and space efficiencies. Hint: Your pseudocode should be guided by the recurrence you set up in part (a).
3. Knapsack Problem. [20 marks] Given n items of known weights w1,...,wn and values v1,...,vn and a knapsack of capacity W, the knapsack problem is to find the most valuable subset of the items that fit into the knapsack.
(a) Write C/C++ pseudocode for a bottom-up dynamic programming algorithm for the knapsack problem. (b) Apply your algorithm in part (a) to the following instance of the knapsack problem with a knapsack of capacity W = 6:
1
Item Weight Value 1 3 $25 2 2 $20 3 1 $15 4 4 $40 5 5 $50
(c) How many different optimal subsets does the instance of part (a) have? (d) In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for an instance of the knapsack problem?
4. The Bridge Crossing Problem. [20 marks total] There are n 1 people who want to cross a rickety bridge; they all begin on the same side. It is night, and they have one flashlight among them. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. The crossing times in minutes of the n people are t1,t2,...,tn, respectively. A pair must walk together at the pace of the slower person. The problem is to minimize the bridge crossing time.
(a) Give C/C++ pseudocode for a greedy algorithm to get all n people to cross the bridge, and determine how long it will take to cross the bridge by using your algorithm. (b) Apply your algorithm to an instance of the problem with n = 4 people, with crossing times of t1 = 1 minute, t2 = 2 minutes, t3 = 5 minutes, and t4 = 10 minutes, respectively. (c) Does your algorithm yield a minimum crossing time for every instance of the problem? If it does then prove it; if it does not, find a small counterexample.
5. Scheduling Video Streams. [20 marks] Suppose n video streams need to be sent, one after another, over a communication link. Stream i consists of a total of bi bits to be sent, at a constant rate, over a period of ti seconds. Two streams cannot be sent at the same time; instead, a schedule must be determined, i.e., an order in which to send them. No matter the order, there cannot be any delays between the end of one stream and the start of the next. Assume the schedule starts at time zero (and ends at timePn i=1 ti, no matter the schedule), and that all the values bi and ti are positive integers. In addition, the link imposes the following constraint, using a fixed parameter r: For each natural number t 0, the total number of bits sent over the time interval from 0 to t cannot exceed rt. A schedule is valid if it satisfies the constraint imposed by the link. Given a set of n streams, each specified by its number of bits bi and its time duration ti, as well as the link parameter r, the problem is to determine whether a valid schedule exists. Example: Suppose there are n = 3 streams with (b1,t1) = (2000,1), (b2,t2) = (6000,2), and (b3,t3) = (2000,1), and the link parameter is r = 5000. Then the schedule that runs the streams in the order 1,2,3 is valid because the constraint is satisfied: At t = 1: The whole first stream is sent; 2000 < 5000·1. At t = 2: Half of the second stream is sent; 2000 + 3000 < 5000·2. Similarly for t = 3 and t = 4. (a) Claim: There exists a valid schedule if and only if each stream i satisfies bi ≤ rti. Prove this claim true or false. (b) Give C/C++ pseudocode for a greedy algorithm that takes a set of n streams, each specified by its number of bits bi and its time duration ti, as well as the link parameter r, and determines whether a valid schedule exists. (c) Clearly explain what makes your algorithm greedy. (d) What is the worst case running time of your algorithm?