CS260 Algorithms

Graham Cormode
[Link]@[Link]

Dynamic
Programming
Algorithmic Paradigms

 Greedy Build up a solution incrementally, greedily optimizing

some local criterion
 Divide-and-conquer Break up a problem into 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 the whole
– We require the “optimal substructure” property: that the optimal
solution can be built up from optimal solutions to subproblems
– We want that the number of subproblems does not grow too big

2
Dynamic Programming outline

 The concept of dynamic programming via “memoization”

 Examples of dynamic programming “Bellman” equations
 Bottom-up vs. top-down views of dynamic programming
 Dynamic programming variations:
– One dimensional dynamic programming (weighted intervals)
– Multiway choice dynamic programming (segmented least squares)
– Two dimensional dynamic programming (knapsack)
– Dynamic programming for sequences and strings
– (If time) Reducing the memory cost for tables by reusing space

3 CS260 Algorithms
Dynamic Programming History

 Attributed to Richard Bellman [1950s]

– Pioneered the systematic study of dynamic programming
– Invented the term “dynamic programming” as a marketing tool
 “Dynamic programming” is not about computer programming
– Dynamic programming = planning over time
– Secretary of Defense was hostile to mathematical research
– Bellman sought an impressive name to avoid confrontation

"it's impossible to use dynamic in a pejorative sense"

"something not even a Congressman could object to"

Reference: Bellman, R. E. Eye of the Hurricane, An Autobiography.

4
Dynamic Programming Applications

 Dynamic programming shows up in many areas of study:

– Bioinformatics: find similar genetic sequences
– Control theory: to decide actions within systems (e.g., engines)
– Information theory: to find an optimal coding scheme
– Operations research: to find optimal allocations (e.g., schedules)
– Computer science: theory, graphics, AI, compilers, systems, ….
 Some famous dynamic programming algorithms:
– Linux ‘diff’ for comparing two files
– Viterbi algorithm for hidden Markov models
– Smith-Waterman for genetic sequence alignment
– Bellman-Ford for shortest path routing in networks
– Cocke-Kasami-Younger for parsing context free grammars
5
 Weighted Interval Scheduling Segmented Least Squares Knapsack Problem

RNA Secondary Structure Sequence Alignment Sequence Alignment in Linear Space

6 CS260 Algorithms
Kleinberg Tardos Section 6.1-6.2

WEIGHTED INTERVAL
SCHEDULING
Weighted Interval Scheduling

 Weighted interval scheduling problem (WIS)

– Job j starts at sj, finishes at fj, and has weight or value vj
– Two jobs are said to be compatible if they don't overlap
 Goal: find maximum weight subset of mutually compatible jobs
a : £££

b : ££££

c : £

d : ££

e : £££

f : £££££

g : ££

h : £
Time
0 1 2 3 4 5 6 7 8 9 10
8
 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 spectacularly if
arbitrary weights are allowed

weight = 999 b

weight = 1 a
Time
0 1 2 3 4 5 6 7 8 9 10 11

9
Weighted Interval Scheduling

 Notation Label jobs by finishing time: f1  f2  . . .  fn

 Define p(j) = largest index i < j such that job i is compatible with j
 Example: p(8) = 5, p(7) = 3, p(2) = 0
1

8
Time
0 1 2 3 4 5 6 7 8 9 10 11
10
Dynamic Programming: Binary Choice

 Notation OPT(j) = value of optimal solution to the problem

consisting of job requests 1, 2, ..., j
 Case 1: OPT selects job j
– collect profit vj
– can’t pick incompatible jobs { p(j) + 1, p(j) + 2, ..., j-1 }
– must include optimal solution to the WIS problem consisting of
remaining compatible jobs 1, 2, ..., p(j) optimal substructure
 Case 2: OPT does not select job j
– must include optimal solution to the WIS problem consisting of
remaining compatible jobs 1, 2, ..., j-1
optimal substructure

