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

For sets and , we define to be the set .

For example, .

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

(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.

- (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.

- Compute a boolean value for and where indicates that it is possible to make change for using demoninations 1 through
- (24 points) DPV. Problem 6.21.
- (8 points) Show that if is an independent set, then is a vertex cover.
- (8 points) Show that if is a vertex cover, then is an independent set.
- (8 points) Show how to use the algorithm of section 6.7 to solve this problem.