CS575 Assignment 3

Description

Objective:

• Design and analyze an algorithm using dynamic programming strategy
• Enhance the concept of heap for sorting.

There are two parts in this assignment: (A) Theory part and (B) programming part

[Part A] Theory [77%]:

1. [10%] Given the following array:

1. 1. [2%] Show the essential complete binary tree for the following array:

1. 1. [4%] Convert the essential complete binary tree into a min heap using the fast-make-heap method. Draw the essential complete binary tree after each siftDown.
   2. [4%] Using the max-heap sorting algorithm to sort the above sequence in the non-decreasing order. Show the heap after the value “9” has been moved to the sorted sequence.

2. [10%] Find the longest common subsequence for the strings S=α β α µ £ α α  β, and T = £ µ α µ β µ £ £ α µ β. Show the table with the lengths and arrows.
3. [10%] Find the shortest distance between all pairs of nodes in the following graph. Show the matrices D⁰, D¹, …, D⁴ and P⁰, P¹, …, P⁴

(4) (5%)  Does Floyd’s algorithm always yield correct results? Use following graph to justify your answer.

 [10%] If we want to design an algorithm to merge two heaps of sizes n1 and n2. Assume that heap 1 is stored in bt1[1,…,n1] and heap 2 is stored in bt2[1,…,n2]. Assume that n2 >= n1. The two heaps do not overlap.

Is the following solution correct?

If yes, give the upper bound of the time complexity.

If not, give an example where it is wrong, describe a correct solution, and give the upper bound of the time complexity.

Copy the larger heap at the end of the smaller one. After the copy bt1 contains all n1 + n2 values. Now apply siftDown to all tree nodes from n1 down to 1.

for (i=1; i <=n2, i++)

bt1[n1+i] = bt2[i]

last = n1 + n2

for (i=n1; i > 0, i=i-1)

siftDown(bt1, i)

1. [6%] Compute the binomial value of  using dynamic programming B table. [4%] Can you make a small B table (less than 6 columns) to obtain the solution.

1.  [12%]

Design a dynamic programming algorithm to solve the sum of subsets problem:

There are n positive integers,  and a positive integer sum S.  Is there a subset A of the n integers such that the sum of the integers in the subset is S, ()? If there is such a subset the output of the program is true otherwise it is false.

Example:  In this case the output is true since p₂+ p₃ = 16.

Example:  In this case there is no solution, and the output is false.

The problem can be solved with dynamic programming.

A Boolean matrix B with rows 0 to n and columns 0 to S is generated. For the examples above the matrix has rows 0 to 3, and columns 0 to 16.

B[i, s] is true if a subset of the first i integers sums to s, otherwise it is false.

The solution to the original problem is true if B[n, S]= true, otherwise it is false.

(1) [5%] Write the recurrence relation for the solution.

• [4%] Write pseudo code to compute B.
• [3%] Apply dynamic programming to the following problem:  Show your matrix B.  Each element of B has the value true or false. Also, use arrows to show the matrix elements that were ordered, or used.

8. (5%) Show that the number of distinct binary search tree b(n) that can be constructed for a set of n orderable keys satisfies the recurrence relation:

9. (5%) Constructing the optimal binary search tree, given

Show the dynamic programming tables of each step.

10. (Optional: Extra points 10%)

Suppose there is an apartment available for rent for a year. There are 6 requesters who want to rent the apartment for 6 different periods of time with 6 different offers:

Requester 1:  starting January 1^st for 3 months, and would like to pay $2k;

Requester 2:  starting February 1^st for 5 months, and would like to pay $4k;

Requester 3:  starting May 1^st for 5 months, and would like to pay $4k;

Requester 4:  starting April 1^st for 7 months, and would like to pay $7k;

Requester 5:  starting October 1^st for 2 months, and would like to pay $2k;

Requester 6:  starting November 1^st for 2 months, and would like to pay $1k;

Since the apartment cannot be rented for more than one requester at a same period of time, design a dynamic programming algorithm to select the subset of requesters in order to maximize the sum of rentals (values).

• Write the recurrence relation for the solution;
• Show the time complexity of your algorithm;
• Using the above instance, show the dynamic programming table of your solution from the 6 requesters;

(Hint: The problem can be generalized by j requesters (j=1, 2, …, n), and each requester would like to pay v(j) dollars for t(j) period of time. )

[Part B] Programming [28%]:

1. [18%] Given a following map, find the shortest path from New York City to Toronto using the dynamic programming approach. (The numbers shown on the map are the distances in miles between cities).

2. (10%) Find the longest common sequence of two strings by the dynamic programming algorithm. Test your implementation with the following two strings: 6541254939322816220209974565477289648317, 3142522751761601737419090933147067701840

Output:  length of LCS and the actual LCS.

3. (Optional: Extra 10%) Design a three-string LCS algorithm for finding the longest common subsequence (LCS) of three strings. Indicate the time complexity of your algorithm. Test your algorithm using following three strings:

String 1: 6541254939322816220209974565477289648317

String 2: 3142522751761601737419090933147067701840

String 3: 2807030561290354259513570160162463275171

Output: length of LCS and the actual LCS

Hint:

1. Extend the recurrence equation from two strings to three strings (e.g., length-LCS(i, j, k)).

Note 1:

For Part B, submit one zip file of your code package including your code, makefile, and write-up (.doc).  The title is:

firstname_lastname_programming_language_used.tar.gz or
firstname_lastname_programming_language_used.zip