Dynamic Programming and Shortest Paths

A beginner's textbook for COMP 550 Midterm 2 · Chapters 4 and 5 · UNC Fall 2026

Download as PDF · Two-page cheat sheet (PDF) · Cheat sheet (web) · Midterm 1 guide

Preface

This book covers the material of COMP 550 Midterm 2: Chapter 4, dynamic programming, and Chapter 5, shortest paths. It is written for a reader who has not been following the lectures and who may be seeing dynamic programming for the first time. Nothing is assumed beyond the ability to read pseudocode and the Midterm 1 material (arrays, breadth-first search, depth-first search, topological ordering, Big-O notation); wherever a Midterm 1 idea is needed it is restated in a sentence or two at the point of use. Every algorithm is presented the same way the lectures present it, in four numbered steps, and every algorithm is run by hand on a concrete input so that you can see what the table of answers looks like. Each chapter ends with exercises whose solutions are hidden until you click, Chapters 6 and 7 are two full practice exams in the format of Midterm 1, and Chapter 8 is a one-page summary for the night before.

The source material is the instructor's handwritten lecture notes for Chapter 4 (five lectures, September 24 to October 13) and Chapter 5 (two lectures, October 20 and 22), together with Midterm 1 and its solutions, which fix the format and the grading conventions. The notes for Chapter 4 Day 2 were damaged in the export and only their first five pages could be recovered; those pages contain the complete treatment of the three topics of that day. Definitions and recurrences are quoted from the notes; explanations that go beyond the notes are marked as such.

About the exam

Everything known about the format comes from Midterm 1 and from the announcements written in the margins of the lecture notes. On Midterm 1, Problem 1 consisted of five one-point questions in which you run an algorithm by hand on a small input and write only the output, with no partial credit. Problems 2 through 5 each asked you to describe an algorithm with a stated running time, explain why it is correct, and analyze its running time, and at least two of the four were copied word for word from the problem sets. For Midterm 2 the hand-simulations will presumably be things like filling a row of a dynamic-programming table, running Bellman-Ford for a given number of rounds, or listing the order in which Dijkstra's algorithm finalizes vertices, and the design problems will be dynamic programs and shortest-path reductions. Problem Set 5 was due Thursday, October 29.

How solutions are written

Every design problem in this course is posed as an input, a goal, and a target running time, and every solution has three parts: the algorithm, a correctness argument, and a running-time analysis. Chapter 4 adds a fixed way of writing the algorithm part for a dynamic program, which the lectures number 1 through 4: define the subproblems (what OPT[i] means, and which subproblem is the answer), give the recurrence with its base cases, write the pseudocode that fills a table d in the right order, and state the running time, which is almost always the number of subproblems times the time per subproblem. The correctness argument for a dynamic program is an explanation of why the recurrence is right: the optimal solution to a subproblem must fall into one of a few cases, and the recurrence takes the best case. Section 1.7 spells this out, and every worked solution in the book follows it.

What is in scope

How to read this book

Read Chapter 1 first, slowly; it is short and everything else depends on it. Then read Chapter 2 with pencil and paper, filling in each table yourself before reading the filled-in version. Chapters 3 and 4 extend the method to two strings and to trees and can be read in either order. Chapter 5 is shortest paths; its first section is a dynamic program, so it will feel familiar, and the other two algorithms are small variations. Then take the practice exams in Chapters 6 and 7 under time pressure, and finish with Chapter 8.

Blue boxes contain definitions and recurrences to know by heart. Orange boxes describe mistakes that are easy to make and cost points. Green boxes connect a topic to how it is tested. Grey text marked "extra context" goes beyond the lecture notes.

Ch 4 · Days 1, 3, 51. Dynamic programming: the method

Dynamic programming, or DP, is the main subject of Midterm 2. The name sounds intimidating, but the idea is modest: to solve a big problem, first write down the answers to all of its smaller versions, in order from smallest to largest, and build each new answer out of the ones already written down. Everything in Chapter 4, and most of Chapter 5, is this one idea applied to different problems. This chapter teaches the idea on problems so easy that you already know how to solve them, which lets you concentrate on the method itself. Later chapters apply the same method to problems that are genuinely hard without it.

1.1 Boiling versus baking

The lecture opened with an analogy. A greedy algorithm (Chapter 3 of the Midterm 1 material) is like boiling: throw things in, pick whatever looks best at each moment, never look back. It is fast and it sometimes works. Dynamic programming is like baking: you follow a recipe exactly, you prepare every ingredient before you combine them, and you cannot skip steps, but the result is reliable. In a greedy algorithm you make one choice per step and commit to it. In a dynamic program you refuse to commit: you compute the best answer for every smaller version of the problem, and only then read off the answer to the whole thing.

Three words will be used constantly, so here is what they mean.

Optimization problem

A problem whose answer is the best (largest, smallest, cheapest, longest) of many possible candidates. "Return the maximum element of A" and "return the length of the longest increasing subsequence of A" are optimization problems.

OPT

The optimal value, that is, the correct answer. In this course OPT is written with square brackets, for example OPT[i], to mean "the correct answer to subproblem number i." OPT is a mathematical quantity, not a variable in a program.

Subproblem

A smaller version of the original problem. If the original input is an array A of length n, a typical subproblem is "the same question, but asked only about the first i elements A[1:i]." The original problem is the subproblem with i = n.

1.2 The four-step recipe

Every dynamic programming solution in this course is written in the same four steps, and the exam expects to see them. Memorize the steps now; the rest of the book is practice in carrying them out.

Step 2 is where all the thinking happens. Steps 1 and 3 are mostly bookkeeping once step 2 is right, and step 4 is usually one sentence. When you are stuck on a DP problem, the question to ask is always the same: if I already knew the answers to all the smaller subproblems, how would I get the answer to this one?

1.3 First example: the maximum of an array

You already know how to find the maximum of an array: scan it, remembering the largest value seen so far. The lecture rewrote this familiar algorithm in the four-step format so that the format itself is the only new thing.

Problem. The input is an array A of n numbers. Return the maximum element of A, that is, the maximum of A[1:n].

Step 1, subproblems. For every i from 1 to n, let OPT[i] be the maximum element of A[1:i]. The original problem is OPT[n], so we will return OPT[n].

Step 2, recurrence. The base case is OPT[1] = A[1], because the maximum of a one-element array is that element. For i from 2 to n, the maximum of A[1:i] is either the maximum of A[1:i−1] or the new element A[i], whichever is larger:

Why is the recurrence right? The largest element of A[1:i] is somewhere in A[1:i]. Either it is A[i] itself, or it is among A[1], …, A[i−1], in which case it is the largest of those, which is OPT[i−1] by definition. Taking the max of the two candidates therefore gives the correct answer. This style of justification, "the answer must come from one of these cases, and the recurrence takes the best case," is what the exam means by explaining why your algorithm is correct for a DP problem.

Step 3, pseudocode. Replace OPT by an array d and fill it from left to right, so that d[i−1] is ready when d[i] is computed.

ALG(A):                       # DP for Max in Array
  d = [A[1]] * n              # an array of length n, every entry A[1]
  for i = 2, ..., n:
    d[i] = max(d[i-1], A[i])
  return d[n]

Step 4, running time. There are n subproblems and each takes O(1) time (one comparison), so the total is n · O(1) = O(n).

Run it on A = [3, 1, 4, 1, 5]: d[1] = 3, then d[2] = max(3, 1) = 3, d[3] = max(3, 4) = 4, d[4] = max(4, 1) = 4, d[5] = max(4, 5) = 5, and the algorithm returns d[5] = 5. Notice that the array d = [3, 3, 4, 4, 5] records the running maximum; d[i] really is the maximum of A[1:i] for every i, which is exactly what step 1 promised.

