Homework submission A pdf copy of your own solutions to Problems 1–3 should be submitted at SUCourse.
Problem 1 Consider a variation of the Longest Common Subsequence (LCS) prob-lem where k (k 2) sequences are given as input and the goal is to find their LCS.
How would you modify the recursive formula and the top-down LCS algo-rithm that we have studied in class for two sequences, to find an LCS for k se-quences? Please explain.
What is the asymptotic time complexity of your algorithm? Please discuss: is it expected or a surprise?
Problem 2 Given a tree (V; E), design an algorithm using dynamic programming to find a minimum cardinality set X V of vertices such that the following holds: for every edge fu; vg 2 E, u 2 X or v 2 X.
Please describe how you design your algorithm (i.e., optimal substructures, recursive solution, construction of solution, etc.), and include a pseudocode of your algorithm.
Analyze the asymptotic time complexity of your algorithm.
How does the computational complexity of this problem change, if a graph is given as an input instead of a tree? Please discuss.
Problem 3 (a) Define the Minimum Leaf Spanning Tree (MLST) problem: What are the input and the output?
Describe a real-world application of MLST.
Prove that MLST is NP-complete.
1
