Speaker note: Every editor, compiler, and search engine you have ever used leans on the ideas in today's lecture — how a string sits in memory, and how to find one string inside another, fast.
Speaker note: Thirteen short animations carry the whole lecture; each idea gets a normal run and an edge/hard run right where it is introduced.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: Nothing about a C string's memory layout is new — only the "where does it end" convention is.
Speaker note: A trie is "Week 4's tree, but the branching factor is the alphabet size." Rabin-Karp is "Week 6's hash, made incremental."
Speaker note: This is genuinely new machinery — worth flagging up front so today doesn't feel like "just more search algorithms."
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Section 1 sets up the one convention every later section assumes: a C string is a char array plus a NUL terminator, nothing more.
Speaker note: The answer — a single reserved byte — has shaped C programming (and C bugs) for over fifty years.
Speaker note: Contrast with Pascal-style strings, which do store a length byte — a design choice with real consequences.
Speaker note: "Someone else's mail" is a friendly way to say undefined behavior — corrupting memory you do not own.
Speaker note: "No shortcut exists" is the single fact that explains every complexity result in this section.
Speaker note: We show the danger by FLAGGING it and stopping — never by actually executing an out-of-bounds write.
Speaker note: Normal example: cap=16, "HELLOWORLD" fits comfortably — watch the copy loop, the terminator, then strlen's second walk.
Speaker note: cap=8, a 10-letter source — watch the guard `if (i == cap) break;` stop the copy one write before it would go out of bounds.
Speaker note: The guard line is the ONE addition that turns a dangerous naive strcpy loop into a safe, teachable one.
Speaker note: This one-line trap (strlen inside a loop condition) is one of the most common accidental-quadratic bugs in C.
Speaker note: Emphasize "every single call" — this is the fact students most often forget in later courses.
Speaker note: `==` compares pointers in C, not characters — two identical-looking strings at different addresses compare unequal.
Speaker note: Let a few hands go up before revealing the answer — this is a very common off-by-one in real code.
Speaker note: Tie this back to the overflow animation: exactly this omission is what "cap=8, 10 letters" demonstrates.
Speaker note: Section 2 answers "what if we don't know the final length in advance?" — the same question Week 1's dynamic array answered for numbers.
Speaker note: This is exactly what java.lang.StringBuilder, C++'s std::string, and Week 1's dynamic array all do internally.
Speaker note: The "double, not +1" choice is the whole content of this section's complexity argument.
Speaker note: "Exponentially rarer" is the intuitive version of the amortized-analysis argument on the complexity slide.
Speaker note: Normal example: initCap=4, "HELLOWORLD" — watch the buffer fill, hit capacity, and grow, with old characters visibly copied.
Speaker note: initCap=1 forces the most growths for 10 letters — a good stress test of the doubling rule.
Speaker note: In C, realloc may MOVE the block — every old pointer into buf becomes invalid the instant this line runs.
Speaker note: "Amortized" means: not every single operation is cheap, but the AVERAGE over a long sequence is.
Speaker note: A fixed growth amount is a classic "looks fine on small inputs, falls over at scale" bug.
Speaker note: Ask students to think in terms of "how many growths happen, and how much does each one cost."
Speaker note: log(n) growths costing up to n each (decreasing) sums to O(n); n/10 growths costing up to n each sums to O(n^2).
Speaker note: Section 3 introduces the trie — the structure behind every autocomplete box and spell checker you have ever used.
Speaker note: Hashing deliberately scatters similar keys — that is exactly why it cannot answer a "starts with" question.
Speaker note: Sixty-five years old and still the first idea any interviewer expects for "design an autocomplete feature."
Speaker note: The flag matters — a fork can be mid-path for one word AND the end of a shorter word at the same time.
Speaker note: This dual role — end-of-word AND has-children — is the single most common source of trie bugs.
Speaker note: A 10-word trie and a 10-million-word trie answer search("CAT") in exactly the same number of steps.
Speaker note: Normal example: CAT, CAR, CARD, DOG — watch shared edges get reused, and the "end" flag appear at word boundaries.
Speaker note: A, AB, ABC, ABCD — no branching at all, a plain linked-list-like chain. This is exactly what section 4 compresses.
Speaker note: C uses a fixed 26-slot array per node; the Java version (in the notes) uses a HashMap instead — a real trade-off.
Speaker note: Reaching the end of the loop only proves "this is a prefix" — the return value also checks isEnd.
Speaker note: That memory price is exactly what section 4's compressed trie fixes.
Speaker note: search("CAR") and search("CARP") walk the same three edges in a trie holding "CARPET" — only one of them is a stored word.
Speaker note: Give students 30 seconds; many will initially say true because the path exists.
Speaker note: This is precisely the found-vs-prefix distinction the "Common mistakes" slide just warned about.
Speaker note: Section 4 fixes the memory waste a plain trie has on long, non-branching words.
Speaker note: Thirteen nodes for something that could, in principle, be one string with no branching at all.
Speaker note: PATRICIA tries are still used today in networking — longest-prefix-match IP routing is a direct application.
Speaker note: Case 3 — the split — is the one genuinely new idea; the other two cases are exactly a plain trie's logic.
Speaker note: Walk this on the board before playing the animation — it is the one step students need to see by hand first.
Speaker note: Two completely different compression ideas from this course — worth naming the difference explicitly.
Speaker note: Normal example: TEST, TEA, TEAM — watch the TEST edge split into TE + ST, then TEAM extend past the A node.
Speaker note: ANT, ARM, ART, AXE — a split inside a split, the hardest case this structure has to handle correctly.
Speaker note: The full split_edge logic (shortening the old label, re-keying the child) is in the notes — this is the decision point.
Speaker note: The time complexity is unchanged; only the constant factor on memory improves, sometimes dramatically.
Speaker note: The re-keying bug is subtle — the child's map/array key must change to match its shortened label's new first letter.
Speaker note: Let students reason it out before revealing — the "no shared prefix" case is the simplest possible one.
Speaker note: Contrast with a plain trie, which would need 5 + 6 = 11 nodes for the same two words.
Speaker note: Section 5 answers a different question: not "is X a word?" but "does pattern P occur anywhere in text T?"
Speaker note: This is the question a text editor's "find" feature, or a genome browser, asks constantly.
Speaker note: "Always differ in length" is why a shorter suffix that is a prefix of a longer one just sorts first, automatically.
Speaker note: Normal example: MISSISSIPPI — watch each suffix, as its own row, slide into sorted position via insertion sort.
Speaker note: AAAAAAAAAA — every comparison runs all the way to the shorter suffix's end; the length rule alone decides every tie.
Speaker note: This is a nice, concrete example of "clever pointer use avoids O(n) extra memory and copying."
Speaker note: The construction cost is paid ONCE; every subsequent search against the same text is fast.
Speaker note: `sa[i]` is a starting POSITION, not a copy of the suffix — printing the suffix needs `text + sa[i]`.
Speaker note: This is the key fact that makes a sentinel character unnecessary for the comparison rule.
Speaker note: Different lengths mean plain lexicographic comparison already handles every possible tie correctly.
Speaker note: Section 6 opens the search family — five algorithms, five different tricks, all answering the same question.
Speaker note: "Simplest possible" is naive search — exactly where you would start with no cleverer idea taught yet.
Speaker note: "Keep going after a match" is the single most-forgotten rule — a common bug jumps m positions after a hit.
Speaker note: Normal example: text="ABABAABABC", pattern="ABABC" — watch a few false starts before the real match at shift 5.
Speaker note: text="AAAAAAAAAA", pattern="AAAB" — every shift compares nearly the whole pattern before failing on the LAST character.
Speaker note: Every algorithm from here to Section 11 is, in some sense, a smarter way to avoid this double loop's worst case.
Speaker note: Frame naive search's worst case as the villain of the rest of the lecture — every later algorithm is "the fix."
Speaker note: Worst-case complexity is not the only consideration — small inputs favor naive search's tiny constant factor.
Speaker note: Give 60 seconds — many will independently rediscover the "AAAA...B" pattern shown in the hard example.
Speaker note: This is exactly the hard-scenario animation shown two slides ago.
Speaker note: Section 7 builds the table Section 8 uses — a KMP lecture needs both halves to make sense.
Speaker note: The key insight: the pattern can be studied ONCE, in advance, independent of the text it will search.
Speaker note: One of the most-cited papers in string algorithms — still the first thing taught after naive search in most courses.
Speaker note: Work through "ABAB" -> lps=2 on the board; it is short enough to do by hand in under a minute.
Speaker note: Normal example: ABABCABABA — watch len grow on a match, and fall back through lps[len-1] (never straight to 0) on a mismatch.
Speaker note: AABAACAABAA — a mismatch falls back through more than one level of lps, not straight to 0.
Speaker note: The "else if (len != 0)" branch — falling back instead of resetting — is THE line students get wrong first.
Speaker note: This amortized argument (a value that only decreases as much as it increased) recurs constantly in string algorithms.
Speaker note: Resetting to 0 still produces A table — just the WRONG one, one that under-reports safe skip distance.
Speaker note: This connects the table's last entry to the pattern's own self-overlap as a whole, not just a prefix.
Speaker note: "AAAAAAAAAA" has lps[m-1] = m-1, the maximum possible self-overlap.
Speaker note: Section 8 is where the lps table earns its keep — this is the payoff slide sequence for section 7's setup.
Speaker note: "Never moves backward" is the single guarantee that gives KMP its O(n+m) bound — say it more than once.
Speaker note: "i stays put" on a fallback is the key line — the text character is never re-examined.
Speaker note: Normal example: the classic CLRS-style text/pattern pair — watch i march forward while j jumps around using lps.
Speaker note: text="AAAAAAAAAAAAAAAB", pattern="AAAAB" — a dense sequence of fallbacks, but i still only ever moves forward.
Speaker note: Three branches, one for each case on the "idea" slide — map them 1:1 with students before moving on.
Speaker note: "No bad input exists" is worth repeating — KMP has no configuration or input that degrades it.
Speaker note: Forgetting the post-match fallback silently misses overlapping occurrences — a quiet, hard-to-spot bug.
Speaker note: The answer should connect directly back to naive search's "re-examines text characters" root cause.
Speaker note: This slide is the payoff of the whole KMP arc — say it slowly, it is the one sentence worth remembering.
Speaker note: Section 9 brings hashing (Week 6) back, in a genuinely new, incremental form.
Speaker note: This is a completely different strategy from KMP's — comparison-avoidance instead of comparison-optimization.
Speaker note: "Candidate, never a certainty" is the single most important sentence in this section.
Speaker note: "Verified" — say it again. Two different substrings CAN hash to the same value; that is not a bug, it is math.
Speaker note: Normal example: mod=101, no spurious hits — watch the rolling hash update, O(1), skipping most windows entirely.
Speaker note: mod=7 (deliberately small) — a hash match that FAILS verification: a spurious hit, correctly rejected.
Speaker note: A genuine teaching moment — never assume `long` means 64 bits in C; its width is platform-defined.
Speaker note: Point at `strncmp` — that call is not optional; skipping it silently reports spurious hits as real matches.
Speaker note: The "hard" example deliberately used mod=7 to make this worst-case behavior visible on purpose.
Speaker note: These three map exactly to the three things this section's animation and program deliberately demonstrate.
Speaker note: The pigeonhole principle is the precise mathematical answer, worth naming explicitly.
Speaker note: This is a nice callback to any discrete-math course students may have also taken.
Speaker note: Section 10 introduces the algorithm that is, in practice, often the fastest for natural-language text.
Speaker note: This sounds backward at first — that is exactly why it is worth pausing on before revealing the idea.
Speaker note: Mention the good-suffix rule exists, but is out of scope — students should know the name for later reading.
Speaker note: "Never less than 1" is a real implementation trap — repeated characters can make the naive shift formula go to 0.
Speaker note: Normal example: text="ABAAABCDAB", pattern="ABC" — watch the right-to-left scan and the resulting jump size.
Speaker note: text="ZZZZZZZZZZ", pattern="ABC" — Z never appears in the pattern, so every window jumps the full pattern length.
Speaker note: The table is built ONCE from the pattern alone — exactly like KMP's lps table, reused unchanged across every window.
Speaker note: Emphasize "in practice" — the average case on real text is what makes this algorithm's reputation.
Speaker note: Comparing left-to-right by mistake still finds correct matches — it just throws away Boyer-Moore's entire point.
Speaker note: The answer is about PROVING a range of positions cannot match, without ever looking at the characters there.
Speaker note: This "prove, don't check" idea is the conceptual heart of every algorithm faster than naive search this week.
Speaker note: Section 11 closes the search family with the most conceptually elegant of the five algorithms.
Speaker note: Frame this as "the elegant one" — students often find the Z-algorithm the most satisfying of the five.
Speaker note: The window [l, r) plays the exact same role as KMP's lps table — "remember what you already know."
Speaker note: Normal example: pattern="AB", text="ABABABABAB" — watch the [l,r) window grow and get reused for later positions.
Speaker note: pattern="AAA" against "AAAAAAAAAA" — the window keeps growing to the string's very end, reuse at almost every step.
Speaker note: Three lines, one per idea: reuse the window, extend it if possible, remember the new window if it grew.
Speaker note: Worth reminding students this is the third time this lecture has used the same "only grows" amortized argument.
Speaker note: A Z value CAN legitimately exceed m if the text itself repeats — >= is the correct match test, not ==.
Speaker note: The honest answer is "it doesn't avoid a table" — Z[] IS the table, playing an analogous role.
Speaker note: lps[i] describes overlap within the pattern alone; Z[i] describes overlap with the whole glued-together string.
Speaker note: A short pause-and-compare section before the lecture pivots to dynamic programming.
Speaker note: KMP is the only one with a GUARANTEED worst case — the safe default whenever adversarial input is a concern.
Speaker note: Section 13 introduces dynamic programming from scratch — no prior week in this course has covered it.
Speaker note: These three real-world examples ground an otherwise abstract question in things students already know.
Speaker note: Write the naive recursive call tree on the board — the repeated sub-trees are visually obvious even for small inputs.
Speaker note: Both properties are required — optimal substructure makes the recursion correct; overlap makes memoizing worthwhile.
Speaker note: Levenshtein's original paper predates the "dynamic programming" name becoming standard in this exact context.
Speaker note: "Every dependency is already computed" is why no recursion is needed at all — a single pass suffices.
Speaker note: Normal example: KITTEN -> SITTING, distance 3 — watch the table fill, then the traceback reconstruct one edit sequence.
Speaker note: CAT -> CATERPILLAR — a is a prefix of b, so every non-matching step is a pure insert, never a substitute or delete.
Speaker note: This is the entire algorithm's core — everything else (base cases, traceback) is bookkeeping around this recurrence.
Speaker note: Mention the space optimization exists but note it sacrifices the ability to run the traceback afterward.
Speaker note: The base-case bug is sneaky — it silently makes "compare against an empty prefix" look free when it should cost.
Speaker note: This connects directly back to the "the idea" slide a few slides ago — a good comprehension check.
Speaker note: Both halves of this answer matter — many students only remember one of the two properties.
Speaker note: Section 14 reuses section 13's exact table shape with one changed recurrence — a nice "same shape, different meaning" close.
Speaker note: This is exactly what a diff tool highlights as unchanged — the connection to git diff pays off here.
Speaker note: This distinction is the single most common conceptual error with LCS — spend real time on this slide.
Speaker note: Contrast explicitly with edit distance's min+1 — that contrast is this section's core teaching point.
Speaker note: Normal example: ABCBDAB / BDCABA, length 4 — watch the diagonal grow on matches, max carried forward otherwise.
Speaker note: ABCDE vs FGHIJ — every cell stays 0, the whole table fills with the "no match, carry max" branch only.
Speaker note: Compare this side by side with edit distance's code slide — the visual similarity is deliberate and instructive.
Speaker note: This is the moment to say explicitly: "you now know the DP table shape, not just two isolated algorithms."
Speaker note: The traceback is required to recover the actual characters — dp[n][m] alone only answers "how long?"
Speaker note: The closing conceptual question of the lecture — tying together sections 13 and 14 explicitly.
Speaker note: This is the cleanest one-sentence summary of the whole DP half of today's lecture.
Speaker note: Five structures, five search algorithms, two DP algorithms — thirteen animations, one lecture.
Speaker note: Encourage students to actually run the programs — every output shown all lecture has been real, not invented.
Speaker note: Dynamic programming is the one idea this week that will keep resurfacing for the rest of your studies.
Speaker note: Full citations with journal names, volumes, and years are all in the printed notes' References section.
Speaker note: Thank the class, remind them where the code and notes live, and open the floor.