Transcript Newass4

Assignment 4. (New) I just find that there are solutions on
website to some questions of the assignment 4. So, I
modified the questions a little bit. Please complete the
new questions. The new questions are modifications of
the old questions and you can easily modify your solution if
you really understand the old questions.
Due on Dec 11, 2007 (Tuesday of week 15). Drop it in Mail Box 63)
This time, Professor Yao and I can explain the questions, but
we will NOT tell you how to solve the problems.
Question 1. (30 points) Give a polynomial time algorithm to
find the longest non-increasing subsequence of a sequence
of n numbers. Here each number may appear more than
once. Can you give a linear space algorithm?
Example: Consider sequence 1,8, 8,2,9, 2, 3,10, 5,4, 5. Both
subsequences 8854 and 8855 are non-increasing
subsequences.
1
Assignment 4.
Question 2. (35 points) Suppose that there are n sequences s1, s2, …, sn . Every
sequence si is a permutation of the m numbers, 1, 2, 3, …, m. That is the
length of each sequence is m and every number appears exactly once in
each si.
Design a polynomial time algorithm to compute the LCS of the n sequences
such that no two consecutive numbers in the LCS are both odd numbers.
What is the time complexity of your algorithm?
Question 3. (35 points) Let T be a rooted binary tree, where each internal
node in the tree has two children and every node (except the root) in T has a
parent. Each leaf in the tree is assigned a letter in ={A, C, G, T}. Consider
an edge e in T. Assume that every end of e is assigned a letter. The cost of e
is 0 if the two letters are identical and the cost is 1 if the two letters are not
identical. The problem here is to assign a letter in  to each internal node of
T such that the cost of the tree is minimized, where the cost of the tree is the
total cost of all edges in the tree. Design a polynomial-time dynamic
programming algorithm to solve the problem.
2