Date 
Subject/Event 
Reading 
Notes 
Tue, Jan. 15th 
Administrivia, what is an algorithm?, designing and analyzing algorithms

Erickson 0;
CLRS 2–2.2;
lecture notes


Thur, Jan. 17th 
Asymptotic analysis, induction

Erickson
I,
Erickson 1,
Lemma 1.1;
CLRS 3;
lecture notes;
Polished notes on asymptotics


Tue, Jan. 22nd 
Reduction and recursion, merge sort, divideandconquer, runtime recurrences

Erickson
1.1–1.6;
CLRS 2.3, 4.0;
lecture notes


Thur, Jan. 24th 
Runtime recurrences, recursion trees, Karastuba multiplication

Erickson
1.4–1.7, 1.9;
CLRS 4;
lecture notes


Tue, Jan. 29th 
Fast Fourier transforms

Erickson A;
CLRS 30;
lecture notes


Thur, Jan. 29th 
Finishing fast Fourier transforms, selection

Erickson A;
Erickson
1.5, 1.8;
CLRS 30;
CLRS 7–7.2, 7.4.1; 9.0, 9.3;
lecture notes


Tue, Feb. 5th 
Dynamic programming, Fibonacci numbers, rod cutting

Erickson
3.1–3.5
(see
Erickson
2 for more on backtracking);
CLRS 15–15.1, 15.3;
lecture notes

Homework 1 due
(LaTeX solution template)
(actual solutions)

Thur, Feb. 7th 
Sequence dynamic programming, edit distance (see also longest common subsequence in CLRS
15.4)

Erickson
3.5–3.7;
CLRS 15.4;
lecture notes


Tue, Feb. 12th 
Dynamic programming and trees, optimal binary search trees, maximum independent set in trees

Erickson
2.8;
Erickson
3.9–3.10;
CLRS 15.5;
lecture notes


Thur, Feb. 14th 
Finish maximum independent set in trees, greedy algorithms, class scheduling, start Huffman
codes

Erickson
3.10;
Erickson
4.2–4.4;
CLRS 16–16.3;
lecture notes


Tue, Feb. 19th 
Finish basic greedy algorithms, Huffman codes

Erickson
4.4;
Erickson
5.1–5.4;
CLRS 16.3;
CLRS 22–22.1;
lecture notes

Homework 2 due
(solutions)

Thur, Feb. 21st 
Midterm 1 review; your questions about past homeworks, concepts, or any textbook exercises
you want to know more about



Tue, Feb. 26th 
Midterm Exam 1: 10:00am to 11:15am in
ECSS 2.410

Midterm 1 problems and
solutions

Thur, Feb. 28th 
Graph basics review, breadthfirst search, depthfirst search

Erickson
5–5.6;
Erickson
6–6.2;
CLRS 22–22.3;
lecture notes


Tue, Mar. 5th 
Depthfirst search, topological sort, dynamic programming and DAGs

Erickson
6–6.4;
CLRS 22.3–22.4;
(CLRS 24.2 for shortest paths in DAGs);
lecture notes


Thur, Mar. 7th 
Minimum spanning trees, Kruskal's algorithm, the Prim–Jarník algorithm

Erickson 7;
CLRS 23;
lecture notes


Tue, Mar. 12th 
Single source shortest paths, Dijkstra's algorithm, BellmanFord

Erickson 8;
CLRS 24;
lecture notes


Thur, Mar. 14th 
Matroids (guest lecture by Jiashuai Lu)

Erickson
E;
CLRS 16.4–16.5;
slides

Homework 3 due
(solutions)

Tue, Mar. 19th 
No class; university closed for Spring break

Thur, Mar. 21st 
No class; university closed for Spring break

Tue, Mar. 26th 
Finish Dijkstra's algorithm, BellmanFord, slow allpairs shortest paths

Erickson 8;
Erickson 9–9.2,
9.5;
CLRS 24;
CLRS 25.0
lecture notes


Thur, Mar. 28th 
Allpairs shortest paths with FloydWarshall, maximum flows, minimum cuts

Erickson 9.8;
Erickson
10–10.3;
CLRS 25.2;
CLRS 26–26.2, basic algorithm;
lecture notes


Tue, Apr. 2nd 
Maxflow mincut theorem, FordFulkerson augmenting paths, EdmondsKarp improvements

Erickson
10–10.4, 10.6–10.7;
CLRS 26–26.2
lecture notes


Thur, Apr. 4th 
Applications of maximum flows, edge/vertexdisjoint paths, maximum bipartite matching, exam
scheduling

Erickson
11;
CLRS 26.3
lecture notes


Tue, Apr. 9th 
Introduction to NPhardness, CircuitSAT, SAT, 3SAT

Erickson
12–12.6;
CLRS 34–34.4
lecture notes

Homework 4 due
(solutions)

Thur, Apr. 11th 
Midterm 2 review; your questions about past homeworks, concepts, or any textbook exercises
you want to know more about



Tue, Apr. 16th 
Midterm Exam 2: 10:00am to 11:15am in
ECSS 2.410

Midterm 2 problems and
solutions

Thur, Apr. 18th 
NPhardness proofs, 3SAT, MaxIndSet, MaxClique, MaxVertexCover

Erickson
12.6–12.10;
CLRS 34.4–34.5.2
lecture notes


Tue, Apr. 23rd 
More NPhardness proofs, MaxVertexCover, 3Color, HamiltonianCycle, SubsetSum

Erickson
12.9–12.12;
CLRS 34.5.2–34.5.5
lecture notes


Thur, Apr. 25th 
Semester review; your questions about anything (except Homework 5)



Tue, Apr. 30th 
Half a QE practice exam

Exercises from Erickson and Problems from CLRS

Homework 5 due
(solutions)

Thur, May 2nd 
More QE practice exam

More exercises from Erickson and Problems from CLRS


Thur, May 9th 
Final Exam: 11:00am to 1:45pm in
ECSS 2.410

Final Exam problems and
solutions