Bellman OPT(j) = 0 if j = 0
equation: = max{ vj + OPT(p(j)) , OPT(j-1)} otherwise
11
Weighted Interval Scheduling: Brute Force
 Brute force algorithm to implement this idea:
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))
}

 Running time: T(n) = T(n-1) + T(p(n)) + O(1) and T(1) = 1

 Worst case: T(n) = T(n-1) + T(n-2) + O(1)
– Question: Is this polynomial or exponential time?
12
Weighted Interval Scheduling: Brute Force

 Observation Recursive algorithm can fail spectacularly

because of redundant sub-problems  exponential growth
 Example Number of recursive calls for a family of "layered"
instances grows like Fibonacci sequence T(n) = T(n-1)+T(n-2)+O(1)
– Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1
 But it doesn’t take exponential time to compute Fib(n)
– We can store and reuse precomputed results
5

1 4 3

2
3 2 2 1
3
4
2 1 1 0 1 0
5
1 0
p(1) = 0, p(j) = j-2
13
 Weighted Interval Scheduling: Memoization
 Computer science calls storing computed results “memoization”
– Not “memorization”, but it is a similar concept
 Memoization means to store results of each sub-problem in a
table, and look up the values whenever needed
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)

for j = 1 to n
M[j] = empty
M[0] = 0 M[.] is the table of results to fill in
M-Compute-Opt(j) {
if (M[j] is empty)
M[j] = max(vj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
return M[j]
} 14
Weighted Interval Scheduling: Running Time

Claim Memoized version of algorithm takes O(n log n) time

– Sort by finish time: O(n log n)
– Computing p() : O(n log n) via sorting by start time
 M-Compute-Opt(j): each invocation takes O(1) time and either
1. returns an existing value M[j]
2. fills in one new entry M[j] and makes two recursive calls
 Progress measure  = # nonempty entries of M[]
– initially  = 0, throughout   n
– Step 2. increases  by 1  at most 2n recursive calls in total
 Overall running time of M-Compute-Opt(n) is O(n) □
 Remark. O(n) if jobs are pre-sorted by start and finish times

15
Weighted Interval Scheduling: Finding a Solution

 Dynamic programming algorithms computes the optimal value

– What if we want the solution itself?
 The table of values usually also encodes the solution
– Find the solution by post-processing the table in O(n) time

Run M-Compute-Opt(n)
Run Find-Solution(n)

Find-Solution(j) {
if (j = 0)
output nothing
else if (vj + M[p(j)] > M[j-1])
print j
Find-Solution(p(j))
else
Find-Solution(j-1)
}
16
Weighted Interval Scheduling: Bottom-Up

 Bottom-up dynamic programming: Unwind the recursion

– Solve the problem by filling in the table from smallest to biggest
 No recursive calls, because every needed value is already there
 Same computational complexity, but slightly simpler code
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)

Iterative-Compute-Opt {
M[0] = 0
for j = 1 to n
M[j] = max(vj + M[p(j)], M[j-1])
}

17
Kleinberg Tardos Section 6.3

SEGMENTED LEAST SQUARES

Segmented Least Squares

 The classic least squares problem in statistics and data science

– Foundational problem in regression and numerical analysis
– Given n points in the plane: (x1, y1), (x2, y2) , . . . , (xn, yn)
– Find a line y = ax + b that minimizes the sum of the squared error
 Sum of squared error is SSE1,n = ∑i=1n (yi – axi – b)2
– We must choose parameters a and b to minimize SSE
 Solved by (partial) derivatives – no dynamic programming (yet)
– Write SX1,n = ∑i=1n xi and SY1,n = ∑i=1n yi
n n 2
y
– Write SXY1,n = ∑i=1 xiyi and SXX1,n = ∑i=1 xi
– a = (n SXY1,n – SX1,n SY1,n)/(n SXX1,n – (SX1,n)2)
– b = (SY1,n – a SX1,n)/n
– O(n) time to compute each sum x
19
Segmented Least Squares

 We will now solve the problem of segmented least squares (SLS)

