CSE 551: Homework 4 (50 points)
Submit your answers in a single PDF file. As
usual, we will grade any two problems. Hence, please answer all the questions.
1. Given n integers, is there a way to partition the integers into two disjoint
subsets so that the sums of the integers in each of the two subsets are equal?
More formally, given {s1, s2, ....., sn} is there a subset I of {1, 2, ..., n} such that,
P
i∈I
si =
P
i /∈I
si
Give a dynamic programming algorithm for this problem. Estimate the run
time of your algorithm.
2. The Longest Common Subsequence (LCS) problem discussed in class finds
one LCS of two strings. Develop a dynamic programming algorithm to find all
such LCSs. (LCS algorithm is available on slide set Dynamic Programming 1)
3. Given two strings, develop a dynamic programming algorithm to compute
the minimum number of insertions/deletions/substitutions of characters needed
to transform the first string into the second.
4. Develop a dynamic programming algorithm to compute the largest independent set of a tree.
1
