CS 5800, Northeastern University
Last updated Fall 2026
This page includes lecture materials for an introductory graduate course on the theory of algorithms. The lectures closely follow Algorithm Design by Kleinberg and Tardos, but also include topics from Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. The lecture notes are intended to pair with the Kleinberg and Tardos companion slides made by Kevin Wayne. I have made some additional slides which are posted below. I also run an optional advanced algorithm session outside of class each week and those materials are labelled (adv).
Introduction to Algorithms.
Algorithm Analysis. Big O, Omega, and Theta notation. Comparison of common runtimes.
Lecture notes (following Kevin Wayne's Algorithm Analysis slides)
Radix sort (adv)
Graph Algorithms. Graph definitions and structures. Traversal algorithms (BFS, DFS) pseudocode, data structures, runtime analysis. Bipartite testing. Strong connectivity testing. Directed graphs and strong connectivity. DAGs and topological sorting.
Lecture notes (following Kevin Wayne's Graphs slides)
Tarjan's algorithm for strongly connected components (adv)
Greedy Algorithms (1). Greedy algorithms for interval scheduling, interval partitioning, minimum lateness scheduling. Greedy-stays-ahead, structural, and exchange arguments for greedy optimality.
Lecture Notes (following Kevin Wayne's Greedy Algorithms I slides)
Gale-Shapley algorithm for stable matching (adv)
Greedy Algorithms (2). Dijkstra's algorithm for single source shortest paths. Prim's and Kruskal's algorithms for constructing minimum spanning trees. Union find data structure.
Lecture notes (following Kevin Wayne's Greedy Algorithms II slides)
Additional Slides
Huffman encoding (adv)
Divide and Conquer Algorithms.
Lecture notes
Closest pair of points in the plane
Dynamic Programming (1).
Lecture notes
Sequence alignment in linear space (adv)
Dynamic Programming (2).
Lecture notes
Floyd-Warshall algorithm for all pairs shortest paths (adv)
Network Flow.
Lecture notes
Preflow-push (push-relabel) algorithm for maximum flow.
Intractability.
Approximation Algorithms.
Randomized Algorithms (1).
Randomized Algorithms (2).
Outro.
Mathematical Review. Each semester I run optional sessions outside of class to reiterate prerequisite material with students. There are four sessions held over the first four weeks of class, covering the following material. The goal is to provide a refresher for students who may have been weak in discrete mathematics, or took the class a long time ago.
Basic data structures. Arrays, linked lists, stacks queues, binary trees, binary search trees, hash tables, min heaps.
Summations. Sum of the first n positive integers, sum of the first n squares, sum of the first n powers of 2, geometric series.
Proofs. Direct proof, proof by contradiction, counterexamples, proof by induction.
Probability. Sample spaces, events, random variables, independence, expected value, linearity of expectation.
Instructors. If you are using the textbook or Kevin Wayne's slides , feel free to email me for the tex files of any material posted here.