1.4 Second example: the sum of an array

The lecture asked the class to repeat the exercise for the sum. Problem. Given an array A of n numbers, return the sum of A.

1. Subproblems. For every i from 1 to n, OPT[i] = the sum of A[1:i]. We will return OPT[n].
2. Recurrence. OPT[1] = A[1], and for i from 2 to n, OPT[i] = OPT[i−1] + A[i]. The sum of the first i elements is the sum of the first i − 1 elements plus the i-th element.
3. Pseudocode.

ALG(A):
  d = [A[1]] * n
  for i = 2, ..., n:
    d[i] = d[i-1] + A[i]
  return d[n]

4. Running time. n − 1 iterations, each O(1), so O(n).

The array d here is the prefix-sum array: d[i] is the sum of the first i elements. It will reappear in Chapter 2 as a tool (the Alice-and-Bob game uses suffix sums, the same idea read from the right).

1.5 Fibonacci numbers, and three ways to run a recurrence

The Fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, …: each number is the sum of the two before it. Formally F(1) = F(2) = 1 and F(n) = F(n − 1) + F(n − 2) for n ≥ 3. The problem is: given a positive integer n, return F(n). Here the recurrence is handed to you by the definition, so this problem isolates a different question: once you have a recurrence, how should you evaluate it? The lecture compared three ways.

Bottom-up (the recommended way)

Subproblems: OPT[i] = F(i) for i from 1 to n; return OPT[n]. Base cases OPT[1] = OPT[2] = 1; recurrence OPT[i] = OPT[i−1] + OPT[i−2] for i ≥ 3. Fill d from left to right:

ALG(n):                       # Bottom-up
  d = [1] * n
  for i = 3, ..., n:
    d[i] = d[i-1] + d[i-2]
  return d[n]

Running time O(n): n subproblems, O(1) each. "Bottom-up" means starting from the smallest subproblems and working up to the big one, which is what every pseudocode in this book does. The lecture recommends writing all exam solutions bottom-up.

Pure recursion (do not do this)

ALG(n):                       # Pure recursion: correct but slow
  if n <= 2: return 1
  return ALG(n-1) + ALG(n-2)

This computes the right answer, but it is exponentially slow, roughly O(2ⁿ) (more precisely O(φⁿ) with φ ≈ 1.618). The reason is repeated work. Drawing the tree of calls for ALG(6): it calls ALG(5) and ALG(4); ALG(5) calls ALG(4) and ALG(3); so ALG(4) is computed twice in full, ALG(3) three times, ALG(2) five times, and so on. Nothing is remembered between calls, so the same subproblems are solved over and over.

Top-down with memoization

Memoization means storing each intermediate result in a global array the first time it is computed, and looking it up instead of recomputing it every later time. Recursion plus memoization is called top-down DP:

d = [0] * n                   # global; d[i] = 0 means "not computed yet"
ALG(n):                       # Top-down DP (recursion + memoize)
  if n <= 2: return 1
  if d[n] != 0: return d[n]   # already known
  d[n] = ALG(n-1) + ALG(n-2)
  return d[n]

Each d[n] is computed once and then served from the array, so the running time is O(n), the same as bottom-up. Top-down and bottom-up compute exactly the same table; they differ only in the order in which entries get filled. The exam will accept either, but bottom-up pseudocode is shorter, has no recursion to get wrong, and makes the running-time analysis obvious (count the loop iterations), which is why the lecture recommends it.

Extra context beyond the notes: the lecture's tangent on the golden rectangle is the fact that the ratio F(n+1)/F(n) approaches φ = (1 + √5)/2 ≈ 1.618, the positive solution of x² = x + 1. It explains where the O(φⁿ) running time of pure recursion comes from, and it is not examinable.

1.6 Saving space

Day 5 of the chapter observed that the Max-in-Array DP stores an entire array d but only ever looks at d[i−1] when computing d[i]. So instead of an array, keep a single number:

Max(A):                       # space-saving version of the DP
  d = A[1]
  for i = 2, ..., n:
    d = max(d, A[i])
  return d

This is the usual Max-in-Array algorithm; the DP version with a full array and the one-variable version do exactly the same comparisons. The general rule is:

Saving space has two drawbacks, both named in lecture: (1) the table values are harder to interpret, and (2) it is harder to reconstruct the solution itself, not just its value, because there are no stored entries to trace back through, "no parent pointers." For the exam this is a reason to write the full-array version unless a problem specifically asks about space. Chapter 2 shows the same trick on the two-dimensional knapsack table, where it reduces the space from O(nB) to O(B), and Chapter 5 shows it on Bellman-Ford.

1.7 How a DP answer is written on the exam

Design problems on Midterm 1 asked for three things: an algorithm, an explanation of why it is correct, and a running-time analysis. For a DP problem the four steps of Section 1.2 supply all three.

Exercises

Ch 4 · Days 1–52. Dynamic programming on arrays

This chapter contains the array problems from Chapter 4, in the order the lectures introduced them, and ends with the catalog of six subproblem patterns that the lecture of October 8 drew up. The first problem, the longest increasing subsequence, is the most important: it introduces the "LIS trick," a way of choosing subproblems that is reused by half the problems in the chapter.

2.1 Longest increasing subsequence

Subsequence

A sequence obtained from A by deleting any elements you like (possibly none) and keeping the survivors in their original order. The elements need not be adjacent in A.

Increasing

Each element is strictly larger than the one before it.

Longest increasing subsequence (LIS)

An increasing subsequence of A of maximum length. There may be several; the problem asks only for the length.

The lecture's example is A = [5, 1, 2, 7, 4, 6, 3]. The sequences [5], [4], [1, 2], and [1, 2, 4] are all increasing subsequences. [3, 6] is not a subsequence, because 3 comes after 6 in A. [7, 4] is a subsequence but is not increasing. The longest increasing subsequence is [1, 2, 4, 6], of length 4, so the algorithm should return 4. The target running time is O(n²).

Why Pattern 1 fails

Try the subproblems of Chapter 1: OPT[i] = length of the LIS of A[1:i]. For the example this gives OPT = [1, 1, 2, 3, ?]. At i = 5 the new element is 4. We know that A[1:4] has an increasing subsequence of length 3, namely [1, 2, 7], but we cannot tell from the number 3 whether 4 extends it. It does not extend [1, 2, 7], but it does extend [1, 2], which is shorter. The subproblem answer has thrown away the information we need: what value the subsequence ends on.

The LIS trick: Pattern 3

The lecture calls the extra requirement the "LIS trick": define the subproblem for A[1:i] but insist that the solution somehow involves A[i]. For the example this gives OPT = [1, 1, 2, 3, 3, 4, 3]: the best subsequence ending on 7 is [1, 2, 7] (length 3), the best ending on 4 is [1, 2, 4] (length 3), the best ending on 6 is [1, 2, 4, 6] (length 4), the best ending on the final 3 is [1, 2, 3] (length 3). The answer is the maximum entry, 4, not the last entry.

Why. Look at the longest increasing subsequence ending on A[i]. Either it is just [A[i]], of length 1, or it has an element immediately before A[i]; call that element A[j]. Then j < i, A[j] < A[i] (increasing), and the part of the subsequence up to A[j] is an increasing subsequence ending on A[j], so it has length at most OPT[j]. Conversely, any increasing subsequence ending on A[j] with A[j] < A[i] can be extended by A[i]. So the best choice is to pick the j with the largest OPT[j] among those with A[j] < A[i], and add 1 for A[i] itself.

A second lecture example, with every step shown. A = [5, 2, 5, 6, 3, 7, 4, 6].

So OPT = [1, 1, 2, 3, 2, 4, 3, 4] and the algorithm returns 4.

