Introduction to Algorithms

This page collects the handwritten lecture notes I compiled when I taught an introductory algorithms course at UCLA in Winter 2022, along with some useful links and copies of the exams I wrote for the class (with solutions).

Exams

Handwritten lecture notes

Each lecture title links to the notes for that lecture. For each lecture I have listed the corresponding sections in two introductory textbooks on algorithms: the book Algorithms by Dasgupta, Papadimitriou and Vazirani (denoted “DPV” in the table below) and the book Algorithm Design by Kleinberg and Tardos (denoted “K&T”).

Lecture Topic K&T Sections DPV Sections
1 Introduction
2 Big-Oh notation and time complexity 2.1, 2.2 0.3
3 Data structures and examples of running times 2.4
4 Greedy: Introduction 4.1, 4.2 5.3
5 Greedy: Proofs of correctness 4.3 5.3
6 Greedy: Heaps 2.5 4.5
7 Greedy: Approximation Algorithms 11.1, 11.2, 11.3 5.4
8 Divide & Conquer: Introduction 5.1, 5.2, 5.3 2.2
9 Divide & Conquer: Sorting and searching 5.1, 13.5 2.3
10 Divide & Conquer: Master theorem 5.4, 5.5 2.1, 2.4, 2.5
11 Dynamic Programming: Introduction 6.1 6.2
12 Dynamic Programming: Examples 6.4 6.4, 6.5
13 Dynamic Programming: Edit distance 6.5, 6.6, 6.7 6.3
14 Dynamic Programming: Arrays vs. Memoization 6.2
15 Graphs: Introduction and depth first search 3.1, 3.2, 3.3 3.1, 3.2
16 Graphs: Shortest paths 3.4, 4.4 4.1, 4.2, 4.3, 4.4
17 Graphs: More shortest paths 6.8, 6.9, 6.10 4.5, 4.6, 6.1, 6.6
18 Graphs: Floyd-Warshall and uses of DFS 3.5, 3.6 3.4, 3.5
19 Graphs: Minimum spanning trees 4.5 5.1
20 Graphs: More MST 4.5 5.1
21 Graphs: Network flow 7.1, 7.2 7.2
22 Graphs: Using network flow 7.5, 7.10 7.3
23 P vs. NP: Introduction 8.1, 8.3, 8.4 8.1, 8.2
24 P vs. NP: Reductions and completeness 8.2, 8.7, 8.10 8.3
25 Bonus lecture: Hashing 13.6 1.5
26 Bonus lecture: Sketching and streaming algorithms
27 Bonus lecture: Huffman Encoding 4.8 5.2