Errata, Lecture Videos

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 booksite should be https://algs4.cs.princeton.edu.
Course introduction (7:52). In the video, the link to the booksite should be https://introcs.cs.princeton.edu.

Quick-Find, slide 14. Find: return id of p.
Quick-Union, slide 23. Find: return root of 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 (6:35). Video is missing semicolon with the statement int i = root(p).
Quick-Union Improvements (10:55). Video says "Ackermann function" instead of "inverse Ackermann function."

Mathematical Model (5:20), slide 6. Visualization of spiral galaxy forming does not display.
Mathematical Models, slide 28, 30, 32. Number of increments should be 1/2 N (N+1) to N^2.

Resizing Arrays (7:20), slide 24. Object overhead of 16 bytes is missing from diagram.
Queues (2:27). Video redeclares Node last (but last is an instance variable so it should not be redeclared).
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".
Shuffling (3:36). Video says "between 0 and i−1" instead of "between 0 and i."
Shuffling (5:55). Video attributes 2k−1 sequence to Shell instead of Hibbard. (Shell's original sequence was floor(N / 2k).)
Elementary sorts: page numbers in videos and pdf slides are not in sync; remove Microsoft war story on shuffling from pdf slides.

Bottom-Up Mergesort (1:39). Video should, for consistency and style, have sort() pass aux[] to merge() instead of making it a static variable.
Stability, slide 56. Shellsort needs at least n = 6 keys to trigger an h-sorting phase with h = 4.
Stability (4:53), slide 57. For consistency and style, the signatures for merge() and sort() should match the corresponding signatures on slides 7 and 9.
Duplicate Keys (7:22). In video, Dijkstra 3-way partitioning demo should continue one step further, incrementing i so that i > gt.
System Sorts (1:30), slide 44. The code StdIn.readStrings() should be replaced by StdIn.readAllStrings().
System Sorts, slide 51. The best case for heapsort should be N log_3 N, not N.

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 should be N log_3 N, not 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.

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).

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).

Depth-First Search (18:51) and slide 39. Reverse the order of the statements edgeTo[w] = v; and dfs(G, w); for consistency with demo.

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.

Greedy algorithm (6:23). In the video, the edge 3-6 is missing from the list of crossing edges.
Edge-weighted graph API (6:04), slide 28. The last edge in 7's adjacency list should be 4->7 (0.37).
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.

Ford–Fulkerson Algorithm (0:21). The video says to initialize all "edges to have capacity zero" but it should initialize all "edges flows to zero."
Java implementation, slide 53 (but not video). The red labels for forward and backward edge and reversed.

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.
3-way radix quicksort, slide 53 (6:36). The probabilistic gurantee for 3-way radix quicksort should be 1.39 W N lg R instead of 1.39 W n lg n.
Suffix arrays, slide 58 (2:20). The first sorted suffix should be "asbestitwas" instead of "asbest".
Suffix arrays, slide 74. This slide should appear in video at time 14:38 instead of 17:28.

R-way tries, slide 15. The instance variable "value" should be named "val" (for consistence with subsequent slides).

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.

Huffman compression, (23:28). The analysis refers to the number of nodes in the "trie", but it should refer to the number of nodes in the "binar heap."

Brewer's Problem, slide 6 (6:16). Amount of corn in first row should be 170 (instead of 179).