Step 3, pseudocode. Fill d from left to right; for each i, scan all earlier j.

LIS(A):
  d = [1] * n
  for i = 2, ..., n:
    for j = 1, ..., i-1:
      if A[j] < A[i] and d[i] < 1 + d[j]:
        d[i] = 1 + d[j]
  return max(d)

Step 4, running time. There are n subproblems, and subproblem i scans i − 1 earlier entries, so each takes O(n) time; the total is n · O(n) = O(n²). (Summing 1 + 2 + ⋯ + (n − 1) gives the same answer exactly.)

Recovering the subsequence itself: parent pointers

Day 2 asked how to output an actual longest increasing subsequence rather than its length. The answer is the same device BFS uses to recover a shortest path: parent pointers. Whenever d[i] is set to 1 + d[j], also record p[i] = j, the index that d[i] was built from. At the end, let i* be an index with d[i*] = max(d); then i*, p[i*], p[p[i*]], … lists the chosen indices from last to first. Reverse it to get the subsequence. The lecture's example is A = [3, 1, 5, 2, 4, 6, 3], which gives d = [1, 1, 2, 2, 3, 4, 3] with p[3] = 1, p[4] = 2, p[5] = 4, p[6] = 5, p[7] = 4; following the pointers from index 6 gives 6 → 5 → 4 → 2, that is, the subsequence [1, 2, 4, 6].

2.2 Longest contiguous increasing subsequence

Now require the subsequence to be contiguous, a run of adjacent elements. For A = [3, 1, 2, 4, 2, 5] the longest increasing run is [1, 2, 4], so the answer is 3. The LIS trick applies again, and the recurrence becomes simpler because a run ending at A[i] can only be extended from the run ending at A[i−1].

For the example, OPT = [1, 1, 2, 3, 1, 2]. Pseudocode: d = [1]*n; for i = 2..n: if A[i] > A[i−1]: d[i] = d[i−1] + 1; return max(d). Each subproblem now takes O(1), so the running time is O(n). The lesson is that the pattern (Pattern 3) stays the same while the recurrence, and hence the running time, depends on the problem.

2.3 Minimum-cost jumps

Problem (Day 3). The input is an array A of n positive integers, with n ≥ 2. You start at position 0, just before the array, and want to reach position n + 1, just after it. Each jump moves 1 or 2 positions to the right, and landing on position i costs A[i]. Return the minimum total cost. For A = [1, 10, 1]: jump to position 1 (cost 1), jump two to position 3 (cost 1), jump out; total 2. Target O(n).

Subproblems with the LIS trick: for i from 1 to n, OPT[i] = the minimum cost of a sequence of jumps that lands on and stops at position i. The lecture asked, as an exercise, why "OPT[i] = min cost given A[1:i]" would not work: to extend a sequence of jumps you need to know where it currently stands, and a subproblem about A[1:i] that does not say where it stops cannot be extended.

Why. The last jump onto position i came from position i − 1 or i − 2, and before that jump the path had landed on and stopped at that position with cost at least OPT of it; the cheaper of the two, plus A[i], is optimal.

ALG(A):
  d = [0] * n
  d[1] = A[1]; d[2] = A[2]
  for i = 3, ..., n:
    d[i] = A[i] + min(d[i-2], d[i-1])
  return min(d[n-1], d[n])

n subproblems, O(1) each: O(n). For A = [1, 10, 1], d = [1, 10, 2] and the answer is min(10, 2) = 2. Since d[i] uses only the two previous entries, the space-saving trick of Section 1.6 applies.

2.4 Best time to buy and sell a stock

Problem (Day 5). A[i] is the price of a stock on day i. You buy on some day i and sell on a later day j > i; return the maximum possible profit A[j] − A[i]. For A = [3, 5, 1, 2, 7, 4] the answer is 7 − 1 = 6. Trying all pairs costs O(n²); the target is O(n).

Subproblems with the LIS trick: for j from 2 to n, OPT[j] = the maximum profit given A[1:j] if we must sell on day j. Then OPT[j] = A[j] − min(A[1:j−1]): sell at today's price, having bought at the cheapest earlier price. We return max(OPT). Computing min(A[1:j−1]) from scratch for every j costs O(j) each and O(n²) in total, which is the trap. The fix is to carry the running minimum along, which is itself a tiny prefix DP (Exercise 1.2).

ALG(A):
  min_A = A[1]
  d = [0] * n
  for j = 2, ..., n:
    d[j] = A[j] - min_A
    min_A = min(min_A, A[j])
  return max(d[2], ..., d[n])

For the example the running minimum before days 2, …, 6 is 3, 3, 1, 1, 1, so d = [–, 2, −2, 1, 6, 3] and the answer is 6. Running time O(n). The space-saving version keeps only ans = max(ans, A[j] − min_A) and returns ans.

2.5 Longest palindromic subsequence: Pattern 4

A palindrome reads the same forwards and backwards: a, aa, aba, racecar are palindromes; ab is not. Problem (Day 2). The input is a string A of length n; return the length of the longest subsequence of A that is a palindrome. For A = acbcbda the answer is 5, achieved by acbca (positions 1, 2, 3, 4, 7) and also by abcba (positions 1, 3, 4, 5, 7). Target O(n²).

Prefix subproblems do not work here, because a palindrome is built from both ends inward: deciding whether the first and last characters can be matched requires a subproblem that has a first and a last character. The lecture's Pattern 4 uses subproblems indexed by an interval.

Why. Consider the longest palindromic subsequence of A[i:j]. If it uses both A[i] and A[j], those two characters are its first and last and must be equal, and what lies between them is a palindromic subsequence of A[i+1:j−1], of length at most OPT[i+1][j−1]; conversely any palindromic subsequence of A[i+1:j−1] can be wrapped in the matching pair, gaining 2. If it does not use A[i], it is a palindromic subsequence of A[i+1:j]; if it does not use A[j], it is one of A[i][j−1]. When A[i] = A[j] the first option is at least as good as the others, which is why the recurrence takes it directly. (Edge case: when j = i + 1 and the two characters match, 2 + OPT[i+1][i] = 2 + 0 = 2, using the convention for an empty interval.)

The table and the order of filling it

Rows are i, columns are j, and only cells with i ≤ j are used (the upper triangle). The cell (i, j) depends on (i+1, j−1), the cell diagonally below-left, (i+1, j), the cell below, and (i, j−1), the cell to the left. So the rows must be filled from the bottom row upward, each row from left to right. Here is the table for A = acbcbda, with the diagonal of 1s as the base case:

Some cells worked out: (2, 4) is cbc; c = c, so 2 + OPT[3][3] = 3. (1, 4) is acbc; a ≠ c, so max(OPT[2][4], OPT[1][3]) = max(3, 1) = 3. (2, 6) is cbcbd; c ≠ d, so max(OPT[3][6], OPT[2][5]) = max(3, 3) = 3. (1, 7), the answer: a = a, so 2 + OPT[2][6] = 5. The lecture's second example, A = abaca, gives first row [1, 1, 3, 3, 3] and answer 3 (aba or aca).

LPS(A):
  d = n x n table, all 0
  for i = 1, ..., n: d[i][i] = 1
  for i = n-1, ..., 1:                   # bottom row first
    for j = i+1, ..., n:                 # left to right
      if A[i] = A[j]: d[i][j] = 2 + d[i+1][j-1]
      else:           d[i][j] = max(d[i+1][j], d[i][j-1])
  return d[1][n]

Running time. About n²/2 subproblems, O(1) each: O(n²).

2.6 The 0/1 knapsack problem: Pattern 5

