CS代考程序代写 Hidden Markov Mode information theory Bioinformatics algorithm Lecture 6:

Lecture 6:
Dynamic Programming I
The University of Sydney
Page 1
Fast Fourier Transform

General techniques in this course
– Greedy algorithms [Lecture 3]
– Divide & Conquer algorithms [Lectures 4 and 5]
– Dynamic programming algorithms [today and 11 Apr] – Network flow algorithms [18 Apr and 2 May]
The University of Sydney
Page 2

Algorithmic Paradigms
– Greedy. Build up a solution incrementally, myopically optimizing some local criterion.
– Divide-and-conquer. Break up a problem into two sub- problems, solve each sub-problem independently, and combine solution to sub-problems to form solution to original problem.
– Dynamic programming. Break up a problem into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems.
The University of Sydney Page 3

Dynamic Programming Applications
– Areas.
– Bioinformatics.
– Control theory.
– Information theory.
– Operations research.
– Computer science: theory, graphics, AI, systems, ….
– Some famous dynamic programming algorithms. – Viterbi for hidden Markov models.
– Unix diff for comparing two files.
– Smith-Waterman for sequence alignment.
– Bellman-Ford for shortest path routing in networks.
– Cocke-Kasami-Younger for parsing context free grammars.
The University of Sydney
Page 4

6.1 Weighted Interval Scheduling
The University of Sydney Page 5

Recall Interval Scheduling (Lecture 3)
– Interval scheduling.
– Input: Set of n jobs. Each job i starts at time sj and finishes at time fj.
– Two jobs are compatible if they don’t overlap in time.
– Goal: find maximum subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 6

Recall Interval Scheduling (Lecture 3)
– Theorem: Greedy algorithm [Earliest finish time] is optimal.
– Claim++: For every 1 ≤ r ≤ k, there exists an optimal solution
containing i1, i2, … ir.
– Proof: (by exchange argument)
– Inductive case (r > 1):
– Assume true for r – 1. Let J1, J2, … Jm be an optimal solution with i1 = J1, i2 = J2, …, ir-1 = Jr-1
– By def. of Greedy, ir finishes earlier than Jr
– Thus, we can swap Jr for ir and solution still feasible and optimal.
Greedy:
OPT: J1 J2 The University of Sydney
…
i1
i2
ir – 1
ir
…
Jr – 1
Jr
Can swap Jr – 1 for ir – 1
Page 7

Recall Interval Scheduling (Lecture 3)
There exists a greedy algorithm [Earliest finish time] that computes the optimal solution in O(n log n) time.
The University of Sydney Page 8

Weighted Interval Scheduling
– Weighted interval scheduling problem.
– Job j starts at sj, finishes at fj, and has weight vj .
– Two jobs compatible if they don’t overlap.
– Goal: find maximum weight subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 9

Unweighted Interval Scheduling Review
– Recall. Greedy algorithm works if all weights are 1.
– Consider jobs in ascending order of finish time.
– Add job to subset if it is compatible with previously chosen jobs.
– Observation. Greedy algorithm can fail if arbitrary weights are allowed.
b
a
weight = 999 weight = 1
The University of Sydney
Page 10
0 1 2 3 4 5 6 7 8 9 10 11
Time