– Points lie (roughly) on a sequence of several line segments
– Given n points in the plane (x1, y1), (x2, y2) , . . . , (xn, yn) with
x1 < x2 < ... < xn, find a sequence of lines that minimizes some f(x)
 We choose f(x) to balance accuracy and complexity of solution
– Allow n lines: perfect fit, but no useful explanation of the data
 Combine SSE for each segment as E, with total number of lines L
 Choose f(x) = E + c L for constant c > 0
– cL is a “regularization” term y
 Now how to solve given f(x)?

20 x
Dynamic Programming: Multiway Choice

 We can set up some notation to describe the cost of a solution

– OPT(j) = minimum cost for points p1, pi+1 , . . . , pj
– e(i, j) = minimum sum of squares for points pi, pi+1 , . . . , pj
 Use previous equations to write e(i,j) in terms of SXi,j, SXYi,j etc.
– For points pi… pj, we take the optimal least squares solution
 To compute OPT(j), find the cost of extending a prefix solution:
– If the last segment uses points pi, pi+1 , . . . , pj for some i,
then the cost is given by e(i, j) + c + OPT(i-1)
Bellman OPT(j) = 0 if j = 0
equation: = min1 ≤ i ≤ j { e(i,j) + c + OPT(i-1)} otherwise

21
Segmented Least Squares: Algorithm
INPUT: n, p1,…,pN , c

Segmented-Least-Squares() {
M[0] = 0
for j = 1 to n
for i = 1 to j
compute the least square error eij for
the segment pi,…, pj

for j = 1 to n
M[j] = min 1  i  j (eij + c + M[i-1])

return M[n]
}

 Running time O(n3) time to run the whole algorithm

– The bottleneck is computing e(i, j) for O(n2) pairs,
– O(n) per (i,j) pair using the previous formula for sum squared error
 Next, we reduce this to O(n2) with some careful precomputation
22
Optional: Cumulative Sums to speed up SLS

 Recall, we need e(i,j) = SSEi,j = ∑k=ij (yk – axk – b)2

= ∑k=ij (yk2 + a2 xk2 + b2 – 2axkyk – 2byk + 2abxk)
 And a, b are functions of (xi, yi), (xi+1, yi+1)… (xj, yj)
aij = (n SXYi,j – SXi,j SYi,j)/(n SXXi,j – (SXi,j)2)
bij = (SYi,j – a SXi,j)/n
 It looks like computing aij, bij, and e(i,j) could take time O(n) each
– Linear time to process all the O(n) points i…j
 There are O(n2) (i,j) pairs to consider, so O(n3) time in total
 Prefix sums: write SXi,j = ∑k=ij xk = ∑k=1j xk - ∑k=1i-1 xk = (SX1,j – SX1,i-1)
– Precompute SX1,j for j=1…n in O(n) time to find any SXi,j in O(1) time
 The same trick works for the other sums: SY, SXX, SXY
– Now e(i,j) takes O(1) time per lookup: O(n2) for the whole algorithm
23 CS260 Algorithms
Kleinberg Tardos Section 6.4

KNAPSACK PROBLEM
Knapsack Problem

 The knapsack problem aims to maximize value subject to capacity

– Given n individual objects and a “knapsack” of fixed size
– Item i weighs wi > 0 kilograms and has value vi > 0
– Knapsack has capacity of W kilograms
# value weight
– Goal: fill knapsack to maximize total value
A 1 1
 Example: picking { C, D } has value 40 B 6 2
C 18 5
W = 11 D 22 6
E 28 7

 Greedy approach: repeatedly add item with biggest ratio vi / wi

 Example: { E, B, A } achieves only value = 35  greedy not optimal

25
Dynamic Programming: False Start

 Try to define OPT(i) = maximum profit subset of items 1, …, i

