Algorithms handbook
A free, structured course on data structures and algorithms: Competitive programming intro, Foundations, NP-hardness & intractability, Arrays & strings, Bit…
Competitive programming intro
The judge workflow, C to C++ bridge, constraint reading, submissions, verdicts, and templates.
- What competitive programming is — How online judges work, what Accepted means, and why constraints force algorithm choices.
- C to C++ bridge — The C++ tools students coming from C need first: streams, vector, string, pair, sort, references, lambdas, and STL containers.
- Reading statements and constraints — A repeatable workflow for turning problem text into edge cases, data structures, and a target Big-O.
- First problem walkthroughs — Three classic beginner judge problems, solved by reading the statement contract carefully.
- Submitting, verdicts, and templates — How to compile locally, run samples, interpret judge verdicts, and keep a clean CP template.
Foundations
How to think about algorithms and measure what they cost.
- Big-O in one sitting — What Big-O measures, the classes worth knowing, and how to derive one from a loop.
- Space complexity — Memory has a Big-O too — auxiliary space, recursion stacks, input space, and trade-offs.
- Time complexity in practice — Best, average, worst, amortized time, and what Big-O deliberately ignores.
NP-hardness & intractability
The complexity landscape beyond Big-O: P, NP, NP-complete, reductions, and what to do when a problem is hard.
- P, NP & verification — What 'efficient' means, the difference between solving and checking, and the P vs NP question.
- NP-complete, NP-hard & coping strategies — Reductions, the hardest problems in NP, the famous examples, and what to do when you hit one.
Arrays & strings
Contiguous memory, O(1) access, and the two-pointer trick.
- Arrays & two pointers — Why indexing is O(1), why inserting in the middle isn't, and the two-pointer pattern.
- The sliding window — Turn an O(n·k) scan into a single O(n) pass by reusing the overlap.
Bit manipulation
Think in binary: operators, the standard bit tricks, and subsets-as-integers bitmask DP.
- Binary, operators & bit tricks — How integers are stored, the six bit operators, and the tricks that show up everywhere.
Searching
Finding a value in a collection — and why sorted data changes everything.
- Linear search — The baseline: check every element until you find the target.
- Binary search — Halving a sorted array each step to find a value in O(log n).
- Ternary search — Splitting search into thirds, why it is O(log n), and why binary still usually wins.
Sorting
Putting things in order — five classic algorithms, watched live.
- Meet sorting — Why sorting matters, what makes one algorithm better, and a playground with all five.
- Bubble sort — The simplest sort, and a clean derivation of why it's quadratic.
- Merge sort — Divide in half, sort each half, merge — and solve the recurrence for O(n log n).
- Quick sort — Partition around a pivot, recurse — fast on average, with a worst case to respect.
- Insertion & selection sort — Two more O(n²) sorts — one shines on nearly-sorted data, one minimises writes.
Recursion
Functions that call themselves — base cases, the call stack, and trees of calls.
- Recursion & the call stack — Base case, recursive case, and how each call lives on the stack until it returns.
- Divide & conquer — Split a problem, solve smaller copies, and combine the answers with recurrence maths.
- Backtracking — Explore choices, and undo them when they hit a dead end.
Linked lists
Nodes connected by pointers — O(1) insertion, but no random access.
- Pointers first (C++) — The memory model behind linked lists: addresses, dereferencing, nullptr, and ownership.
- Linked lists — How nodes and pointers trade away indexing for cheap insertion at the ends.
- Stacks & queues from a list — The same nodes build two different structures — depending on which end you use.
Stacks & queues
Two restricted lists: last-in-first-out and first-in-first-out.
- Stacks (LIFO) — Push and pop from one end — the structure behind undo, parsing, and the call stack.
- Queues (FIFO) — Add at the rear, remove from the front — fairness, and breadth-first search.
- Where they shine — Bracket matching, undo histories, and the searches you've already met.
Hashing & hash tables
Turning keys into bucket indices for O(1) average lookup.
- Hash tables — How a hash function gives near-constant-time lookup, and what happens on a collision.
- Sets & the two-sum trick — How a hash set turns an O(n²) search into a single O(n) pass.
Trees & BSTs
Hierarchical structure, and the binary search tree's ordered layout.
- Trees & binary search trees — Nodes, children, and the ordering invariant that makes a BST searchable in O(log n).
- Searching a BST & why balance matters — Search follows one path down — fast when balanced, slow when not.
- Red-black trees — A self-balancing BST that uses colors and rotations to guarantee O(log n).
Tree traversals
The four ways to visit every node — and what each one is good for.
- Tree traversals — In-order, pre-order, post-order and level-order — see each visiting sequence light up.
- Depth-first vs breadth-first — Two ways to explore a tree — go deep, or go wide.
Heaps & priority queues
A complete binary tree in an array that always hands you the min (or max) in O(log n).
- The heap structure — Why a complete binary tree packs into an array, and the one invariant that makes it a heap.
- Sift up, sift down & the priority queue — Insert, extract-min, heapsort, and where priority queues show up in graph algorithms.
Graphs & representations
How to store a graph, traverse it with BFS/DFS, and order or component-split it.
- Representing a graph — Adjacency list vs matrix vs edge list, and the directed/undirected/weighted choices.
- Traversal, components, cycles & topological sort — BFS and DFS on a general graph, then the structural algorithms they unlock.
Pathfinding & Graphs
Searching mazes and networks: BFS, DFS, Dijkstra, A*, Bellman-Ford and Floyd-Warshall.
- Searching a grid — How the four classic searches explore space, and what 'shortest path' really means.
- Weighted graphs: Dijkstra & A* — Shortest paths with non-negative weights, priority queues, and admissible heuristics.
- Bellman-Ford — Shortest paths with negative edges, plus negative-cycle detection.
- Floyd-Warshall — All-pairs shortest paths with a compact dynamic-programming recurrence.
Minimum spanning trees
Connect every vertex with minimum total edge weight using Kruskal, Prim, and DSU.
- Spanning trees and MSTs — Tree vs spanning tree, why cycles are unnecessary, and what a minimum spanning tree optimizes.
- Kruskal and DSU — Sort edges by weight, accept safe edges, and use Union-Find to detect cycles.
- Prim's algorithm — Grow one connected tree with the cheapest edge crossing the current cut.
Greedy algorithms
Make the locally best choice and never look back — when an exchange argument proves it's optimal.
- The greedy method — When taking the locally best choice is globally optimal — and how to prove it.
- Kadane's maximum subarray — Scan once, greedily restarting or extending a running sum to find the best contiguous block.
- Classic greedy algorithms — Fractional knapsack, interval problems, and Huffman coding.
Divide & conquer
Split a problem into independent subproblems, solve them, and combine — with the Master Theorem to read the cost.
- The divide-and-conquer method — The three-step template, the Master Theorem, and fast power.
- Classic divide-and-conquer algorithms — Merge sort, counting inversions, the median of two sorted arrays, and majority voting.
Dynamic programming
Solve overlapping subproblems once and reuse the answers — 1D and 2D tables.
- DP foundations & 1D tables — Overlapping subproblems, memoization vs tabulation, and 1D DP on climbing stairs and coin change.
- 2D tables: grids, strings & knapsack — When a subproblem needs two indices: unique paths, edit distance, LCS, and 0/1 knapsack.
- Bitmask DP & the Travelling Salesman — Encode a subset in the bits of an integer, then DP over subsets — the assignment problem and Held-Karp TSP.
Strings & pattern matching
Find a pattern inside a text fast: the naive scan, KMP's failure function, and rolling hashes.
- Pattern matching: the naive scan — The substring-search problem and the straightforward O(n·m) sliding approach.
- KMP & the failure function — Never re-compare a matched prefix: precompute borders and skip in O(n + m).
Math for algorithms
The number theory and combinatorics that show up in contests: gcd, modular arithmetic, primes, and nCr.
- Divisibility, GCD & modular arithmetic — Euclid's algorithm, LCM, and arithmetic that stays inside a modulus.
- Primes, fast power & combinatorics — Sieve of Eratosthenes, binary exponentiation, modular inverse, and nCr mod p.
Game theory
Impartial games: winning/losing positions, Nim, and Sprague–Grundy numbers.
- Winning & losing positions — Impartial games, normal play, and computing W/L positions bottom-up.
- Nim & Sprague–Grundy — The XOR rule for Nim and Grundy numbers that compose independent games.