Weighted Interval Scheduling
Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn .
Def. p(j) = largest index i < j such that job i is compatible with j. Ex: p(8)=5,p(7)=3,p(2)=0. 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney Time Page 11 Key steps: Dynamic programming 1. Define subproblems 2. Find recurrence relating subproblems 3. Solve the base cases 4. Transform recurrence into an efficient algorithm The University of Sydney Page 12 Dynamic Programming: Weighted Interval Scheduling Step 1: Define subproblems OPT(j) = value of optimal solution to the problem consisting of job requests 1, 2, ..., j. The University of Sydney Page 13 Weighted Interval Scheduling Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn . Def. p(j) = largest index i < j such that job i is compatible with j. Solve OPT(8) 1 3 2 4 5 6 7 8 p(8) The University of Sydney Page 14 0 1 2 3 4 5 6 7 8 9 10 11 Time Dynamic Programming: Weighted Interval Scheduling Step 2: Find recurrences – Case 1: OPT selects job j. • can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., p(j) The University of Sydney Page 15 Dynamic Programming: Weighted Interval Scheduling Step 2: Find recurrences – Case 1: OPT selects job j. • can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., p(j) The University of Sydney Page 16 OPT(j) = vj + OPT (p(j)) Case 1 Weighted Interval Scheduling Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn . Def. p(j) = largest index i < j such that job i is compatible with j. Solve OPT(8) 1 3 2 4 5 6 7 8 p(8) The University of Sydney Page 17 0 1 2 3 4 5 6 7 8 9 10 11 Time Dynamic Programming: Weighted Interval Scheduling Step 2: Find recurrences – Case 1: OPT selects job j. • can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., p(j) – Case 2: OPT does not select job j. • must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., j-1 OPT(j) = vj + OPT (p(j)) Case 1 The University of Sydney Page 18 Dynamic Programming: Weighted Interval Scheduling Step 2: Find recurrences – Case 1: OPT selects job j. • can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 } • must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., p(j) – Case 2: OPT does not select job j. • must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., j-1 OPT(j) = max {vj + OPT (p(j)), OPT(j-1)} Case 1 Case 2 The University of Sydney Page 19 Dynamic Programming: Weighted Interval Scheduling Step 3: Solve the base cases OPT(0) = 0 OPT(j)=ìí 0 if j=0 îmax{vj +OPT(p(j)), OPT(j-1)} otherwise The University of Sydney Page 20 Done...more or less Weighted Interval Scheduling: Naïve Recursion – Naïve recursion algorithm. Input: n, s1,...,sn , f1,...,fn , v1,...,vn Sort jobs by finish times so that f1 £ f2 £ ... £ fn. Compute p(1), p(2), ..., p(n) Compute-Opt(j) { if (j = 0) return 0 else return max(vj + Compute-Opt(p(j)), Compute-Opt(j-1)) } return Compute-Opt(n) The University of Sydney Page 21 Weighted Interval Scheduling: Correctness Theorem: Compute-Opt(j) = OPT(j) Proof: Proof by induction. – Base case: OPT(0) = 0 – Induction hypothesis (i M[j-1])
print j
Find-Solution(p(j))
else
Find-Solution(j-1)
}
picked job j
# of recursive calls £ n Þ O(n). The University of Sydney
Page 31
31

Maximum-sum contiguous subarray
Given an array A[ ] of n numbers, find the maximum sum found in any contiguous subarray
A zero length subarray has maximum 0
Example:
1
-2
7
5
6
-5
5
8
1
-6
The University of Sydney Page 32

Brute-force algorithm (Lecture 1)
– How many subarrays in total?
– Algorithm: For each subarray, compute the sum. Report
the subarray that has the maximum sum.
The University of Sydney
Page 34
O(n2)
O(n)
Total time: O(n3)

Divide-and-conquer algorithm (Tutorial 5)
Maximum contiguous subarray (MCS) in A[1..n]
– Three cases:
a) MCS in A[1..n/2]
b) MCS in A[n/2+1..n]
c) MCS that spans A[n/2, n/2 + 1]
– (a) & (b) can be found recursively
– (c) can be found in two steps
– Consider MCS in A[1..n/2] ending in A[n/2].
– Consider MCS in A[n/2+1..n] starting at A[n/2+1]. – Sum these two maximum
The University of Sydney
Page 35

Divide-and-conquer algorithm
Maximum contiguous subarray (MCS) in A[1..n]
– Threecases:
a) MCS in A[1..n/2]
b) MCS in A[n/2+1..n]
c) MCS that spans across A[n/2]
2·T(n/2)
– (a) & (b) can be found recursively
– (c) can be found in two steps
– Consider MCS in A[1..n/2] ending in A[n/2].
– Consider MCS in A[n/2+1..n] starting at A[n/2+1].
– Sum these two maximum The University of Sydney
Page 38

Divide-and-conquer algorithm
Maximum contiguous subarray (MCS) in A[1..n]
a. MCS in A[1..n/2]
b. MCS in A[n/2+1..n]
c. MCS that spans across A[n/2]
2·T(n/2)
– (a) & (b) can be found recursively
– (c) can be found in two steps
– Consider MCS in A[1..n/2] ending in A[n/2].
– Consider MCS in A[n/2+1..n] starting at A[n/2+1]. O(n) – Sum these two maximum
The University of Sydney
Page 47

Divide-and-conquer algorithm
Maximum contiguous subarray (MCS) in A[1..n]
– MCSinA[1..n/2]
a. MCS in A[n/2+1..n]
b. MCS that spans across A[n/2]
2·T(n/2)
– (a) & (b) can be found recursively
– (c) can be found in two steps
– Consider MCS in A[1..n/2] ending in A[n/2].
– Consider MCS in A[n/2+1..n] starting at A[n/2+1]. O(n) – Sum these two maximum
Total time: T(n) = 2·T(n/2) + O(n) = O(n log n) The University of Sydney Page 48

Dynamic programming Step 1: Define subproblems
OPT(i) = optimal solution ending at i.
The University of Sydney Page 49

