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

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

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

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

Tue, Apr. 9th 


Homework 4 due (tentative)

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

Tue, Apr. 30th 


Homework 5 due (tentative)

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