# 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 $U$ and $V$, we define $(U-V)$ to be the set $\{\; x \;:\; x\in U \;\&\; x\notin V\;\}$.

For example, $(\{\,1,2,3,4,5\,\}-\{\,1,3,5\,\}) = \{\,2,4\,\}$.

#### Problems

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

2. (26 points) DPV, Problem 6.11.

• Compute $L[i,j] =$ the length of the longest common subsequence of $x_1 x_2 \dots x_i$ and $y_1 y_2 \dots y_j$.
• $L[0,j] = L[i,0] = 0$ since in those cases one of the strings is empty.
• To compute $L[i,j]$ (when $i>0$ and $j>0$) you may want to consider $L[i-1,j-1]$, $L[i-1,j]$, $L[i,j-1]$, and whether $x_i=y_j$.
• Point Breakdown:
• 10 points for the recursive equation for $L[i,j]$.
• 8 points for justifying the above equation
• 8 points for the $\Theta(m\cdot n)$-time pseudocode for building the $L$ table.
3. (26 points) DPV, Problem 6.18.
• Compute a boolean value $C[i,u]$ for $i=1,\dots,n$ and $u=0,\dots,v$ where $C[i,u]$ indicates that it is possible to make change for $u$ using demoninations 1 through i.
• $C[i,0] = \mathsf{true}$ for $i=0,\dots,n$.
• $C[0,u] = \mathsf{false}$ when $u=1,\dots,v$.
• The key problem is figuring out the general recursion for $C[i,u]$.
• Point Breakdown:
• 10 points for the recursive equation for $C[i,j]$.
• 8 points for justifying the above equation
• 8 points for the $\Theta(n\cdot u)$-time pseudocode for building the $C$ table.
4. (24 points) DPV. Problem 6.21.
1. (8 points) Show that if $U$ is an independent set, then $(V-U)$ is a vertex cover.
2. (8 points) Show that if $U$ is a vertex cover, then $(V-U)$ is an independent set.
3. (8 points) Show how to use the algorithm of section 6.7 to solve this problem.