Algorithm Design, Lecture Slides Errata

Below are all the known errors in Kevin Wayne's lecture slides for the textbook Algorithm Design by Jon Kleinberg and Éva Tardos. We highlight the printed version mistake in pink, and the corrected replacement in green. Please email Kevin if you discover any more.

2.10
Printed: asymmetric
Corrected: rename to not transitive
Reported by Gang Tan, 18-Sep-05.
Fixed 20-Jan-05.

3.30
Printed: on same level
Corrected: on adjacent levels
Reported by Gang Tan, 18-Sep-05.
Fixed 20-Jan-05.

3.39
Printed: Topological order is misssing edge from v1 to v7.
Corrected: Add edge from v1 to v7.
Reported by Gang Tan, 15-Jan-05.
Fixed 20-Jan-05.

4.7
Printed: Greedy: i1 i1
Corrected: Greedy: i1 i2
Reported by Gang Tan, 15-Jan-05.
Fixed 20-Jan-05.

5.36
Printed: 110101010
Corrected: 11010101 and remove first line for add example
Reported by Gang Tan, 15-Jan-05.
Fixed 20-Jan-05.

FFT, slide 14
Printed: k + n
Corrected: k + n/2
Reported by Kevin Wayne, 26-Apr-06.
Fixed 26-Apr-06.

6.12
Printed: w_j
Corrected: v_j
Reported by Frank Ruskey, 17-Dec-08.
Fixed 18-Dec-09.

6.15
Printed: M[j] = 0
Corrected: M[0] = 0
Reported by Sofya Raskhodnikova, 23-Dec-07.
Fixed 18-Dec-08.

6.18
Printed: see p. 288
Corrected: see p. 304
Reported by Sofya Raskhodnikova, 23-Dec-07.
Fixed 18-Dec-08.

6.39
Printed: 5 mismatches, 1 gap
Corrected: 6 mismatches, 1 gap
Reported by Gang Tan, 15-Jan-05.
Fixed 20-Jan-05.

7.21 (max flow, min cut)
Printed: c(e) > 0
Corrected: f(e) > 0
Reported by Jim Marvel, 03-Nov-07.
Fixed 05-Novn-07.

7.23 (max flow, min cut)
Printed: f(e) - b
Corrected: f(e^R) - b
Reported by Jim Marvel, 03-Nov-07.
Fixed 05-Novn-07.

7.25 (max flow applications)
Printed: "4" above "10"
Corrected: remove "4" above "10"
Reported by Gang Tan, 15-Jan-05.
Fixed 20-Jan-05.

8.15
Printed: Are Cook and Karp reductions the same?
Corrected: Are Cook and Karp reductions the same with respect to NP?
Reported by Richard Ladner, 16-Nov-09.
Fixed 18-Nov-09.

8.37 (Polynomial Reductions)
Printed: 100110, 100001, 10000, 10111, 1101
Corrected: 100010, 100101, 10100, 10011, 1001
Reported by Kevin Wayne, 25-May-06.
Fixed 25-May-06.

9.2
Printed: Amy
Corrected: Alice
Reported by Frank Ruskey, 17-Dec-08.
Fixed 18-Dec-09.

9.14
Printed: sequence of configurations starting from {C1}
Corrected: start sequence from empty set
Reported by Frank Ruskey, 17-Dec-08.
Fixed 18-Dec-09.

10.8
Printed: base case is k = 1
Corrected: need base case of k = 0
Reported by Sofya Raskhodnikova, 23-Dec-07.
Fixed 18-Dec-08.

10.13
Printed: w_v + sum_v Mout[v]
Corrected: w_u + sum_v Mout[v]
Reported by Frank Ruskey, 17-Dec-08.
Fixed 18-Dec-09.

11.5, 11.11
Printed: pseudocode
Corrected: needs to return schedule
Reported by Sofya Raskhodnikova, 23-Dec-07.
Fixed 18-Dec-08.

11.5
Printed: O(n log n)
Corrected: O(n log m)
Reported by Frank Ruskey, 17-Dec-08.
Fixed 18-Dec-09.

11.55
Printed: Table of values
Corrected: First 3 values need to have an extra digit
Reported by Frank Ruskey, 17-Dec-08.
Fixed 18-Dec-09.