– Case 1: OPT does not select item i
◼ OPT selects best of { 1, 2, …, i-1 }

– Case 2: OPT does select 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: We need to consider more sub-problems!
– We need to parameterize the sub-problems in more detail
 Knapsack is a two dimensional problem: values × weight
– We will go on to build a two dimensional table
26
Dynamic Programming: Adding a New Variable

 Instead, define optimal over indices and weights

OPT(i, w) = max profit subset of items 1, …, i with weight limit w
 Case 1: OPT(i,w) does not select item i
– OPT selects best of { 1, 2, …, i - 1 } using weight limit w
 Case 2: OPT(i,w) selects item i
– new weight limit = w – wi
– OPT selects best of { 1, 2, …, i - 1 } using this new weight limit

OPT(i, w) = 0 if i = 0
= OPT(i-1, w) if wi > w
= max { OPT(i-1, w), vi + OPT(i-1, w-wi)} otherwise

27
Knapsack Problem: Bottom-Up

 Knapsack dynamic programming. Fill up an n-by-W array

– Takes time O(1) per entry, O(nW) in total

Input: n, W, 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]
28
 Knapsack Algorithm
W+1
0 1 2 3 4 5 6 7 8 9 10 11
 0 0 0 0 0 0 0 0 0 0 0 0
{A} 0 1 1 1 1 1 1 1 1 1 1 1
n+1 { A, B } 0 1 6 7 7 7 7 7 7 7 7 7
{ A, B, C } 0 1 6 7 7 18 19 24 25 25 25 25
{ A, B, C, D } 0 1 6 7 7 18 22 24 28 29 29 40
{ A, B, C, D, E } 0 1 6 7 7 18 22 28 29 34 34 40

Item Value Weight

OPT: { C, D }
A 1 1 W = 11
B 6 2
value = 22 + 18 = 40
C 18 5 read off the optimal
D 22 6 solution from the table
E 28 7
29
Knapsack Problem: Running Time

 The running time of this algorithm is (n W)

– Not polynomial in input size!
– Parameter W is specified in (log W) bits, so the time is
exponential in the size of this parameter
– The algorithm is called “pseudo-polynomial."
– Decision version of Knapsack is NP-complete (foreshadowing)
 Knapsack approximation algorithm
There exists a polynomial time algorithm that produces a
feasible solution that has value within 0.01% of optimum
– See Section 11.8 of Kleinberg Tardos if interested

30
Kleinberg Tardos Section 6.5

RNA SECONDARY STRUCTURE

RNA Secondary Structure

 RNA = Ribonucleic acid, in biochemistry

– DNA = two-stranded (double helix), RNA = single stranded
 To us, RNA is a string B = b1b2bn over the alphabet { A, C, G, U }
– A pairs up with U, G pairs up with C
C A
 Secondary structure RNA tends to loop
A A
back and form base pairs with itself A U G C
This structure is essential for
C G U A A G
understanding molecule behavior G
U A U U A
G
A C G C U
G
C G C G A G C
G
Example A U
GUCGAUUGAGCGAAUGUAACAACGUGGCUACGGCGAGA
G
32
RNA Secondary Structure

 Secondary structure A set of pairs S = { (bi, bj) } that satisfy:

– [Watson-Crick] S is a matching and each pair in S is a base pair
complement: A-U, U-A, C-G, or G-C
– [No sharp turns] The ends of each pair are separated by at least 4
intervening bases. If (bi, bj)  S, then i < j - 4
– [Non-crossing] If (bi, bj) and (bk, bl) are two pairs in S, then we
cannot have i < k < j < l
 We can enforce all required conditions with simple checks on S
 Free energy It is assumed that an RNA molecule will form the
secondary structure with the optimum total free energy
– This corresponds to maximizing the number of base pairs
 Goal Given an RNA molecule B = b1b2bn, find a secondary
