0 of 56 done
Start hereComplexity Analysis

Procedures that operate on data, as opposed to the ways of storing it in 02-data-structures.

The filing rule, and its one exception. If a note is about storing, it is a structure; if it is about doing, it is an algorithm. The exception is that an algorithm which belongs to exactly one structure is filed with that structure, because keeping it next to the vocabulary it assumes is what makes it readable. Two families have moved out of this folder on that basis:

What remains here is everything that is not the property of a single structure: the measuring system, the general problem-solving techniques, and the number and bit work.

Reading order

The foundation — read this before any data structure

  1. Complexity Analysis — [Beginner → Intermediate] — a folder. , and and why they are not interchangeable; best, average and worst case; space complexity; and amortised analysis with all three methods — aggregate, accounting and potential.

Everything in this course is quoted in the vocabulary that folder establishes, so it genuinely comes first — right after loops and what they cost.

Recursion

  1. Recursion — [Beginner → Advanced] — a folder: the three questions that produce a recursive function; the call stack and why space is the depth; recursion trees and recurrence relations; and the Master Theorem, including the two famous recurrences it cannot solve.

Searching, splitting and sorting

  1. Searching — [Beginner → Intermediate] — a folder: linear and binary search over a collection, binary search on the answer, and state-space search — the frontier, the explored set, heuristics and tie-breaking.
  2. Divide and Conquer — [Intermediate] — split, solve, combine, and why the combine step is the whole algorithm; choosing , and deliberately; why reducing the number of subproblems changes the exponent (Karatsuba, Strassen) while a cheaper combine changes at most a log factor; and a case where the technique applies and is still the wrong tool.
  3. Sorting — [Beginner → Advanced] — a folder: the lower bound and what it actually forbids, the elementary sorts, merge, quick, and the non-comparison sorts (counting, radix, bucket) that beat the bound by not comparing.

Techniques

  1. Greedy Algorithms — [Intermediate → Advanced] — a folder: when the locally best choice is provably right and the exchange argument that proves it; the coin-change trap; and the selection and scheduling family — hire-K-workers, where a group’s cost is a product rather than a sum, and interval scheduling, where only one of three plausible sort keys is correct.
  2. Dynamic Programming — [Intermediate → Advanced] — a folder: the two properties that make DP apply (both measured, not asserted); state, transition and base case; memoisation versus tabulation and why the transition dictates the fill order; space optimisation; and the classic one- and two-dimensional problems with reconstruction.

Number and bit work, and classic problems

  1. Number Theory Basics — [Intermediate] — primes, sieves, GCD, modular arithmetic.
  2. Leader / Majority — [Intermediate] — Boyer–Moore voting in space.
  3. Max Slice — [Intermediate] — Kadane’s algorithm and the maximum-subarray family.
  4. Bit Manipulation — [Intermediate] — masks, shifts, and the tricks worth recognising.
  5. Math and Geometry — [Intermediate] — matrix rotation, spiral traversal, coordinate reasoning.

What lives elsewhere, and where

If you are looking forGo to
Pre-, in-, post-order, level-order on a tree06-trees/04-traversal/
DFS, BFS, edge classification09-graphs/05-traversal/
Topological sort, Dijkstra, MST, shortest paths, A*09-graphs/06-algorithms/
Backtracking, sliding window, two pointers, and the other recognition patterns04-patterns/

How these pair with the structures

AlgorithmWants
Counting / radix sortarrays as buckets
Merge sorta scratch array of size
Quicksortthe call stack, deep if you recurse on the smaller side
Binary searcha sorted random-access container
Dynamic programminga table, or a memo dictionary
Sieve of Eratosthenesa boolean array of size

What is verified

Every finished note in this folder follows the course standard, alongside 02-data-structures and 04-patterns: stated prerequisites, observable outcomes, a runnable lab whose expected output was generated from an actual run, practice with a done when, and a demonstrable finish line.

Several labs exist to break the algorithm rather than to show it working:

LessonWhat the lab demonstrates
complexitythe ratio per doubling is the complexity — 2.00x for , 4.01x for — and growing an array by one instead of doubling makes append
amortised analysisa charge of 2 per append going into debt at while a charge of 3 never does; and the potential function holding the amortised cost at a flat 3 while actual costs run 1, 2, 3, 1, 5
recursiongetrecursionlimit() reporting 1,000 while only 996 frames are usable; and naive Fibonacci making 242,785 calls for 26 distinct subproblems
Master Theoremthe gap case measuring doubling ratios of 2.55/2.49/2.44 — distinguishable from the wrong Case-3 answer by the numbers alone
divide and conquerthe max-subarray solution losing to Kadane’s linear scan by ~20x at — applicable is not optimal
binary search on the answerthe floor/ceil midpoint bug hanging at hi == lo + 1, and 300 random instances cross-checked against linear scan
state-space searchtree search costing 60x graph search by solution depth 10, because the state space is finite while the search tree is not
greedy selectionhire-K greedy agreeing with brute force 400/400 while “take the K cheapest wages” is wrong on 130/400; two plausible interval sort keys each failing on one input and tying on another
dynamic programminga reversed fill order returning 0 instead of 34 with no error; the rolling knapsack’s upward loop returning 15 where the answer is 5; and merge sort’s subproblem redundancy measured at exactly 1.0x
searchingall three classic binary-search bugs failing: an infinite loop, a missed single element, and the JDK’s nine-year overflow
leaderthe voting phase confidently returning a candidate that is not a majority
max slicemax(0, ...) Kadane’s answering a different question on all-negative input
greedygreedy coin change failing on and , and 0/1 knapsack failing on the rule that is optimal for the fractional version
geometryfloat slopes calling three points collinear when exact integer cross products say otherwise

Where a lab claims an output, that output came from executing the code.

Question banks

One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.


↑ Back to Data Structures & Algorithms