CSC $204-$ Algorithm Design and Analysis

Homework $6-$ Dynamic Programming, NP$-$Completeness

Name: $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$1.$ Dynamic Programming $(31$ points$)$

$($a$)$ Consider the rod$-$cutting problem discussed in lecture. Suppose we are

given the following price$/$length table below. Fill out the table for the maximum

revenue for each subproblem? $(8$ points$)$

$($b$)$ Consider the longest common subsequence problem. Suppose we are

given the following sequences below. Fill out the dynamic programming table

below? $(8$ points$)$

rn

$123456789$

$1458812141922$

length i

price pi

$123456789$

rn

length i

X $=$ atatcg Y $=$ ggatgc

g g a t g c

a

t

a

t

c

g

$($c$)$ What is the length of the longest common subsequence from the table

above? $(8$ points$)$

$($d$)$ What is the longest common subsequence? $(7$ points$)$

$2.$ NP$-$Completeness $(24$ points$)$

Your professor at Hofstra comes to you one day claiming that they have finally solved

an NP$-$Complete problem. They tell you the following two statements.

$(1)$ The $3-$Coloring problem is solvable in worst case time $.$

$(2)$ In the worst case, there does not exist an algorithm to solve $3-$Coloring faster than

$.$

Assuming that your professor is correct, for each of the following statements below,

state whether the statement is true or false, and then write a few sentences to justify

your answer.

$($i$)$ All NP$-$Complete problems are solvable in polynomial time.

$($ii$)$ All problems in NP are solvable in polynomial time.

$($iii$)$ All NP$-$Hard problems are solvable in polynomial time.

O$($n $10)$

$\backslash$Omega $($n $8)$

$($iv$)$ All NP$-$Complete problems are solvable in time.

$($v$)$ There exists no NP$-$complete problem that can be solved faster than in the

worst case.

$($vi$)$ P $=$ NP