Description
1. A string is a palindrome if it is the same read left to right or right to left, e.g. ababa. The longest
palindrome subsequence of a string x is its longest subsequence (of not necessarily consecutive symbols)
that is a palindrome.
We want an algorithm to determine in time O(|x|
2
) the length of the longest
palindrome sub-sequence of a string x.
(a) A cheap solution is, let y be the reverse of x, and apply the standard Longest Common Subsequence
(LCS) algorithm to x and y. This approach is numerically correct, but flawed, since the character
locations for a LCS in x and y does not have to reference the same sequence of physical characters.
Suppose x is ZABZA, what are the LCS for x and its reverse? How many are they? Are they all
palindrome?
(b) A better way is to design a new DP algorithm. Let l(i, j) be the length of longest palindrome in
x[i, . . . , j], please write the recurrence equations, including the initial conditions. Please analyze
the time and space complexity.
2. (Maximum Independent Set in Trees1
) In an undirected graph G = (V, E), an independent set
S is a subset of the vertex set V that contains no edge inside it, i.e. S is an independent set on G
⇔ S ⊆ V, ∀u, v ∈ S → {u, v} ∈/ E.
Given a rooted tree T(V, E) with root node r, find an independent set of the maximum size. Briefly
describe why your algorithm is correct.
3. You are given a set of n intervals on a line: (a1, b1], . . . ,(an, bn]. Design a greedy algorithm to select
minimum number of intervals whose union is the same as the union of all intervals. Please also analyze
the time complexity, and prove the correctness by showing the two properties.
4. Suppose you have an unrestricted supply of pennies, nickels, dimes, and quarters. You wish to give your
friend n cents using a minimum number of coins.
You need to:
(a) Describe a greedy strategy to solve this problem, and analyze its time complexity;
(b) Prove the correctness of your algorithm.
1Finding maximum-sized independent sets in general graphs is NP-complete. So we will focus on tree cases.
