Algorithms

How to design an algorithm, and how to know it is good

About this course

Algorithm design and analysis from first principles — asymptotics, the major design paradigms, the data structures that make them work, and the boundary where efficient solutions stop existing.

What you will be able to do

  • Analyse running time and space with asymptotic notation, and justify the bound
  • Apply divide and conquer, greedy and dynamic programming to unseen problems
  • Choose the data structure a problem actually needs, and say why
  • Design and analyse algorithms on graphs
  • Recognise NP-complete problems and argue about intractability

What this course covers

  • Activity Selection by Earliest Finish Time
  • Greedy Algorithm Strategy and Conditions
  • Huffman Coding
  • When Greedy Fails: Zero-One Knapsack and Coin Change
  • The Exchange Argument Proof Template
  • Minimum Spanning Trees: Kruskal and Prim
  • Clause Nine: Greedy as a Proof Obligation
  • Algorithm definition and RAM cost model
  • Loop invariants and correctness proofs
  • Efficiency, growth rates, and the growth hierarchy
  • Insertion sort: algorithm, invariant, and runtime
  • Big-O notation: formal definition
  • Worked proofs: Big-O bound and worst-case count
  • Divide and Conquer Paradigm
  • Recursion Trees
  • The Master Theorem
  • Karatsuba Multiplication
  • Worked Unrollings and Lecture Summary
  • Hash functions and the compression problem
  • Collision resolution by chaining
  • The load factor alpha
  • Expected-constant-time and universal hashing
  • Open addressing and probe sequences
  • Deletion with tombstones in open addressing
  • Load-factor management and amortised rehashing
  • Graph vocabulary and representation
  • Breadth-first search and shortest paths
  • Depth-first search and timestamps
  • Queue vs. stack: why BFS gives distances and DFS does not
  • Topological sort via DFS finish times
  • Connected components and cycle detection
  • Clause twelve and lecture synthesis
  • Heap: array as complete binary tree
  • Sift-down (Max-Heapify) repair operation
  • Build-max-heap in linear time
  • Heapsort vs. Mergesort trade-offs
  • Heapsort algorithm
  • Data structure as algorithm — course spine clause four
  • Weighted graphs and shortest-path problem setup
  • Dijkstra's algorithm
  • Relaxation — the core operation
  • Bellman-Ford algorithm
  • DAG shortest paths
  • Floyd-Warshall algorithm
  • Negative cycles and algorithm selection summary
  • Three Asymptotic Bounds: Big-O, Omega, Theta
  • Best, Worst, and Average Case Spectrum
  • Amortized Analysis and the Doubling Array
  • The Limit Test for Asymptotic Classification
  • Clause Two of the Course Spine: Efficiency as a Band
  • Worked Proofs: Big-Theta and Amortized Total by Hand
  • Ordered dictionary and motivation for BSTs
  • Binary search tree structure and operations
  • The shape problem: height depends on insertion order
  • Rotations: the single shape-repair tool
  • Red-black trees: color-based height guarantee
  • AVL trees: balance-factor height guarantee via Fibonacci
  • Clause eight: invariant-maintained logarithm
  • Overlapping Subproblems and the DP Idea
  • Dynamic Programming Definition and Four-Step Recipe
  • Rod-Cutting Problem and Recurrence
  • Optimal Substructure and Cut-and-Paste Proof
  • Zero-One Knapsack via Two-Index Table
  • Memoization vs. Tabulation (Top-Down vs. Bottom-Up)
  • Clause Ten: Consider Every Choice, Solve Each Subproblem Once
  • Subproblem State Design for String DP
  • Longest Common Subsequence (LCS)
  • Edit Distance (Levenshtein Distance)
  • Matrix Chain Multiplication
  • Interval Dynamic Programming
  • DP Checklist: Six Design Questions
  • Clause Eleven: The State Is the Design
  • Three groundrules for complexity theory
  • P, NP, and the checking-vs-finding gap
  • Polynomial-time reductions and NP-hardness
  • The Cook-Levin theorem and the NP-complete family
  • The NP-complete problem family and pseudo-polynomial time
  • Approximation algorithms and ratio guarantees
  • Coping strategies for NP-complete problems
  • Partition: pivot placement in linear time
  • Quicksort: recursion and pivot-choice trade-offs
  • Comparison-sort lower bound via decision trees
  • Linear-time sorting: counting sort and radix sort
  • Clause five of the course spine: knowing your model and its floor
  • The Four Algorithmic Paradigms and Analysis Toolkit
  • Data Structures as Cost Decisions
  • The Decision Map: Routing an Unfamiliar Problem
  • Correctness Proof Techniques by Paradigm
  • The Spectrum of Computational Hardness
  • Randomized and Parallel Algorithm Frontiers
  • Further Frontiers and the Pivot to Machine Learning
  • Linear search on unsorted data
  • Binary search on sorted arrays
  • Order statistics and the selection problem
  • Quickselect (randomized select)
  • Median-of-medians pivot selection
  • The shrinking recurrence and linear worst-case proof
  • Clause six — don't sort to find; algorithm family summary

Syllabus

  1. Foundations and Asymptotics

    1. L1 · What Is an Algorithm?
    2. L2 · Analyzing Algorithms

  2. Divide and Conquer, Sorting and Searching

    1. L3 · Divide & Conquer
    2. L4 · Sorting I — Heaps and Heapsort
    3. L5 · Sorting II — Quicksort, Lower Bounds, Linear Time
    4. L6 · Searching & Selection

  3. Data Structures

    1. L7 · Hashing
    2. L8 · Balanced Search Trees

  4. The Design Paradigms

    1. L9 · Greedy Algorithms
    2. L10 · Dynamic Programming I
    3. L11 · Dynamic Programming II

  5. Graphs, Hardness and Synthesis

    1. L12 · Graph Algorithms I
    2. L13 · Graph Algorithms II
    3. L14 · NP-Completeness
    4. L15 · The Algorithmic Toolkit