String Algorithms and Complexity Theory

reading · we frame, you read MIT or the canonical taught · we author, no canonical fits ↺ spirals back to earlier lessons

Course locked

Complete Parallel and Concurrent Algorithms first.

This course unlocks once you've finished its prerequisite. Open prerequisite →

Prerequisites

Discrete Mathematics not yet

Introduction to Algorithms and Complexity not yet

Graph Fundamentals not yet

Complete prerequisites first to enroll.

reading · 30 min + ~193 min canonical

String Matching: Brute Force, KMP, Rabin-Karp

Find a substring inside a larger string. It sounds trivial — just scan through, checking each position. That's the brute-force approach, and it's O(n × m) where n is the text leng…

primary MIT 6.006 — String Matching, Complexity lectures

preview →

reading · 30 min + ~193 min canonical L1

Tries, Suffix Arrays, and Suffix Trees: When the Structure of Strings Matters

The previous lesson taught algorithms that match a single pattern in a single text. What if you need to query the same text many times — "is X a prefix of any word in my dictionar…

primary MIT 6.006 — String Matching, Complexity lectures

after L1 locked

reading · 40 min + ~193 min canonical L1

P, NP, and the Question That's Been Open Since 1971

Some problems we can solve quickly. Sorting a billion numbers: a few seconds. Finding the shortest path between two cities: milliseconds. Routing data packets: nanoseconds.

primary MIT 6.006 — String Matching, Complexity lectures

after L2 locked

reading · 40 min + ~193 min canonical L1

NP-Completeness and Reductions: How Karp Found 21 Problems That Were All the Same

In 1972, Richard Karp published a paper showing that 21 different problems — graph colouring, travelling salesman, vertex cover, Hamiltonian cycle, knapsack, set cover, and 15 oth…

primary MIT 6.006 — String Matching, Complexity lectures

after L3 locked

reading · 30 min + ~193 min canonical L1

Approximation and Randomised Algorithms: When "Almost Right" Beats "Eventually Right"

The previous two lessons established that NP-complete problems can't be solved in polynomial time (we believe). But businesses still need to route delivery trucks, schedule classe…

primary MIT 6.006 — String Matching, Complexity lectures

after L4 locked

exercise reading · 15 min L1

Exercises: Easy (Warm-up)

- [ ] Implement Trie (Prefix Tree) (#208) — NC/LC — Insert, search, startsWith methods - [ ] Single Number (#136) — NC/LC — XOR all elements, duplicate cancels out - [ ] Number of…

after L5 locked

exercise reading · 30 min L1

Exercises: Medium (Core)

- [ ] Design Add and Search Words (#211) — NC/LC — Trie with wildcard DFS - [ ] Implement KMP string matching in Ruby — Build failure function, O(n+m) matching - [ ] Implement Rab…

after L6 locked

exercise reading · 45 min L1

Exercises: Hard (Stretch)

- [ ] Word Search II (#212) — NC/LC — Trie + DFS on grid, prune branches - [ ] Prove that 3-SAT is NP-complete (written proof) — Reduction from SAT - [ ] Implement a suffix array …

after L7 locked

exercise reading · 60 min L1

Mini-Project

- [ ] Build a text search engine in Ruby — construct a trie from a corpus of documents, support prefix search and autocomplete, implement KMP for exact phrase matching, rank resul…

after L8 locked

L10

project reading · 360 min L1

Project: Autocomplete Engine

Build a trie-based autocomplete system in Ruby. Load a dictionary of 100K+ words, support prefix search returning top-10 suggestions ranked by frequency. Implement KMP for exact s…

after L9 locked

L11

assessment reading · 63 min L1

Self-Assessment: String Algorithms and Complexity Theory

- [ ] What is a trie? What operations does it support and what are their time complexities? - [ ] Explain the KMP string matching algorithm. What is the failure function? - [ ] Wh…

after L10 locked

L12

assessment reading · 60 min L1

Quarter 4 Gate Check: DP and Advanced Algorithms

- [ ] Course 4.1 knowledge check passed - [ ] Course 4.2 knowledge check passed - [ ] Course 4.3 knowledge check passed - [ ] Course 4.4 knowledge check passed - [ ] Smart Text Ed…

after L11 locked

L13

assessment reading · 120 min L1

Year 1 Assessment: Foundations

Complete all of the following. There is no time limit on the overall assessment, but individual items have targets.

after L12 locked

13 lessons. Read in order; spiral back when you need to. By the end you'll have used the core ideas twice — once on the abstract, once on something you'll meet at work next week.