Errata Help Center Learn more.

Below are the known errors in the lecture slides and videos.

Week 0

• Course introduction (3:28). In the video, a video compression artifact has removed the path between the two nodes.
• Course introduction (6:46). In the video, the link to the Algorithms 4/e booksite should be http://algs4.cs.princeton.edu.
• Course introduction (7:53). In the video, the link to the Intro to Java booksite should be http://introcs.cs.princeton.edu.

Week 1

• Quick-Union (5:24). Video is missing semicolon with the statement int i = root(p).
• Quick-Union Improvements, slide 35. There are N = 11 nodes (and not 10).
• Quick-Union Improvements, slide 35. The given tree could not have been created using weighted quick union.
• Quick-Union Improvements (10:55). Video says "Ackermann function" instead of "inverse Ackermann function."
• Union-Find Applications, slide 48. Hinley-Milner should be Hindley-Milner.
• Analysis of Algorithms: Observations, slide 26. As of Java 7u6, substring extraction takes time proportional to N (instead of 1).
• Mathematical Models, slide 28, 30, 32. Number of increments should be 1/2 N (N+1) to N^2.

Week 2

• Queues (2:27). Video redeclares Node last (but last is an instance variable so it should not be redeclared).
• Stack and Queue Applications (0:50), slide 53. The class declaration should be List<Item> extends Iterable<Item> instead of List<Item> implements Iterable<Item>. More technically, in Java 1.7, it extends Collection, which extends Iterable.
• Iterators (6:35), slide 50. iterator() should return an Iterator (instead of Iterable).
• Sorting Introduction (1:00). Video says data is read in from "standard input" instead of from "StdRandom.uniform()".
• Insertion sort, slide 34. Compares ≤ exchanges + (N − 1) instead of =.
• Shellsort (3:02). Video says to consider using "shellsort" to sort subsequences instead of "selection sort".
• Shellsort (5:41). Video attributes 2^k − 1 sequence to Shell instead of Hibbard.
• Shuffling (3:36). Video says "between 0 and i − 1" instead of "between 0 and i."
• Shuffling, slide 61. Updated link: How We Learned to Cheat at Poker.
• Elementary sorts: page numbers in videos and pdf slides are not in sync; remove Microsoft war story on shuffling from pdf slides.

Week 3

• Mergesort (8:47), slide 9. The statement aux = new Comparable[a.length] should be Comparable[] aux = new Comparable[a.length]
• Mergesort (22:16), slide 21. The call sort(a) should call sort(aux, a, 0, a.length-1).
• Bottom-Up Mergesort (1:37). In video, better style to declare aux[] array in sort() and pass as an argument to merge().
• Stability, slide 57. The signature for merge() should match the signature for the version on slide 7.
• Duplicate Keys. Dijkstra 3-way partitioning demo should continue one step further, incrementing i so that i > gt.

Week 4

• Heapsort, slide 35. There should be a note that the signature for sink() requires passing the array a[] and N.
• Heapsort, slide 39. The best case for heapsort is 3N compares (if all keys are equal). We note that if all keys are distinct, then the best case is N lg N.
• Event-driven simulation, slide 51-52. The variable σ should be replaced by s.
• Binary search trees, slide 14. Worst-case height should be N − 1 (instead of N).
• Deletion in BSTs (8:20). Video says that if you randomly choose between predecessor and successor in Hibbard deletion, then the height of the resulting trees is sqrt(N). This is unknown—the conjecture is that the resulting trees have height logarithmic in N.

Week 5

• Red-Black BSTs (09:07). Video says that h's color is going to be black after the rotation. It should say red.
• Kd-Trees (08:30 to 09:10). Video says "above/upper" instead of "below/lower" a few times.
• Kd-Trees (19:19), slide 15. The right subtree (above the splitting line) of 5 should be explored before the left subtree (below the splitting line).

Week 6

• Symbol table applications: indexing clients (6:06). Video calls StdIn.readStrings() instead of in.readAllStrings().
• Symbol table applications: indexing clients (6:06). Video declares variable named pages instead of set.
• Symbol table applications: indexing clients (6:06). Video calls set.put(i) instead of set.add(i).