# CIS 675: Algorthms – Spring 2019 Homework 8

Abbreviations

• DPV = Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.
• PG = Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

• Chapters 6 and 7 of DPV

#### Notation

• For sets and , we define to be the set .

For example, .

#### Problems

1. (24 points) PG Problems 392, 393, 394. Each part is 8 points.

2. (26 points) DPV, Problem 6.11.

• Compute the length of the longest common subsequence of and .
• since in those cases one of the strings is empty.
• To compute (when and ) you may want to consider , , , and whether .
• Point Breakdown:
• 10 points for the recursive equation for .
• 8 points for justifying the above equation
• 8 points for the -time pseudocode for building the table.
3. (26 points) DPV, Problem 6.18.
• Compute a boolean value for and where indicates that it is possible to make change for using demoninations 1 through i.
• for .
• when .
• The key problem is figuring out the general recursion for .
• Point Breakdown:
• 10 points for the recursive equation for .
• 8 points for justifying the above equation
• 8 points for the -time pseudocode for building the table.
4. (24 points) DPV. Problem 6.21.
1. (8 points) Show that if is an independent set, then is a vertex cover.
2. (8 points) Show that if is a vertex cover, then is an independent set.
3. (8 points) Show how to use the algorithm of section 6.7 to solve this problem.