Problem (Day 2). There are n items; item i has value v[i] and weight w[i], all positive integers, and the knapsack has capacity B, a positive integer. Choose a set of items of total weight at most B so that the total value is as large as possible, and return that value. Each item is either taken whole or not at all, hence "0/1." For v = [4, 2, 3, 5], w = [3, 1, 2, 2], B = 5 the answer is 10, from items 2, 3, 4 (weight 1 + 2 + 2 = 5, value 2 + 3 + 5).

This is the problem that the greedy "best value per unit weight" rule of Midterm 1 solves only when items may be taken fractionally. For whole items greedy fails (Midterm 1 had the counterexample v = [4, 4, 7], w = [5, 5, 6], B = 10). The dynamic program succeeds because its subproblems record not only which items have been considered but also how much capacity is left.

Why. An optimal solution for items 1..i and capacity j either does not use item i, in which case it is an optimal solution for items 1..i−1 and capacity j, or uses item i, in which case the remaining items form an optimal solution for items 1..i−1 with the capacity j − w[i] that is left over, and the value gains v[i]. The second option is only available when w[i] ≤ j. The recurrence takes the better of the two.

Rows are items, columns are capacities. Each cell looks at the cell directly above it and at the cell in the row above, w[i] columns to the left.

For instance OPT[2][4] = max(OPT[1][4], 2 + OPT[1][3]) = max(4, 6) = 6, and OPT[4][5] = max(OPT[3][5], 5 + OPT[3][3]) = max(7, 10) = 10.

Knapsack(v, w, B):
  d = n x (B+1) table, all 0           # columns 0..B
  for j = 1, ..., B: if w[1] <= j: d[1][j] = v[1]
  for i = 2, ..., n:
    for j = 1, ..., B:
      d[i][j] = d[i-1][j]
      if w[i] <= j: d[i][j] = max(d[i][j], v[i] + d[i-1][j - w[i]])
  return d[n][B]

Running time. n(B + 1) subproblems, O(1) each: O(nB). Extra context beyond the notes: O(nB) depends on the numerical value of B, not only on the number of items, so it is fast when the capacity is small and slow when it is huge; this is sometimes called pseudo-polynomial. The exam only needs O(nB).

Unbounded knapsack

Day 2's second problem: each item may be taken any number of times. Two changes. The base row becomes OPT[1][j] = k · v[1] where k is the largest integer with k · w[1] ≤ j (take as many copies of item 1 as fit). And in the "take item i" option, item i stays available afterwards, so OPT[i−1][j − w[i]] becomes OPT[i][j − w[i]]: OPT[i][j] = max( OPT[i−1][j], v[i] + OPT[i][j − w[i]] ). Still O(nB).

Saving space

Day 5 pointed out that row i of the 0/1 table depends only on row i − 1, so two arrays of length B + 1 suffice in place of the n × (B + 1) table, reducing space from O(nB) to O(B). Even one array works, provided that within each row j is processed from B down to 0: d[j] needs the old value of d[j − w[i]], which has not been overwritten yet when moving right to left. Processing left to right would instead use the already-updated d[j − w[i]], which allows item i to be taken again, and computes the unbounded knapsack. This is the lecture's one-line summary: right to left solves 0/1; left to right solves unbounded.

2.7 The Alice-and-Bob game: Pattern 2

Problem (Day 5). The input is an array A of n ≥ 3 positive integers. Alice and Bob alternate turns, Alice first. On a turn the player removes 1, 2, or 3 numbers from the left end of A and adds them to their score. Both play optimally, each maximizing their own total. Return Alice's maximum possible score. For A = [4, 1, 5, 2, 3, 10, 1, 2] the answer is 18. Target O(n).

The game is always played on a suffix A[i:n] of the original array, which suggests Pattern 2: subproblems indexed by suffixes.

Let S[i] = A[i] + A[i+1] + ⋯ + A[n] be the suffix sum, with S[n+1] = 0. If the current player takes k numbers (k = 1, 2, 3), they score A[i] + ⋯ + A[i+k−1] = S[i] − S[i+k], and then the opponent moves on A[i+k:n] and, playing optimally, gets OPT[i+k] out of the S[i+k] that remains; everything the opponent does not take eventually comes back to the current player, who therefore also gets S[i+k] − OPT[i+k].

The table is filled from i = n down to 1, because each subproblem needs larger indices. The suffix sums S are precomputed in O(n) by S[n] = A[n], S[i] = A[i] + S[i+1]; computing each sum from scratch inside the recurrence would make the algorithm O(n²), which the lecture called the naive version.

For example OPT[5] = 16 − min(OPT[6], OPT[7], OPT[8]) = 16 − 2 = 14 (take 3, 10, 1 and leave Bob the 2), and OPT[1] = 28 − min(14, 10, 15) = 18 (Alice takes 4 and 1, leaving Bob the position worth only 10 of the remaining 23).

ALG(A):
  S = [0] * (n+1); S[n] = A[n]
  for i = n-1, ..., 1: S[i] = A[i] + S[i+1]
  d = [0] * n
  d[n] = S[n]; d[n-1] = S[n-1]; d[n-2] = S[n-2]
  for i = n-3, ..., 1:
    d[i] = S[i] - min(d[i+1], d[i+2], d[i+3])
  return d[1]

Running time. O(n) to compute S, then n subproblems at O(1) each: O(n).

2.8 The six subproblem patterns

On October 8 the lecture collected the kinds of subproblems seen so far. The three starred ones were singled out as the most important.

Exercises

Ch 4 · Days 3–43. Dynamic programming on two strings: edit distance

The previous chapter used one-dimensional tables: one entry per prefix of a single array. This chapter introduces the two-dimensional table, which is needed when the input consists of two sequences and a subproblem must say how much of each has been used. The example is edit distance, which the lecture treated in detail on two separate days and which is the most important single algorithm of Chapter 4 for exam purposes: it is the model for every "two strings" or "two arrays" DP.

3.1 The problem

The story, from lecture, is spell-checking and genetics: how far apart are two words, or two DNA sequences? The input is two strings, A of length m and B of length n. You may change A using three kinds of moves:

1. Insert any character anywhere in A.
2. Delete any character from A.
3. Replace any character of A with any character.

The edit distance ED(A, B) is the minimum number of moves needed to turn A into B. The goal is to return ED(A, B). The lecture's examples: ED(cat, bat) = 1 (replace c with b), ED(cat, cats) = 1 (insert s), ED(cat, bar) = 2 (replace c, replace t), ED(cat, dog) = 3 (replace every letter). The running-time target is O(mn).

3.2 Subproblems: Pattern 6

A subproblem must record how much of A and how much of B have been accounted for, so it needs two indices.

This is Pattern 6 in the lecture's catalog: the input is a pair (A, B) and OPT[i][j] is the answer for the pair of prefixes (A[1:i], B[1:j]). There are (m + 1)(n + 1) subproblems, arranged in a table with m + 1 rows (one per prefix of A, including the empty one) and n + 1 columns.

Base cases. OPT[0][j] = j, because turning the empty string into B[1:j] requires inserting all j characters and nothing less works. Symmetrically OPT[i][0] = i: the only way to turn A[1:i] into the empty string is to delete all i characters.

3.3 The recurrence: three ways to handle the last character

The lecture's running example is A = star, B = water. Fix a subproblem with i, j ≥ 1, say turning "star" into "wate" (i = 4, j = 4). Think about what the last thing is that any sequence of moves does to produce the final character "e" of the target. There are exactly three possibilities:

1. Turn star into wat (cost OPT[4][3]) and then insert e at the end. Total OPT[i][j−1] + 1.
2. Turn sta into wate (cost OPT[3][4]) and then delete the leftover r. Total OPT[i−1][j] + 1.
3. Turn sta into wat (cost OPT[3][3]) and then deal with the last characters r and e directly: replace r with e, costing 1. Total OPT[i−1][j−1] + 1. If the last characters had been equal, as with star → water where both end in r, this step would cost nothing: star → water is the same as sta → wate.