Dynamic programming algorithm
Example 1:
OPT[1] = 6 6
3 -1 2
OPT[2] = 3 OPT[3] = 1 OPT[4] = 4 OPT[5] = 3 OPT[6] = 5
6 -3
6 -3 -2 6 -3 -2 6 -3 -2 6 -3 -2
3
3 -1
3 -1 2
6 -3 -2
The University of Sydney
Page 50
OPT[i] – optimal solution ending at i

Dynamic programming algorithm
Example 2:
OPT[1] = 0 -2
OPT[2] = 5 OPT[3] = 4 OPT[4] = 0 OPT[5] = 3 OPT[6] = 2 OPT[7] = 4
-2 5
-1 -5 -2 5 -1
3 -1 2
-2 5
-2 5 -2 5 -2 5 -2 5
-1 -5 -1 -5 -1 -5 -1 -5
3
3 -1
3 -1 2
The University of Sydney
Page 52
OPT[i] – optimal solution ending at i

Dynamic programming algorithm
Example 2:
OPT[1] = 0 -2
OPT[2] = 5 OPT[3] = 4 OPT[4] = 0 OPT[5] = 3 OPT[6] = 2 OPT[7] = 4
Step 2: Find recurrences
-2 5
-1 -5 -2 5 -1
3 -1 2
-2 5
-2 5 -2 5 -2 5 -2 5
-1 -5 -1 -5 -1 -5 -1 -5
3
3 -1
3 -1 2
The University of Sydney
Page 53
OPT[i] = max{OPT[i-1]+A[i], 0}

Dynamic programming algorithm Step 3: Solve the base cases
OPT[1] = max(A[1], 0)
OPT[i] = The University of Sydney
max(A[1], 0) max{OPT[i-1]+A[i], 0}
if i=1 if i>1
Why can’t we just take A[1]?
Page 54

Pseudo Code
OPT[1] = max(A[1], 0) for i = 2 to n do
OPT[i] = max(OPT[i-1]+A[i], 0) MaxSum = max1≤ i ≤ n OPT[i]
The University of Sydney
Page 55
OPT[i] – optimal solution ending at i
Total time: O(n)

6.4 Knapsack
A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem.
First mentioned by Mathews in 1897. “Knapsack problem” by Dantzig in 1930.
The University of Sydney Page 56

Knapsack Problem
– Knapsackproblem.
– Givennobjectsanda”knapsack.”
– Item i weighs wi > 0 kilograms and has value vi > 0. – KnapsackhascapacityofWkilograms.
– Goal: fill knapsack so as to maximize total value.
– Example: { 3, 4 } has value 40.
W = 11
Item
Value
Weight
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
– Greedy: repeatedly add item with maximum ratio vi / wi.
– Ex: { 5, 2, 1 } achieves only value = 35 Þ greedy not optimal.
The University of Sydney
Page 58

Knapsack Problem
– Knapsackproblem.
– Givennobjectsanda”knapsack.”
– Item i weighs wi > 0 kilograms and has value vi > 0. – KnapsackhascapacityofWkilograms.
– Goal: fill knapsack so as to maximize total value.
– Example: { 3, 4 } has value 40.
W = 11
Item
Value
Weight
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
– Greedy: repeatedly add item with maximum ratio vi / wi. (“best bang for buck”)
– Ex: { 5, 2, 1 } achieves only value = 35 Þ greedy not optimal. The University of Sydney
Page 59

Dynamic Programming: False Start
– Definition. OPT(i) = max profit subset of items 1, …, i.
– Case 1: OPT does not select item i.
• OPTselectsbestof{1,2,…,i-1}
– Case 2: OPT selects item i.
• accepting item i does not immediately imply that we will have to
reject other items
• without knowing what other items were selected before i, we don’t even know if we have enough room for i
Conclusion: Need subproblems with more structure!
The University of Sydney Page 60

Dynamic Programming: Adding a New Variable Step 1: Define subproblems
OPT(i, w) = max profit subset of items 1, …, i with weight limit w.
Item
Value
1
1
2
6
3
18
4
22
5
28
The University of Sydney
Page 61
i=5 w = 11