structure S that maximizes the number of base pairs
33
RNA Secondary Structure: Examples
G
G G G G
G G
C U C U
C G C G C U
A U A U A G
U A U A U A

base pair

A UGUGG C C AU A UGGGG C AU A GUUGG C C AU

4
ok sharp turn: crossing:
disallowed disallowed
34
RNA Secondary Structure: Subproblems

 First attempt OPT(j) = maximum number of base pairs in a

secondary structure of the substring b1b2bj
match bt and bn

1 t n
 Difficulty This set up requires solutions to two sub-problems:
 Finding secondary structure in b1b2bt-1
– OK: this can be expressed as OPT(t-1)
 Finding secondary structure in bt+1bt+2bn-1
– Not OK: we don’t have access to this solution
 So we will set up a richer set of solutions to sub-problems
35
Dynamic Programming Over Intervals

 Notation OPT(i, j) = maximum number of base pairs in a

secondary structure of the substring bibi+1bj
 Case 1 If i  j - 4
– OPT(i, j) = 0 by no-sharp turns condition
 Case 2 Base bj is not involved in a pair
– OPT(i, j) = OPT(i, j-1)
 Case 3. Base bj pairs with bt for some i  t < j - 4
– non-crossing constraint decouples resulting sub-problems
– OPT(i, j) = 1 + maxt { OPT(i, t-1) + OPT(t+1, j-1) }

take max over t such that i  t < j-4 and

bt and bj are Watson-Crick complements
36
Bottom Up Dynamic Programming Over Intervals

 Q. In what order to solve the sub-problems?

– A. Do shortest intervals first - in order of k = (j-i)
– This way, we always have what we need already computed

RNA(b1,…,bn) {
for k = 5, 6, …, n-1
4 0 0 0
for i = 1, 2, …, n-k
j = i + k 3 0 0
Compute M[i, j] using formula i 2 0
1
return M[1, n]
6 7 8 9
}
j
 The dynamic programming approach solves the RNA secondary
structure problem in O(n3) time and O(n2) space
– Two outer loops over k and i, and a third loop over t in the formula
37
Dynamic Programming Summary So Far

 A generic recipe for dynamic programming:

– Characterize structure of problem
– Recursively define value of optimal solution (and state what OPT is)
– Compute value of optimal solution (efficiently!)
– Construct optimal solution from computed information
 We have seen several dynamic programming patterns:
– Binary choice: weighted interval scheduling
– Multi-way choice: segmented least squares
– Adding a new variable: knapsack
– Dynamic programming over intervals: RNA secondary structure
 Top-down vs bottom-up: a personal preference
– Build up incrementally vs. define recursively
38
More Dynamic Programming

 Dynamic programming breaks problems into smaller pieces

– Relying on “optimal substructure” properties
– Building up tables of partial solutions
 We’ve already seen some examples without realizing it
– Dijkstra’s algorithm tabulates the shortest distance to each node
– We can reconstruct the route from this information
 More advanced examples of dynamic programming on graphs
– Bellman-Ford: linear space dynamic programming for shortest paths
– Handles negative edge weights if no negative cycles
– Used in network routing protocols
– Coming up later this term!

39 CS260 Algorithms
Kleinberg Tardos Section 6.6

SEQUENCE ALIGNMENT
String Similarity
o c u r r a n c e -
How similar are two strings?
– ocurrance o c c u r r e n c e

– occurrence
6 mismatches, 1 gap
 Suppose we are allowed to add,
remove or change characters
o c - u r r a n c e
 Can we find an optimal alignment?
o c c u r r e n c e
– Depends on the cost of different
types of ‘edit’ 1 mismatch, 1 gap

o c - u r r - a n c e

o c c u r r e - n c e

0 mismatches, 3 gaps
41
Edit Distance

 Finding the similarity between strings has several applications

– Basis for Linux ‘diff’, in version control
– Speech recognition based on phonemes
– Computational biology: understanding sequences changes
 Edit distance [Levenshtein 1966, Needleman-Wunsch 1970]