In the table, the three terms are the cell to the left, the cell above, and the cell diagonally up-left. So each cell is the minimum of its three neighbors plus 1, except that the diagonal neighbor contributes +0 when the row's character equals the column's character. The lecture also noted a shortcut: if A[i] = B[j], then OPT[i][j] = OPT[i−1][j−1]; when the last characters already agree, you never need to touch them, so you may copy the diagonal entry without taking a min.

Why the recurrence is correct. Take any optimal way of turning A[1:i] into B[1:j] and look at what happens to the last character of the target B[j]. Either it was inserted (case 1), or it came from A[i] (unchanged or replaced, case 3), or A[i] was deleted and B[j] came from an earlier character (case 2). These cases cover every possibility, each case costs exactly what the corresponding term says plus an optimal solution of the smaller subproblem, and the minimum of the three is therefore the optimum. The base cases are correct because inserting or deleting every character is forced when one string is empty.

3.4 Filling the table

Rows are prefixes of A = star, columns are prefixes of B = water. The first row and first column are the base cases 0, 1, 2, …; every other cell is the minimum of (left + 1, up + 1, diagonal + δ). Fill row by row, left to right, so that all three neighbors are ready.

Some cells, worked out loud. Cell (s, w): left is 1, up is 1, diagonal is 0 and s ≠ w so δ = 1; the minimum of 2, 2, 1 is 1 (replace s with w). Cell (t, t), shown in bold: the characters match, so copy the diagonal cell (s, a) = 2; indeed "st" → "wat" costs 2 (replace s with w, insert a). Cell (a, a): match, copy the diagonal (t, w) = 2. Cell (r, a): left 4 + 1, up 2 + 1, diagonal 3 + 1 (r ≠ a); the minimum is 3. Cell (r, r), the answer: match, copy the diagonal (a, e) = 3. So ED(star, water) = 3; one optimal sequence of moves is star → wtar → watar → water (replace s with w, insert a, replace the second a with e).

3.5 Pseudocode and running time

Edit-Distance(A, B):               # |A| = m, |B| = n
  d = (m+1) x (n+1) table
  for i = 0, ..., m: d[i][0] = i
  for j = 0, ..., n: d[0][j] = j
  for i = 1, ..., m:
    for j = 1, ..., n:
      delta = 0 if A[i] = B[j] else 1
      d[i][j] = min(d[i][j-1] + 1, d[i-1][j] + 1, d[i-1][j-1] + delta)
  return d[m][n]

Running time. There are (m + 1)(n + 1) = O(mn) subproblems and each takes O(1) time (a comparison and a minimum of three numbers), so the total is O(mn). The lecture's slogan applies exactly: number of subproblems times time per subproblem.

Order of evaluation. The double loop fills the table row by row. Any order works as long as the left, upper, and diagonal neighbors of a cell are filled before the cell itself; column by column is also fine. This is the two-dimensional version of "fill d from left to right."

3.6 Recovering the moves, not just the number

The table stores only costs. To recover an actual sequence of moves, start at the bottom-right cell and walk backward: at cell (i, j), find which of the three neighbors achieved the minimum, record the corresponding move (insert B[j], delete A[i], or replace/keep), and step to that neighbor; stop at (0, 0). Each step moves at least one index down, so this takes O(m + n) time after the table is built. The lecture called such stored choices parent pointers; the space-saving version of a DP (Section 1.6) throws away exactly the information this walk needs, which is why saving space makes reconstruction hard.

3.7 Variants built on the same table

Exam problems like to change the rules slightly and ask for the new recurrence. The table and the running time do not change; only the three terms do.

• Different move costs. If an insertion costs c_ins, a deletion c_del, and a replacement c_rep, the recurrence becomes min(OPT[i][j−1] + c_ins, OPT[i−1][j] + c_del, OPT[i−1][j−1] + c_rep·δ_ij), with base cases OPT[0][j] = j·c_ins and OPT[i][0] = i·c_del.
• No replacements allowed. Drop the diagonal term unless A[i] = B[j]: OPT[i][j] = min(OPT[i][j−1] + 1, OPT[i−1][j] + 1) when the characters differ, and OPT[i−1][j−1] when they agree.
• Longest common subsequence (LCS). Extra context beyond the notes, included because it is the standard companion to edit distance. A subsequence is obtained by deleting characters (not necessarily adjacent ones) without reordering. To find the length of the longest string that is a subsequence of both A and B, use the same subproblems OPT[i][j] = LCS length of A[1:i] and B[1:j], with base cases OPT[0][j] = OPT[i][0] = 0, and recurrence OPT[i][j] = OPT[i−1][j−1] + 1 if A[i] = B[j], and max(OPT[i−1][j], OPT[i][j−1]) otherwise. Running time O(mn).

Exercises

Ch 4 · Days 4–54. Dynamic programming on trees

The last two lectures of Chapter 4 moved from arrays to trees. The method is unchanged, but the subproblems are now subtrees instead of prefixes, and the order in which the table is filled is "children before parents" instead of "left to right." Two problems were treated: the maximum-weight independent set, which is the model problem, and the maximum-weight matching, which was set as a worksheet.

4.1 Trees as input

In this chapter a tree is a connected graph with no cycles, rooted at vertex 1. Rooting the tree gives every edge a direction, away from the root, and gives every vertex other than the root a unique parent; the vertices just below u are its children. A vertex with no children is a leaf. The tree is given as an array T where T[u] is the list of u's children (an adjacency list that only records edges going downward). The subtree rooted at u, written T(u), consists of u together with all of its descendants. A tree with n vertices has exactly n − 1 edges, so anything that costs O(m + n) on a tree costs O(n).

Trees are friendly to dynamic programming because of one fact: the subtrees of the different children of u do not touch each other. There is no edge between a vertex in T(v₁) and a vertex in T(v₂) when v₁ and v₂ are distinct children of u. So a decision made inside one child's subtree never affects another child's subtree, and the subproblems "answer for T(v)" can be combined independently at u.

4.2 Maximum-weight independent set

An independent set in a graph is a set S of vertices such that no edge has both of its endpoints in S: no two chosen vertices are adjacent. Problem (Day 4). The input is a tree T rooted at 1 in which every vertex u has a weight w[u] > 0. Return the maximum possible total weight Σ_u∈S w[u] of an independent set S. (The lecture abbreviates "maximum independent set" as MIS.)

In the lecture's first example above, the weights are 3 at the root, 2, 2, 5 at its children, 4 below the first child and 1 below the second. Taking the root (3) forbids all three of its children, leaving 3 + 4 + 1 = 8. Better is to skip the root: take the vertex of weight 5, the vertex of weight 4 (which forbids its parent of weight 2), and the other child of weight 2 (which forbids the leaf of weight 1), for 5 + 4 + 2 = 11, which is optimal.

Why one number per vertex is not enough

The first attempt in lecture was the natural subproblem OPT[u] = weight of the maximum independent set in T(u). It was crossed out. The trouble appears when combining at u: if u is put into S, then no child of u may be in S, but the number OPT[v] for a child v does not tell us whether the set it describes uses v. We need to know the best set in T(v) that avoids v, and the best overall. So the lecture kept two numbers per vertex.

Why. If u is in S, none of its children can be, so within each child's subtree the best we can do is the best set that excludes the child, and the subtrees are independent of each other, so the totals add. If u is not in S, each child's subtree may do whatever is best for it, with or without the child, and again the totals add. The leaf cases are immediate. Every independent set of T(u) either contains u or does not, so the two values cover every possibility, and the answer for the whole tree is the better of the two at the root.

