Lecture notes on Algorithms

These notes are for an undergraduate course on algorithms, covering the usual topics, but with more of an emphasis on learning to do proofs than is found in most courses. We take the perspective that being able to verify correctness (via detailed proofs) is an integral part of learning to design algorithms.

draft of September 29, 2026, by N. Young. Built from github.com/nealeyoung/algs101.

Notes (PDF)

1. Preliminaries
2. Long-Form Proofs
3. Stable Matching
4. Divide and Conquer
5. Greedy Algorithms
6. Graph Traversal
7. Dynamic Programming
8. Flow, Reductions, and Linear Programming
9. NP

• Appendix A: Python code
• Appendix B: Homework assignments
• All lecture notes, as one book (PDF)

Homework assignments

1. Preliminaries, Long-Form Proofs, Stable Matching
   1. Asymptotic (Θ) notation
   2. Proof about big-O
   3. Proof by induction (a mysterious recursive function)
   4. An instance with only one stable matching
   5. Checking a proof about the 1951 algorithm
   6. PDF, template, Overleaf
2. Preliminaries, Stable Matching, Divide and Conquer
   1. Ordering functions by growth rate (big-O)
   2. Bounding sums (geometric sums)
   3. Recursion trees
   4. Recursion trees: a variant of mergesort
   5. Busy hospitals (prove or disprove)
   6. Lonely doctor (prove or disprove)
   7. PDF, template, Overleaf
3. Divide and Conquer
   1. Recurrences
   2. 2D Local Maximum: an incorrect algorithm
   3. Bus routes
   4. PDF, template, Overleaf
4. Greedy Algorithms
   1. Activity Selection (simulating rselect and iselect)
   2. Making Change: when is the greedy algorithm optimal?
   3. Puncturing Intervals: the greedy step
   4. PDF, template, Overleaf
5. Greedy Algorithms, Graph Traversal
   1. Puncturing Intervals: the full algorithm
   2. Breadth-first search
   3. Depth-first search
   4. PDF, template, Overleaf
6. Greedy Algorithms, Graph Traversal
   1. Depth-first search and topological sort
   2. Prim's algorithm (Minimum Spanning Tree)
   3. Minimum Spanning Tree: checking a conjecture and proof
   4. Dijkstra's algorithm
   5. Street sweeping (a DFS-based algorithm; HackerRank)
   6. PDF, template, Overleaf
7. Dynamic Programming
   1. Shortest path in a grid
   2. Making Change
   3. Counting Ways to Make Change
   4. Dijkstra's algorithm: a conjecture
   5. PDF, template, Overleaf
8. Dynamic Programming, Greedy Algorithms
   1. Scheduling light and heavy jobs
   2. Counting valid subsequences
   3. The Game of Piles
   4. Minimum Spanning Tree: the reverse-delete (cycleBreaker) algorithm
   5. PDF, template, Overleaf
9. Dynamic Programming, Flow
   1. Counting Subset Sums
   2. Smallest Subset Sum
   3. Three-Way LCS
   4. Finding a maximum flow and a minimum cut
   5. PDF, template, Overleaf
10. Flow, Reductions, LP
    1. Tiling by bars (via Bipartite Matching)
    2. Solving small linear programs
    3. Critical edges, or a conjecture about maximum flows
    4. PDF, template, Overleaf
11. Flow, Reductions, P and NP
    1. Family seating (via Max Flow)
    2. K-Path
    3. PDF, template, Overleaf

Code

The Python code, on GitHub (all files), by lecture note. Each lecture note also lists its code in its last section.

• Stable Matching (lecture note 3)
  • stable_matching.py
• Divide and Conquer (lecture note 4)
  • mergesort.py
  • closest_pair.py
  • selection.py
  • local_maximum.py
• Greedy Algorithms (lecture note 5)
  • library.py
  • activity_selection.py
  • Huffman.py
  • Dijkstra.py
  • min_spanning_tree.py
• Graph Traversal (lecture note 6)
  • graph_library.py
  • breadth_first_search.py
  • depth_first_search.py
• Dynamic Programming (lecture note 7)
  • graph_library.py
  • dynamic_programming_paths.py
  • making_change.py
  • subset_sum.py
  • knapsack.py
  • longest_increasing_subsequence.py
  • longest_common_subsequence.py
  • edit_distance.py
  • longest_palindrome.py
  • paragraph_layout.py
  • min_wt_triangulation.py
  • optimal_binary_search_tree.py
  • Bellman_Ford.py
  • Floyd_Warshall.py
• Max Flow, Reductions, and Linear Programming (lecture note 8)
  • graph_library.py
  • max_flow.py

© 2018–2026 Neal E. Young. The notes and homeworks are licensed under CC BY-NC-SA 4.0 and the code under the MIT License, except where noted; see LICENSE.