Transcript Notes for Lecture 11

Pseudo-polynomial time algorithm
(The concept and the terminology are important)
Partition Problem:
Input: Finite set A=(a1, a2, …, an} and a size s(a) (integer) for each
aA.
Question: Is there a subset A’A such that
 a A’ s(a) =  a A –A’ s(a)?
Theorem: Partition problem is NP-complete (Karp, 1972).
An dynamic algorithm:
For in and j 0.5  a A s(a) , define t(i, j) to be true
if and only if there is a subset Ai of {a1, a2, …, ai} such that
 a Ai s(a)=j.
Formula:
T(i,j)=true if and only if t(i-1, j)=true or t(i-1, j-s(ai))=true.
1
Example
i j 0
1 T
2 T
3 T
4 T
5 T
1
T
T
T
T
T
2
F
F
F
F
F
3
F
F
F
T
T
4
F
F
F
T
T
5
F
F
T
T
T
6
F
F
T
T
T
7
F
F
F
F
F
8
F
F
F
T
T
9
F
T
T
T
T
10
F
T
T
T
T
11
F
F
F
F
T
12
F
F
F
T
T
13
F
F
F
T
T
Figure 4.8 Table of t(i,j) for the instance of PARTITION for which
A={a1,a2,a3,a4,a5}, s(a1)=1, s(a2)=9, s(a3)=5, s(a4)=3, and s(a5)=8.
The answer for this instance is "yes", since t(5,13)=T, reflecting the
fact that s(a1)+s(a2)+s(a4)=13=26/2.
2
Backtracking
B  0.5aA s(a)
i=n; W=B;
if ( t(n, W)== false) then stop;
While (i> 0 ) do
{ if (t(i, W) == true) {
if (t(i-1, W)== true) then i=i-1;
else
{ W=W-s(ai); print “ai” i=i-1; }
}
}
3
Time complexity
• The algorithm takes at most O(nB) time to fill in the
table, where B  0.5aA s(a) (Each cell needs constant
time to compute).
•Do we have a polynomial time algorithm to solve the
Partition Problem and thus all NP-complete problems?
–No.
–O(nB) is not polynomial in terms of the input size.
S(ai)=2n=10000…0 . (binary number of n+1 bits ).
So B is at least O(2n). The input size is O(n2) if there some ai with
S(ai)=2n.
B is not polynomial in terms of n (input size) in general.
However, if any upper bound is imposed on B, (e.g., B is Polynomial),
the problem can be solved in polynomial time for this special case.
(This is called pseudo-polynomial.)
4
0-1 version
5
6
7
8
9
10
Change-making problem:
Given an amount n and unlimited quantities of coins
of each of the denominations
d1, d2, …, dm,
find the smallest number of coins that add up to n or
indicate that the problem does not have a solution.
Solution:
Let d(i) be the minimum number of coins used for
amount i.
Initial values: d(0)=0, d(i)=.
equation: d(i) = min d(i-dk)+1.
k=1, 2, …, m.
11
Change-making problem:
Initial values: d(0)=0, d(i)=.
equation: d(i) = min d(i-dk)+1
k=1, 2, …, m & i-d ≥0
k
d1=2 and d2=5. i=7.
i= 0, 1, 2, 3, 4, 5, 6, 7
d(i): 0, , 1, , 2, 1, 3, 2.
Backtracking: $5, $2.
(how do you get d(7)=2? d(7)=d(2)+5. Print $5 and
goto d(2). How do you get d(2)? D(2)=2+d(0). Print
out $2 and goto d(0). Whenever reach d(0), we stop. )
for i=3, since d(3)= , there is no solution.
12
More On Dynamic programming
Algorithms
Shortest path with edge constraint:
Let G=(V, E) be a directed graph with weighted edges. Let s and v be
two vertices in V. Find a shortest path from s to u with exactly k
edges. Here kn-1 is part of the input.
Solution:
Define d(i, v) be the length of the shortest path from s to v with exactly i
edges.
d(i, v)=min {c(w, v)+d(i-1, w)}
wV.
Initial values: d(i, s)=0, for i=0, d(i,s)=  for i=1, 2, …, d(0, v)=;
d(k, v) will give the length of the shortest path. A backtracking process can
give the path.
13
u
5
v
8
8
-2
6
z 0
-3
8
7
-4
2
8
8
7
9
x
y
i
z,
u,
x,
v,
y
0
0




1 
6z
7z
2 

14u
4x
3
2v

9y
4y


2u
23x.
14
• Exercise: Let T be a rooted binary tree, where
each internal node in the tree has two children and
every node (except the root) in T has a parent.
Each leaf in the tree is assigned a letter in ={A, C,
G, T}. Figure 1 gives an example. Consider an
edge e in T. Assume that every end of e is
assigned a letter. The cost of e is 0 if the two letters
are identical and the cost is 1 if the two letters are
not identical. The problem here is to assign a letter
in  to each internal node of T such that the cost of
the tree is minimized, where the cost of the tree is
the total cost of all edges in the tree. Design a
polynomial-time dynamic programming algorithm
to solve the problem.
15
A
A
A
C
Figure 1
16
Assignment 4.
(Due on Friday of Week 13. Drop it in Mail Box
71 or 72)
This time, Sze Man Yuen and I can explain the
questions, but we will NOT tell you how to solve
the problems.
Question 1. (30 points) Give a polynomial time
algorithm to find the longest monotonically
increasing subsequence of a sequence of n numbers.
Your algorithm should use linear space. (10 points
for linear space) (Assume that each integer appears
once in the input sequence of n numbers)
Example: Consider sequence 1,8, 2,9, 3,10, 4, 5.
Both subsequences 1, 2, 3, 4, 5 and 1, 8, 9, 10 are
monotonically increasing subsequences. However,
1,2,3, 4, 5 is the longest.
17
Assignment 4.
• Question 2. (30 points) Given an integer d and a
sequence of integers s=s1s2…sn. Design a
polynomial time algorithm to find the longest
monotonically increasing subsequence of s such that
the difference between any two consecutive
numbers in the subsequence is at least d.
• Example: Consider the input sequence 1,7,8, 2,9,
3,10, 4, 5. The subsequence 1, 2, 3, 4, 5 is a
monotonically increasing subsequence such that the
difference between any two consecutive numbers in
the subsequence is at least 1.
• 1, 3, 5 is a monotonically increasing subsequence
such that the difference between any two consecutive
numbers in the subsequence is at least 2.
18
Assignment 4.
Question 3. (40 points). Suppose you have one
machine and a set of n jobs a1, a2, …, an to process
on that machine. Each job aj has an integer
processing time tj, a profit pj and an integer deadline
dj. The machine can process only one job at a time,
and job aj must run uninterruptedly for tj
consecutive time units. If job aj is completed by its
deadline dj, you receive a profit pj, but if it is
completed after its deadline, you receive a profit of
0. Give a dynamic programming algorithm to find
the schedule that obtains the maximum amount of
profit. What is the running time of your algorithm?
(Let d be the biggest deadline, the running time can be
related to d. )
19