Data Structures & Algorithms
Preprocessing a pattern turns a blind rescan into a series of informed skips, and the graph and dynamic programming algorithms both win by reusing work a plain recursion would throw away. These notes turn my Georgia Tech DSA IV material into demos you can step through.
Module 12 · Pattern Matching
Finding a pattern of length m inside a text of length n, where overlapping occurrences all count. Brute force retries every alignment, O(mn) in the worst case; Boyer-Moore skips ahead using a last occurrence table, KMP realigns using a failure table for an O(m + n) guarantee, and Rabin-Karp screens each window with a rolling hash before comparing characters.
Module 13 · Graph Algorithms
A graph is a vertex set plus an edge set, stored as an adjacency list, an adjacency matrix, or an edge list. DFS and BFS are the two exhaustive-search templates, both O(|V| + |E|), and Dijkstra's algorithm generalizes BFS to weighted graphs by swapping the queue for a priority queue.
Module 14 · MST
Prim's and Kruskal's, two greedy algorithms that build the cheapest tree connecting every vertex of an undirected graph. Prim's grows one component outward across a cut; Kruskal's merges clusters globally and needs a disjoint set to reject the edges that would close a cycle.
Module 15 · Dynamic Programming
Divide-and-conquer for problems whose subproblems overlap: store each subproblem's answer instead of recomputing it, which turns many exponential recursions polynomial at the cost of extra space. LCS, 0-1 knapsack, Bellman-Ford, and Floyd-Warshall are all built on that one idea.
Search for abacab inside abacadbaabacab: compare from the back of the pattern, then let the last occurrence table decide how far to shift.
occurrences: —
1. Pattern abacab (m = 6) against text abacadbaabacab (n = 14). Boyer-Moore preprocesses the pattern before it reads any text.
Run BFS from A on a five-vertex graph, then reset and run recursive DFS from the same start to watch the visit orders diverge.
Marks a vertex on the way into the queue, so nothing is ever queued twice.
Adjacency lists: A: B, C · B: A, D · C: A, D · D: B, C, E · E: D
1. BFS marks A as it goes into the queue. Dequeue A and add its unvisited neighbors B and C, marking each on the way in. Queue: B, C.
Grow the MST outward from A, always taking the cheapest edge across the cut between visited and unvisited vertices, including one dequeued edge that gets discarded.
1. The graph: five vertices, seven undirected edges, every weight distinct. An MST is the cheapest set of four edges that connects all five.
Fill the longest common subsequence table for "BLOG" and "BOG" row by row, then walk back from the bottom-right cell to read the subsequence itself.
lcs: —
1. Compare x = "BLOG" down the rows with y = "BOG" across the columns. Row 0 and column 0 are all zeros, because an empty prefix shares nothing.
Boyer-Moore and KMP both preprocess the pattern so a mismatch can shift it intelligently; Rabin-Karp instead screens each window with a rolling hash and only compares characters when the hashes agree. Boyer-Moore is sublinear in the typical case at O(m + n/m) but degrades to O(mn), KMP is O(m + n) whatever the input, and Rabin-Karp is linear with a good hash and O(mn) if every hash collides. Large alphabets suit Boyer-Moore, small alphabets or streaming text suit KMP, and searching many patterns at once suits Rabin-Karp.
Module 12 · Pattern Matching
Dijkstra splits vertices into unexplored, frontier (in the priority queue, possibly on a suboptimal path), and visited. A vertex is certified the instant it is dequeued, because a cheaper route would have gone through an already-visited neighbor and been enqueued smaller. A negative edge breaks exactly that certificate, since Dijkstra never revisits, which is why negative weights need Bellman-Ford (O(|V|·|E|)) or Floyd-Warshall (O(|V|³)).
Module 13 · Graph Algorithms
Prim's is greedy: the visited set splits the graph into a cut, the priority queue holds the frontier edges crossing it, and dequeuing the smallest is the locally optimal choice. That choice is also globally correct, because any MST must contain the minimum-cost edge over any cut. The skeleton is Dijkstra's, but the priority pushed is the edge weight alone rather than a cumulative distance, and it runs in O(|E| log |E|) with a binary heap.
Module 14 · MST
Kruskal's takes edges in weight order and keeps any that does not close a cycle, which the cycle property justifies: given distinct edge weights, the heaviest edge of a cycle belongs to no MST. Its clusters grow globally instead of outward from one source, so every vertex can be visited while the MST is still incomplete, and a visited set cannot tell a cluster merge from a cycle. A disjoint set answers that with find and union at amortized O(α(n)), so the heap dominates at O(|E| log |E|), or O(|E| log |V|) on a simple graph.
Module 14 · MST
Dynamic programming is divide-and-conquer for problems whose subproblems repeat: compute each subproblem once, store it, and reuse it. Naive recursive Fibonacci is exponential, while the memoized version is O(n) time and O(n) space — the usual trade of polynomial space for polynomial time. Drawing subproblems as vertices and dependencies as edges shows the boundary: DP applies when that graph is a DAG, with top-down DP as a DFS over it and bottom-up as reverse topological order.
Module 15 · Dynamic Programming
Bellman-Ford relaxes every edge |V|−1 times, because a shortest path uses at most |V|−1 edges, and it handles the negative weights Dijkstra's cannot, in O(|V|·|E|) time and O(|V|) space. Floyd-Warshall solves all pairs in O(|V|³) time and O(|V|²) space by admitting one more intermediate vertex per outer iteration, which is why that loop has to be outermost. Both detect negative cycles: one extra Bellman-Ford round that still improves a distance, or a negative entry on the Floyd-Warshall diagonal.
Module 15 · Dynamic Programming
Module 12 · Pattern Matching
Comparing right to left means the first character examined in a window is the one furthest along in the text, so a mismatch there can shift the pattern by up to m. That mismatched text character is what the last occurrence table indexes; if it is absent from the pattern the table reads −1 and the pattern moves completely past it.
f[i] is the length of the longest proper suffix of p[0..i] that is also a prefix of p[0..i]. On a mismatch at pattern index j > 0 the search jumps to f[j−1] instead of restarting, so the text index never moves backward — that is what makes KMP O(m + n) in the worst case, with best and worst both linear.
H(next) = (H(cur) − h(front)·b^(m−1))·b + h(new): drop the front character, promote the rest, append the new one. The b^(m−1) power is computed once with the initial hash, so window size never affects the update cost, though a run of hash collisions still drags the search back to O(mn).
Module 13 · Graph Algorithms
BFS uses a queue and finishes every vertex one edge from the start before going two edges out. DFS uses recursion or a stack and goes deep before wide. Both are O(|V| + |E|) in the worst case, so the choice comes from where the target sits, how deep the graph runs, and how wide the branching is.
Any shorter route would have to pass through an already-visited neighbor, and that route would have been enqueued with a smaller key and dequeued first. The frontier still in the queue may hold suboptimal paths, but the minimum dequeue is final.
The course implementation has no decreaseKey, so the priority queue can hold one entry per considered edge: O(|E| log |E|). Two separate things collapse that to log |V|. On a simple graph log |E| ≤ log |V|² = 2 log |V|, so the two forms are the same bound. And with decreaseKey the queue never exceeds O(|V|) entries, giving O((|V| + |E|) log |V|), which becomes O(|E| log |V|) on a connected graph.
Module 14 · MST
Dense graphs tie on paper but favor Prim's in practice, since Kruskal's dequeues and cycle-checks every edge; sparse graphs, presorted edges, and wanting a minimum spanning forest all favor Kruskal's. With edges streaming under O(|V|) memory it is Kruskal's too: its accept-or-reject rule needs only the disjoint set, while Prim's buffers candidates in a priority queue.
find walks parent pointers up to the representative root, and path compression repoints every node on that path straight at the root on the way back up. union by rank attaches the shorter tree under the taller root and bumps rank only when the two ranks tie, so together find and union are amortized O(α(n)) — inverse Ackermann, effectively constant.
Distinct edge weights guarantee a unique MST, as does the graph already being a tree. Negative weights are fine here, unlike in Dijkstra's, and negating every weight turns the same algorithms into a maximum spanning tree.
Module 15 · Dynamic Programming
Overlapping subproblems plus optimal substructure. Merge sort splits into disjoint subarrays, so there is nothing to reuse; DP applies when subproblems share dependencies, and memoizing them collapses the repeated work. The hard part is identifying the subproblems, not implementing them.
If x[i] and y[j] match, L[i][j] = L[i−1][j−1] + 1; otherwise L[i][j] = max(L[i−1][j], L[i][j−1]), with row 0 and column 0 set to 0. Backtracking from L[n][m] rebuilds the string: a diagonal step takes that character, and when top and left tie the choice is arbitrary — it changes which LCS you get, never the length.
The capacity W is written with about log W digits, so O(nW) is exponential in the size of the input. That is pseudo-polynomial time: polynomial in the value of a number, not in its representation. The same subtlety applies to any algorithm whose running time is driven by a numeric input.