Dynamic Programming: Adding a New Variable Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
Item
Value
1
1
2
6
3
18
4
22
5
28
The University of Sydney
Page 63
OPT[i,w] = OPT[i-1,w]
case 1
i=5 w = 11
max{

Dynamic Programming: Adding a New Variable Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• new weight limit = w – wi
• OPT selects best of { 1, 2, …, i–1 } using this new weight limit
OPT[i,w] = OPT[i-1,w] , vi+OPT[i-1,w-wi]
case 1 case 2
The University of Sydney
Page 65
max{

Dynamic Programming: Adding a New Variable Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• new weight limit = w – wi
• OPT selects best of { 1, 2, …, i–1 } using this new weight limit
OPT[i,w] = OPT[i-1,w] , vi+OPT[i-1,w-wi]}
case 1 case 2
The University of Sydney
Page 66
max{

Dynamic Programming: Adding a New Variable Step 3: Solve the base cases
The University of Sydney
Page 67
OPT[0,w] = 0

Dynamic Programming: Adding a New Variable
– Base case: OPT[0,w] = 0
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• newweightlimit=w–wi
• OPT selects best of { 1, 2, …, i–1 } using this new weight limit
0 if i=0 OPT[i,w] = OPT[i-1,w] if wi > w
max{OPT[i-1,w], vi+OPT[i-1,w-wi]} otherwise
The University of Sydney Page 68

Knapsack Algorithm Recurrence: Example
n+1
W+1
0 1 2 3 4 5 6 7 8 9 10 11
Æ 000000000000 {1} 011111111111 {1,2} 016777777777
{1,2,3} 0 1 6 7 7 18 19 24 25 25 25 25
{1,2,3,4} {1,2,3,4,5}
0 1 6 7 7 18 22 24 28 29 29 40 0 1 6 7 7 18 22 28 29 34 34 40
OPT[i,w] =
0
OPT[i-1,w]
max{OPT[i-1,w], vi+OPT[i-1,w-wi]}
if i=0
if wi > w otherwise
W = 11
Item Value Weight
111 262 3 18 5 4 22 6
5 28 7
The University of Sydney
Page 69

Knapsack Problem: Bottom-Up
– Knapsack. Fill up an (n+1)-by-(W+1) array.
Input: n, w1,…,wN, v1,…,vN for w = 0 to W
M[0, w] = 0
for i = 1 to n
for w = 1 to W
if (wi > w)
M[i, w] = M[i-1, w]
else
M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]} return M[n, W]
The University of Sydney Page 70

Knapsack Algorithm: Bottom-Up Example
n+1
W+1
0 1 2 3 4 5 6 7 8 9 10 11
Æ 000000000000 {1} 011111111111 {1,2} 016777777777
{1,2,3} 0 1 6 7 7 18 19 24 25 25 25 25
{1,2,3,4} {1,2,3,4,5}
0 1 6 7 7 18 22 24 28 29 29 40 0 1 6 7 7 18 22 28 29 34 34 40
OPT[i,w] =
0
OPT[i-1,w]
max{OPT[i-1,w], vi+OPT[i-1,w-wi]}
if i=0
if wi > w otherwise
W = 11
Item Value Weight
111 262 3 18 5 4 22 6
5 28 7
The University of Sydney
Page 71

n+1
W+1
0 1 2 3 4 5 6 7 8 9 10 11
Æ 000000000000 {1} 011111111111 {1,2} 016777777777
{1,2,3} 0 1 6 7 7 18 19 24 25 25 25 25
Knapsack Algorithm
OPT[i,w] =
0
OPT[i-1,w]
max{OPT[i-1,w], vi+OPT[i-1,w-wi]}
OPT: {4,3}
value = 22 + 18 = 40
if i=0 Item Value Weight
The University of Sydney
W=11 3 18 5 4 22 6
5 28 7
Page 72
{1,2,3,4} {1,2,3,4,5}
0 1 6 7 7 18 22 24 28 29 29 40 0 1 6 7 7 18 22 28 29 34 34 40
if wi > w otherwise
111 262

Knapsack Problem: Running Time
– Running time: Q(nW).
– Not polynomial in input size!
– “Pseudo-polynomial” : polynomial in size of numbers not their bit length – Decision version of Knapsack is NP-complete. [Lecture 10]
– Knapsack approximation algorithm. There exists a polynomial algorithm (w.r.t. n) that produces a feasible solution that has value within 0.01% of optimum. [Lecture 10/11?]
The University of Sydney Page 73
What is input size?
Input size = O(n log W)

Longest increasing subsequence
Given a sequence of numbers X[1..n] find the longest increasing subsequence (i1, i2, …, ik), that is a subsequence where numbers in the sequence increase.
The University of Sydney
Page 74
52863697

Longest increasing subsequence
Define a vector L[]:
– L[i] = length of the longest increasing subsequence that ends at i.
– L[1]=1 52863697
– Example: L[1] = 1
L[2] = 1 L[3] = 2
L[4] = 2 L[5] = 2 L[6] = 3
L[7] = 4 L[8] = 4
The University of Sydney
Page 76

Longest increasing subsequence
Define a vector L[]:
– L[i] = length of the longest increasing subsequence that ends at i.
– L[1]=1 52863697
– Dynamic programming formula:
L[i] = max { L[j] +1 | X[j] < X[i]} 0

Related Posts