CSE 7350/5350 D.W. Matula

Homework Set # 5 Dynamic Programming Total Points: 50

Due date: 30 Apr 2008

---

1. [Binomial Coefficients]

The recurrence (m choose n) = (m-1 choose n-1) + (m-1 choose n) is the basis for Pascal’s triangle employed in elementary algebra to display the coefficient sequences for (x + y)^k. Show that this recurrence can be utilized to design an algorithm for computing (2n choose n) that uses integer additions as primitive steps and is polynomial in the bit length of the value of (2n choose n). Describe how your implementation can utilize O(n²) or a tighter bound for the bits of storage.

2. [De-merging]
If two sequences a₁, a₂,..., a_m and b₁, b₂,..., b_n are interleaved, we say that the resulting sequence c₁, c₂,..., c_m+n is a shuffle of the first two. For example,

  2,3,3,2,2,5,4,4,5,3,2,3,2,4,5

is a shuffle of 2,3,2,5,4,3,2,4 and 3,2,4,5,2,3,5 since it can be obtained by interleaving those two sequences in this way:

  2,3     2,5,4       3       2,4
       3,2         4,5     2,3       5

You are to give a dynamic programming algorithm for determining whether or not a given sequence is a shuffle of two other given sequences. Your algorithm is to run in time O(mn), where m, n and m + n are the lengths of the three sequences. You should carefully describe each step of the process, e.g. this should include certain definitions, the principal recurrence relations, the table setup, the order in which the table contents are computed, and the computation storage window utilized.

3. [Shortest Path Count]

a) Describe a dynamic program that determines the distance matrix and counts the number of distinct shortest paths between each pair of vertices of a graph that runs in time O(|V||E|) given the adjacency list for the graph.

b) Apply your algorithm to the 16 vertex graph illustrated in the dual MAS walkthrough in the Maximum Adjacency Search Project Description on the homepage. (If done by hand show only the 4x16 portion for rows a,b,c,d).

c) (5 bonus points) Implement your algorithm and apply it to Benchmark Graphs 1-5 from the Projects section of the homepage.

4. [Monotonic Subsequences]
Given the sequence a(1), a(2),..., a(n), of real numbers, consider the problem of determining the length k of a longest monotonically increasing subsequence  a(i₁) < a(i₂)  <...< a(i_k) where i₁ < i₂ <...< i_k.

Using the paradigm of dynamic programming give the best algorithm you can for determining a longest monotonically increasing subsequence. Describe the algorithm and analyze its time and space complexity. (See text p. 319, 16.3-5, 6). Discuss the storage space required to solve for the variable k compared to obtaining a longest sequence.

Apply your algorithm from (a) to the following data, forwards and backwards:

54, 76, 30, 44, 74, 15, 78, 67, 36, 46, 11, 77, 42, 49, 82, 73, 80,
66, 52, 58, 22, 68, 35, 40, 24, 13, 55, 27, 39, 16, 43, 93, 61, 53,
90, 45, 70, 41, 56, 79, 14, 69, 38, 65, 63, 18, 57, 26, 59, 47.

5. [Randomized Dynamic Subsequence Selection]

a) Consider the dynamic ascending subsequence selection problem as illustrated in the SOLO game discussed in class.

Write a program to compute the expected value of the 52 card game. Tabulate the solution of the n card game and the ''take point'' for n=2^k, where 1 <= k <= 18. Estimate functions describing the general solution for the value and take point for arbitrary n.

b) [Time/space/accuracy of SOLO recurrence solution] (5 bonus points)

Describe an algorithm and data structure design that allows for computing the expected value of the n card SOLO game in time O(n).

How little space is sufficient for computing the value of the n card game?

What is the effect of numerical accuracy limitation in computing the “take point”? Compare single vs. double precision computation of the recurrence, and discuss or analyze.