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

• Digraph API (1:52) and slide 16. The edge should be labeled 12->9 instead of 12-9.
• Digraph Search (8:21) and slide 30-31. One of the white boxes is not reachable and should be colored gray.
• Strong Components, slide 54 (2:50). The return type of the methods connected() and stronglyConnected() should be boolean instead of int.
• Strong Components (17:41). The edge 0->5 is missing from the second figure.

Week 2

• Greedy algorithm (6:23). In the video, the edge 3-6 is missing from the list of crossing edges.
• Kruskal's algorithm (8:00), slide 40. To get the benefit (linear-time) of bottom-up heap construction, you would need to call MinPQ with the full array or iterable of edges.
• Kruskal's algorithm (8:00), slide 41. The order of growth of Kruskal's algorithm is E log* V if the edges are in sorted order of weight. But to achieve this, we would need to modify the code on slide 40 to use an array instead of a MinPQ.
• Prim's algorithm (21:55). The edge 4-7 (0.37) should replace the edge 0-4 (0.38) on the priority queue. Edge 4-7 will remain on the priority queue until edge 4-5 (0.35) replaces it.
• Shortest Paths APIs, slide 9 (6:01). public int weight() should be public double weight().
• Dijkstra's algorithm (5:04). The video says edge 1->4 but it should say 1->7
• Negative weights (1:02). Dijkstra's algorithm will give the correct answer on the example given. To fix, add an edge 3->4 of weight 0. Now, in the version of Dijkstra's algorithm where each vertex can be relaxed at most once, Dijkstra's algorithm will incorrectly conclude that the shortest path from 0 to 4 is 0->3->4 instead of 0->1->2->3->4.

Week 3

• Radix sorts, slides 7-9, 12, 64. Beginning with Java 7, Update 6 the substring() method takes linear time and space in the length of the extracted substring (instead of constant time and space).
• MSD radix sort (1:38). In the video, the trace inverts "shell" and "shore" in row 1, column 8 ; and "she" and "shore" in row 2, column 1.
• Suffix arrays (2:10), slide 58. The first entry in the array of sorted suffixes should be "asbestitwasw" instead of "asbest".

Week 4

• Break week.

Week 5

• Rabin-Karp, slide 55 (9:33). The type of txtHash should be long instead of int.

Week 6

• Regular expression applications, slide 54. The regular expression should be "http://(\w+\.)*(\w+)". Inside a Java string literal we need \\w, but not here.
• Regular expression applications, slide 54. The string http://www.cs.princeton.edu/news is not matched by the regular expression.

Week 7

• Brewer's Problem, slide 6 (6:16). Amount of corn in first row should be 170 (instead of 179).
• Brewer's Problem, slide 12. S_C, S_C, S_M ≥ 0 should be S_C, S_H, S_M ≥ 0.
• Classifying Problems, slide 38 (6:26). Reduction can be simplified considerably.
• Reductions: Classifying Problems, slide 57. "Who's fault?" should be "Whose fault?"