– Gap penalty ; mismatch penalty pq
– Cost = sum of gap and mismatch penalties

C T G A C C T A C C T - C T G A C C T A C C T

C C T G A C T A C A T C C T G A C - T A C A T

TC + GT + AG+ 2CA 2 + CA

42
Sequence Alignment

 Goal: Given two strings X = x1 x2 . . . xm and Y = y1 y2 . . . yn find

alignment of minimum cost
 An alignment M is a set of ordered pairs xi-yj such that each
item occurs in at most one pair and no crossings
 The pair xi-yj and xi'-yj' cross if i < i', but j > j'

 Example: CTACCG vs. TACATG x1 x2 x3 x4 x5 x6

C T A C C - G
– M = x2-y1, x3-y2, x4-y3, x5-y4, x6-y6
– Cost(M) = 2 + CA - T A C A T G

y1 y2 y3 y4 y5 y6
43
Sequence Alignment: Problem Structure

 OPT(i, j) = min cost of aligning strings x1 x2 … xi and y1 y2 … yj

 Case 1: OPT matches xi-yj define AA = CC = GG = TT = 0
– pay mismatch for xi-yj + min cost of aligning x1 x2…xi-1 and y1 y2…yj-1
 Case 2a: OPT leaves xi unmatched
– pay gap for xi and min cost of aligning x1 x2 … xi-1 and y1 y2 … yj
 Case 2b: OPT leaves yj unmatched
– pay gap for yj and min cost of aligning x1 x2 … xi and y1 y2 … yj-1

OPT(i,j) = j if i=0
= i if j=0
= min {xi yj + OPT(i-1, j-1),
 + OPT(i-1, j),
 + OPT(i, j-1) } otherwise
44
Sequence Alignment: Algorithm
Sequence-Alignment(m, n, x1x2...xm, y1y2...yn, , ) {
for i = 0 to m
M[i, 0] = i
for j = 0 to n
M[0, j] = j

for i = 1 to m
for j = 1 to n
M[i, j] = min([xi, yj] + M[i-1, j-1],
 + M[i-1, j],
 + M[i, j-1])
return M[m, n]
}

 Analysis (mn) time and space to fill in the table

– There are mn entries in the table, setting M[i,j] takes O(1) time
 For English words or sentences m, n are typically  10-100
 But in computational biology: m = n = 100,000 or more
– 10 billions ops OK, but 10GB array starts to fill memory…
45
Kleinberg Tardos Section 6.7

SEQUENCE ALIGNMENT IN
LINEAR SPACE
Sequence Alignment: Linear Space

 Can we avoid using quadratic space?

 A partial answer: optimal value in O(m + n) space and O(mn) time
– Build up the table one row at a time, and forget the old rows
– Compute OPT(i, •) from OPT(i-1, •)
– But, there’s no longer a simple way to recover the alignment itself
 A result due to [Hirschberg 1975]
Optimal alignment in O(m + n) space and O(mn) time
– Based on a clever combination of divide-and-conquer with
dynamic programming
– Inspired by an idea of Savitch from complexity theory

47
Sequence Alignment: Linear Space

 Edit distance graph: Let f(i, j) be shortest path from (0,0) to (i, j)
– Observation: f(i, j) = OPT(i, j)
– Can compute f(•, j) for any given j in O(mn) time and O(m + n) space

 y1 y2 y3 y4 j y5 y6
 0-0

x1

x2 i-j

x3 m-n
48
Sequence Alignment: Linear Space

 Edit distance graph. Let g(i, j) be shortest path from (i, j) to (m, n)
– Solve by reversing edges and swapping the roles of (0, 0) and (m, n)
– Can compute g(•, j) for any given j in O(mn) time and O(m + n) space

 y1 y2 y3 j y4 y5 y6
 0-0

x1 i-j

x2