A worked example

This is the lecture's larger example. Each vertex is labelled with its number, and the weight is written beside it. Working upward from the leaves, the pair (OPT_in, OPT_out) at each vertex is:

The answer is max(19, 21) = 21. To see which vertices achieve it, walk back down: the root is out; child 2 is in (10 > 6), so 5 and 6 are out and then 7 and 8 are in; child 3 is out (8 > 5), so 9 and 10 are free and both are in, forcing 11 out; child 4 is a tie, and taking it out gives 12 and 13. The set {2, 7, 8, 9, 10, 12, 13} has weight 5 + 3 + 2 + 3 + 5 + 1 + 2 = 21.

4.3 The order of computation and the running time

Each recurrence uses the values of u's children, so every child must be computed before its parent. The lecture's phrase for this is "sort V in reverse topological order": if you think of each edge as pointing from parent to child, a topological ordering lists every parent before its children, and the reverse of it lists every child before its parent. In practice any of the following produces such an order in O(n) time: run DFS from the root and take the vertices in order of their post values (a vertex finishes after all of its descendants); or run BFS from the root, record the order in which vertices are discovered, and reverse it (a child is always discovered after its parent).

MIS-Tree(T, w):
  L = the vertices of T in an order with every child before its parent   # e.g. reverse BFS order
  d_in = [0] * n; d_out = [0] * n
  for u in L:
    d_in[u] = w[u]
    for v in T[u]:
      d_in[u]  = d_in[u]  + d_out[v]
      d_out[u] = d_out[u] + max(d_in[v], d_out[v])
  return max(d_in[1], d_out[1])

For a leaf the inner loop does nothing, so d_in[u] = w[u] and d_out[u] = 0, which are the base cases. Running time. Computing the order is a BFS or DFS on a graph with n − 1 edges, O(n). The loop over children costs O(1) per child, and every vertex except the root is the child of exactly one vertex, so the loops cost O(n) in total. The whole algorithm is O(n), which the lecture summarized as "≈ BFS."

4.4 A single array, using grandchildren

Day 5 returned to the crossed-out subproblem and showed it can be made to work after all, by looking two levels down. Let OPT[u] be the weight of the maximum independent set of T(u). Either u is out, and each child's subtree is free, or u is in, and then each child is out but each grandchild's subtree is free:

Running time is still O(n): the triple loop "for u; for v in T[u]; for x in T[v]" visits every vertex once as a child and once as a grandchild, so about 2n steps in total. Both formulations are acceptable; the two-array version is easier to explain and extends more easily to other problems, which is why the exam solutions in this book use it.

4.5 Maximum-weight matching in a tree

A matching is a set F of edges such that no two edges in F share an endpoint. Problem (Day 5 worksheet). The input is a tree rooted at 1 in which every edge e has a weight w(e) > 0; return the maximum total weight of a matching.

In the figure, edges are labelled with their weights. The best matching takes the edges of weight 3 (root to its right child), 4 (vertex 2 to vertex 5), and 2 (vertex 8 to vertex 9), for a total of 9; no two of these share a vertex.

Why. In a matching of T(u), vertex u is matched to at most one child. If it is matched to none, every child's subtree is free (OPT_out[u]). If it is matched to child v by the edge (u, v), that edge contributes w(u, v); v is now used, so inside T(v) only matchings that leave v unmatched are allowed (OPT_out[v]); and every other child x of u has a free subtree (OPT[x]). Taking the best over the choice of v, and comparing with matching nobody, covers every case.

Running time, and the trick that makes it O(n). Evaluated literally, the sum Σ_{x ≠ v} OPT[x] costs O(number of children) for each candidate v, so a vertex with k children costs O(k²), which is O(n²) for a star-shaped tree. The lecture's fix is to notice that Σ_{x ≠ v} OPT[x] = OPT_out[u] − OPT[v], which is O(1) once OPT_out[u] is known. So compute OPT_out[u] first, then OPT[u] = max( OPT_out[u], max_v [ w(u, v) + OPT_out[v] + OPT_out[u] − OPT[v] ] ), which costs O(k) at a vertex with k children and O(n) in total.

Worked example

OPT[1] = 9. At the root the winning option matches 1 to 3 (weight 3), leaves 3 unmatched below (OPT_out[3] = 2, the edge 8–9), and takes the best matching of T(2), which is the edge 2–5 of weight 4.

4.6 A remark on general graphs

The lecture ended with a tangent: for an independent set in a general graph, not a tree, no polynomial-time algorithm is known, and the question of whether one exists is the P versus NP problem. The tree structure is what makes the dynamic program possible, because it is what makes the children's subproblems independent. On the exam, if a problem gives you a tree, expect a DP of this shape; if it gives you an arbitrary graph and asks for an independent set, something else is going on.

Exercises

Ch 5 · Days 1–25. Shortest paths

Chapter 5 of the course is about finding shortest paths in a directed graph whose edges have lengths. The lecture introduced it as "four sections, three of which are dynamic programming," and the first two algorithms in this chapter are indeed dynamic programs in exactly the sense of Chapter 1, with the vertices as subproblems. The third, Dijkstra's algorithm, is a greedy algorithm in the style of Prim's. Which algorithm applies depends on what the edge lengths are allowed to be, so keep track of the assumptions as you read.

5.1 The single-source shortest path problem

Edge length

Every edge e = (u, v) has a number ℓ(e) = ℓ(u, v), its length (also called its weight). Unless a section says otherwise, lengths may be positive, zero, or negative.

Length of a path

The sum of the lengths of its edges. A path with no edges has length 0.

Distance

The distance from s to v is the smallest length of any path from s to v; it is ∞ if v cannot be reached from s.

Walk

Like a path, but vertices and edges may repeat. Bellman-Ford reasons about walks.

From Midterm 1 you know one algorithm for this problem already: breadth-first search computes d[v] = the number of edges on a shortest path, which is the distance when every edge has the same positive length. The lecture lists it as section 2.1 and notes that it "works when all ℓ(e) are the same and > 0." The three new algorithms handle more general lengths.

5.2 Shortest paths in a DAG by dynamic programming

A DAG is a directed graph with no cycles. Recall from Midterm 1 that a DAG has a topological ordering, a listing of the vertices in which every edge goes from an earlier vertex to a later one, and that Topological-Sort finds one in O(m + n) time. The lecture's section 5.1 is the shortest-path problem on a DAG, with lengths that "can be anything," including negative.

Why. A shortest path from s to v, if v ≠ s, has a last edge (u, v) for some in-neighbor u. The part of the path before that edge is a path from s to u, whose length is at least the distance OPT[u]; so the shortest path to v has length at least min_u(OPT[u] + ℓ(u, v)). Conversely, for each in-neighbor u, a shortest path to u followed by the edge (u, v) is a path to v of length OPT[u] + ℓ(u, v). So the minimum is exactly the distance.

Why a DAG makes it work. The recurrence for OPT[v] needs OPT of the in-neighbors of v. In a DAG, every in-neighbor of v comes before v in a topological ordering, so if we process vertices in that order, all the values needed for v are ready when v is reached. There is no circularity. (In a graph with a cycle, OPT[v] might depend on OPT[u], which depends on OPT[v]; that is the problem Bellman-Ford solves.)

Step 3. To enumerate the in-neighbors of v we need the reverse graph G^R, in which every edge is flipped: G^R[v] lists the u with (u, v) ∈ E. It is built in O(m + n) time by scanning every list once: for each u, for each v in G[u], append u to G^R[v].

DAG-DP(G, s):                          # shortest paths in a DAG
  d = [infinity] * n; d[s] = 0
  topologically sort V
  G_R = reverse of G
  for v in V, in topological order:
    for u in G_R[v]:
      d[v] = min(d[v], d[u] + l(u, v))
  return d

