Description
be submitted at SUCourse.
Problem 1 Consider a variation of the Longest Common Subsequence (LCS) problem 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 algorithm that we have studied in class for two sequences, to find an LCS for k sequences? Please explain.
- What is the asymptotic time complexity of your algorithm? Please discuss: isit 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 {u,v}∈ E, u ∈ X or v ∈ 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 isgiven 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