x3 m-n
49
Sequence Alignment: Linear Space
 Observation 1 The cost of shortest path via (i, j) is f(i, j) + g(i, j)
 Observation 2 Let q be an index that minimizes f(q, n/2) + g(q, n/2)
Then, the shortest path from (0, 0) to (m, n) uses (q, n/2)

 y1 y2 y3 n/2 y4 y5 y6
 0-0

x1 i-j q

x2

x3 m-n
Sequence Alignment: Linear Space
 Divide: find index q that minimizes f(q, n/2) + g(q, n/2)
– Align xq and yn/2 in the dynamic programming solution
 Conquer: recursively compute optimal alignment in each piece
n/2
 y1 y2 y3 y4 y5 y6
 0-0

x1 i-j q

x2

x3 m-n
51
Sequence Alignment: Running Time Warmup

 Theorem Let T(m, n) = maximum running time of algorithm on

strings of length at most m and n. Then T(m, n) = O(mn log n)
T(m, n) ≤ 2T(m, n/2) + O(mn) ≤ T(m, n) = O(mn logn)

 Remark Analysis is not tight because two sub-problems are of

size (q, n/2) and (m - q, n/2)
– Next, we do a more detailed analysis to save a log n factor

52
Sequence Alignment: Running Time Analysis

 Theorem Let T(m, n) = maximum running time of algorithm

on strings of length m and n. Then T(m, n) = O(mn)
 Proof (by induction on n)
– O(mn) time to compute f( •, n/2) and g ( •, n/2) and find index q
– T(q, n/2) + T(m - q, n/2) time for two recursive calls.
– Choose constant c so that: T(m, 2) ≤ cm
T(2, n) ≤ cn
– Base cases: m = 2 or n = 2
T(m, n) ≤ cmn + T(q, n/2) + T(m- q, n/2)
– Inductive hypothesis: T(m, n)  2cmn
– The induction holds! T(m,n) ≤ T(q,n/2) + T(m−q,n/2) + cmn
– So T(m,n) ≤ 2cmn ≤ 2cqn/2 + 2c(m−q)n/2 + cmn
= O(mn) □ = cqn + cmn − cqn + cmn
= 2cmn
53
The story so far…

 Week 1: intro, recap of algorithms analysis, Stable Matching

– Some refreshers from CS126, some new stuff
 Week 2: Greedy algorithms
– Making locally greedy choices for optimal outcomes
 Week 3: Graph algorithms
– Revisiting shortest paths and spanning trees afresh
 Week 4: Divide and conquer
– Breaking a big problem into smaller pieces
 Week 5: Dynamic programming
– Piecing together a solution from partial answers

54 CS260 Algorithms
Coming up next:

 Week 6: Formalising notions of algorithm, tractability, reduction

– What do we consider “feasible” for algorithms
 Week 7: P and NP (and standard algs in these classes)
– Capturing the idea of computational complexity classes
 Week 8: NP-completeness, mutual reducibility
– A large class of “hard” problems that are all interlinked
 Week 9: Graph algorithms part 2
– More general path finding techniques
 Week 10: Flow networks
– Studying the ability of networks to carry resources

55 CS260 Algorithms
CS260 Learning outcomes

From [Link] :
 Understand a variety of techniques for designing efficient
algorithms, proving their correctness, and analyzing their
efficiency
– Greedy algs, divide-and-conquer, dynamic programming…
 Understand some fundamental algorithmic problems and
algorithms for solving them
– Stable matching, sorting, closest point, scheduling, knapsack…
 Understand a variety of data structures and be able to use them
effectively to use them effectively in design and implementation
of algorithms
– We’ve seen and used arrays, lists, priority queues, graphs, matrices
56 CS260 Algorithms
A puzzle for the bored

 An odd number of
students are standing in
a field, so that all
pairwise distances are
distinct. Each student is
told to watch the
closest other student.
Show that there is some
student who is not
watched.

57 CS260 Algorithms