Step 4. Topological sorting is O(m + n), building G^R is O(m + n), and the double loop scans each reversed adjacency list once, O(m + n). Total O(m + n), the same as BFS. Note that vertices placed before s in the topological order, and vertices unreachable from s, keep d = ∞, which is correct.

A worked example

Let s = 1. A topological ordering is 1, 3, 2, 4, 5, 6 (vertex 2 must come after 3 because of the edge (3, 2)). Processing in that order:

So d = [0, 3, 2, 0, 1, 0]. The shortest path to 6 is 1 → 3 → 2 → 4 → 5 → 6, of length 2 + 1 − 3 + 1 − 1 = 0.

Two variations from lecture

Longest paths in a DAG. Does the same logic find the longest path from s to each vertex? Yes: OPT[v] = max_u(OPT[u] + ℓ(u, v)), with d initialized to −∞ and d[s] = 0, in the same topological order, in O(m + n) time. The argument is identical with "longest" in place of "shortest." This works only because a DAG has no cycles; see Section 5.6.

Widest paths. Suppose every edge has a positive weight w(e), and define the width of a path to be the smallest weight of any edge on it (the "bottleneck"). We want, for every v, the maximum width of any s→v path. Subproblems OPT[v] = that maximum width, with OPT[s] = ∞ (no edge to be a bottleneck); recurrence OPT[v] = max_u min(OPT[u], w(u, v)), because a path to v through its last edge (u, v) has width min(width of the part to u, w(u, v)), and the part to u should be as wide as possible. Pseudocode: d = [0]*n, d[s] = ∞, and in topological order, for u in G^R[v]: d[v] = max(d[v], min(d[u], w(u, v))). O(m + n).

On the DAG above (same shape, all weights positive), the widest-path values from s = 1 in the order 1, 3, 2, 4, 5, 6 are ∞, 2, 4, 3, 2, 2: for instance d[2] = max(min(∞, 4), min(2, 1)) = 4 and d[4] = max(min(4, 3), min(2, 5)) = 3. The longest-path values are 0, 2, 4, 7, 8, 9.

5.3 Bellman-Ford

Now let G be any directed graph, with cycles allowed and negative lengths allowed, subject to one condition: G has no negative cycle, that is, no cycle whose total length is negative. If a negative cycle were reachable from s, walking around it again and again would make walks of arbitrarily negative length, and "distance" would make no sense.

Above, the cycle 2 → 3 → 2 has length −3 + 1 = −2, so there is no shortest walk from 1 to 2 or 3. Bellman-Ford assumes nothing of the kind exists.

Why the DAG recurrence breaks

The recurrence OPT[v] = min_u(OPT[u] + ℓ(u, v)) is still a true statement about distances when there is no negative cycle, but it can no longer be evaluated, because on a cycle the subproblems depend on each other in a circle (the lecture's example was a cycle 5 → 7 → 3 → 5): there is no order in which every in-neighbor is done first. The lecture crossed the recurrence out "because of cycles." The repair is the standard one for a circular recurrence: add a second index that always decreases.

Why n − 1 edges suffice. Since there are no negative cycles, removing a cycle from a walk never makes it shorter, so some shortest walk to v is a path with no repeated vertices, which has at most n − 1 edges. Hence OPT[v][n − 1] is the true distance.

Why. The shortest walk to v with at most j edges either uses at most j − 1 edges (first term), or uses exactly j edges, in which case it ends with some edge (u, v) and the walk before it reaches u with at most j − 1 edges, so it costs at least OPT[u][j − 1] + ℓ(u, v); conversely each such combination is a walk to v with at most j edges. The two indices make the dependence acyclic: column j depends only on column j − 1, so the columns are filled left to right.

The table

Rows are vertices, columns are j = 0, 1, …, n − 1. Column 0 is 0 at s and ∞ elsewhere; each later column is computed from the previous one; the last column is the answer. The lecture's Day 1 example, with s = 1, is this graph:

Column 1: 2 is reached by the edge (1, 2) of length 4, 4 by (1, 4) of length 5, and 3 is not reachable with one edge. Column 2: OPT[2][2] = min(4, OPT[4][1] − 3) = 2 using 1 → 4 → 2; OPT[3][2] = min(∞, OPT[2][1] − 1, OPT[4][1] + 2) = 3. Column 3: OPT[3][3] = min(3, OPT[2][2] − 1, OPT[4][2] + 2) = 1 using 1 → 4 → 2 → 3. Column 3 is returned: d = [0, 2, 1, 5].

Bellman-Ford(G, s):
  d = n x n table, all infinity; d[s][0] = 0       # columns 0 .. n-1
  G_R = reverse of G
  for j = 1, ..., n-1:
    for v in V:
      d[v][j] = d[v][j-1]
      for u in G_R[v]:
        d[v][j] = min(d[v][j], d[u][j-1] + l(u, v))
  return column n-1 of d

Step 4, running time. There are n − 1 columns, and filling one column scans every reversed adjacency list once, O(m + n). Assuming the graph is connected (in the undirected sense), m ≥ n − 1, so O(m + n) = O(m) and the total is O(mn). The lecture wrote this as "n columns, each takes O(m + n) = O(m)."

The space-saving version and edge relaxation

Each column depends only on the previous one, so by Section 1.6 the table can be replaced by a single array that is updated in place. Day 2 gave this version, which is the form of Bellman-Ford found in most textbooks:

Bellman-Ford-2(G, s):                 # space-saving version
  d = [infinity] * n; d[s] = 0
  for j = 1, ..., n-1:
    for each edge (u, v) in E:        # i.e. for u in V: for v in G[u]
      d[v] = min(d[v], d[u] + l(u, v))     # "relax (u, v)"
  return d

The update d[v] = min(d[v], d[u] + ℓ(u, v)) is called relaxing the edge (u, v); the intuition, in the lecture's words, is "check if we can improve d[v] through d[u]." The space-saving version needs no reverse graph: it just visits every edge once per round by scanning all the adjacency lists. It is still O(mn): n − 1 rounds of O(m + n).

Extra context beyond the notes: if a negative cycle is reachable from s, then even after n − 1 rounds some edge can still be relaxed. Running one extra round and checking whether any d[v] changes therefore detects reachable negative cycles in O(m) additional time.

5.4 Dijkstra's algorithm

Dijkstra's algorithm assumes all lengths are nonnegative, ℓ(e) ≥ 0, and in exchange is faster than Bellman-Ford. The lecture introduced it as "≈ Prim's": like Prim's algorithm for minimum spanning trees, it grows a set S of finished vertices outward from the start, one vertex per step, always choosing the vertex that is currently closest.

Dijkstra(G, s):
  d = [infinity] * n; d[s] = 0
  S = empty set
  while |S| < n:
    u = the vertex in V \ S with the smallest d[u]
    add u to S
    for v in G[u]:                             # relax every edge leaving u
      d[v] = min(d[v], d[u] + l(u, v))
  return d

So each step finalizes one vertex u (its d[u] never changes again) and relaxes the edges leaving it. Vertices never reached keep d = ∞ and are added to S last, which changes nothing.

A worked example

This is the lecture's example with s = 1. The table shows d after each step; the chosen vertex is in bold.

The vertices are finalized in the order 1, 2, 3, 4, 5, and d = [0, 3, 4, 6, 7]. Notice d[4] was improved twice, from 10 to 7 to 6, before vertex 4 was chosen; once chosen, it is final.

Why it is correct

Extra context beyond the notes, which stated the algorithm without a proof: when u is chosen, d[u] is the length of some s→u path that stays inside S until its last edge. Any other s→u path must leave S at some first edge (x, y) with x in S and y outside; its length is at least d[y] (because (x, y) was relaxed when x was added) which is at least d[u] (u had the smallest d outside S), and the rest of the path only adds nonnegative lengths. So no path to u is shorter than d[u]. This argument fails if an edge can be negative, which is why Dijkstra requires ℓ(e) ≥ 0: with edges (1, 2) of length 1, (1, 3) of length 3, and (3, 2) of length −5, Dijkstra finalizes d[2] = 1 at step 2, but the distance is 3 − 5 = −2.

Why not just use Prim's algorithm?

Both algorithms grow a tree from vertex 1 by repeatedly adding one vertex, so the lecture asked whether the minimum spanning tree is a tree of shortest paths. It is not. In the graph above (undirected, so each edge may be used in either direction), the minimum spanning tree is the path 1–2–3–4 of total weight 3, but the shortest path from 1 to 4 is the direct edge of length 2, whereas the tree path has length 3. Prim's rule picks the lightest edge leaving S; Dijkstra's rule picks the vertex with the smallest total distance d[u] = d[x] + ℓ(x, u), which is a different quantity.

Running time

With arrays. The set S can be stored as a 0/1 array ("add u to S" means S[u] = 1), and the minimum can be found by scanning the d array. There are n iterations, each scanning n entries, O(n²) in total, plus one relaxation per edge over the whole run, O(m). Since m ≤ n², the total is O(n²).

With a heap. Instead of scanning d for the minimum in every iteration, keep the unfinished vertices in a priority queue implemented as a heap, a binary tree in which every node's key (its d-value) is at most its children's keys, so the minimum sits at the top. In a heap, finding and removing the minimum takes O(log n) instead of O(n), and changing a vertex's d-value takes O(log n) instead of O(1). Dijkstra finds the minimum n times and changes a d-value at most m times (once per relaxation), for a total of n · O(log n) + m · O(log n) = O((n + m) log n), which is O(m log n) for a connected graph. The lecture mentioned, as a tangent from the textbook, that a Fibonacci heap improves this to O(m + n log n); that is not examinable.

5.5 Choosing the right algorithm

A design problem on the exam will often be "model this situation as a shortest-path problem and call the right algorithm." Check the assumptions in this order.

1. Are all edge lengths the same? Use BFS, O(m + n).
2. Is the graph a DAG? Use DAG DP, O(m + n), negative lengths allowed, and remember it also does longest and widest paths.
3. Are all lengths nonnegative? Use Dijkstra, O(n²) or O(m log n).
4. Otherwise, if there is no negative cycle, use Bellman-Ford, O(mn).

Undirected graphs with nonnegative lengths are handled by replacing each edge {u, v} with the two directed edges (u, v) and (v, u). A problem that limits the number of edges ("at most k edges," "at most k stops") is asking for column k of the Bellman-Ford table. A problem with a few extra states ("you may skip one toll") is usually a DAG DP or Dijkstra on a graph with a copy of each vertex per state.

5.6 Longest paths and cycles

The last question of Day 2 was whether the Bellman-Ford logic can compute longest paths in a general graph. It cannot. In the graph above, with every edge of length 1, the walk s → 1 → 2 → 3 → 1 → 2 → 3 → … gets longer every time it goes around the cycle, so "the longest walk" does not exist and the recurrence keeps increasing with each column, the lecture's "problem!" Longest paths behave well only in DAGs (Section 5.2). Extra context: finding the longest simple path, with no repeated vertices, in a general graph is a problem with no known polynomial-time algorithm, in the same family as the independent set problem of Section 4.6.

5.7 The fourth section of Chapter 5

The export ends with the lecture of October 22, which covered sections 5.1 through 5.3. The lecture of October 27 presumably covered the fourth section, and the Day 1 notes say that three of the four sections are dynamic programs, so the fourth is a DP as well. The standard fourth topic in a shortest-paths chapter, and the only widely taught shortest-path DP not already covered, is the Floyd-Warshall algorithm for all-pairs shortest paths. What follows is extra context, not taken from the course notes; check it against your own notes from October 27.

Problem: a directed graph with lengths and no negative cycle; return the distance between every pair of vertices. Subproblems: for every pair (u, v) and every k from 0 to n, OPT[k][u][v] = the length of the shortest u→v path whose intermediate vertices (all vertices except the two endpoints) are among 1, …, k. Base: OPT[0][u][v] = ℓ(u, v) if (u, v) is an edge, 0 if u = v, and ∞ otherwise. Recurrence: OPT[k][u][v] = min( OPT[k−1][u][v], OPT[k−1][u][k] + OPT[k−1][k][v] ), because the best path either avoids vertex k or passes through it once, going from u to k and then from k to v using only smaller intermediate vertices. Return OPT[n][u][v]. There are n · n² subproblems at O(1) each, so O(n³); and since layer k depends only on layer k − 1, the space-saving trick of Section 1.6 reduces the table to n × n. For comparison, running Bellman-Ford from every vertex costs O(mn²) and running Dijkstra from every vertex costs O(n³) with arrays but requires nonnegative lengths.

Exercises

6. Practice Midterm 2, version A

This is a full practice exam in the format of Midterm 1: 25 points, 65 minutes, closed-everything. Problem 1 has five one-point parts answered without explanation; Problems 2 through 5 each ask for an algorithm, a correctness argument, and a running-time analysis. Set a timer, write your answers on paper, and only then open the solutions. The official practice midterm, when it is posted, should be worked the same way.

ALG(A):
  d = [0] * n
  d[1] = A[1]; d[2] = max(A[1], A[2])
  for i = 3, ..., n:
    d[i] = max(d[i-1], A[i] + d[i-2])
  return d[n]

ALG(A, B):
  d = (m+1) x (n+1) table, all 0
  best = 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if A[i] = B[j]:
        d[i][j] = d[i-1][j-1] + 1
        best = max(best, d[i][j])
  return best

ALG(T, w):
  L = vertices in an order with every child before its parent   # reverse BFS order from 1
  d = [0] * n
  for u in L:
    best = 0
    for v in T[u]: best = max(best, d[v])
    d[u] = w[u] + best
  return max(d)

ALG(G, s):
  c = [0] * n; c[s] = 1
  topologically sort V
  G_R = reverse of G
  for v in V, in topological order, skipping s:
    for u in G_R[v]:
      c[v] = c[v] + c[u]
  return c

7. Practice Midterm 2, version B

A second full exam in the same format, with a different mix of topics, followed by a set of short questions of the kind that are easy to lose points on. Take it after you have reviewed your mistakes from version A.

ALG(A, k):
  d = (n+1) x (k+1) table, all false; d[0][0] = true
  for i = 1, ..., n:
    for j = 0, ..., k:
      d[i][j] = d[i-1][j]
      if A[i] <= j and d[i-1][j - A[i]]: d[i][j] = true
  return d[n][k]

ALG(A, B):
  d = (m+1) x (n+1) table, all 0
  for i = 1, ..., m:
    for j = 1, ..., n:
      if A[i] = B[j]: d[i][j] = d[i-1][j-1] + 1
      else:           d[i][j] = max(d[i-1][j], d[i][j-1])
  return m + n - 2 * d[m][n]

ALG(T, w):
  L = vertices in an order with every child before its parent
  d = [0] * n
  for u in L:
    d[u] = w[u]
    for v in T[u]: d[u] = d[u] + max(0, d[v])
  return d[1]

ALG(G, s, x, t):
  d1 = Dijkstra(G, s)
  d2 = Dijkstra(G, x)
  return d1[x] + d2[t]

8. Summary

This chapter collects the recipes, recurrences, and facts of the book in the form of a single reference page. Read it the night before, and use it to check that every line means something to you.