Mon, Aug. 21st 
Introduction and administrivia, what is an algorithm, induction review, growth of functions and asymptotic notation

CLRS 1, 2.1–2.2, and 3.1; Erickson Appendix I;
notes


Wed, Aug. 23rd 
More induction, asymptotic notation continued 
CLRS 3; Erickson Appendix I;
notes


Mon, Aug. 28th 
Recursion, divideandconquer, Tower of Hanoi, merge sort, recurrences 
CLRS 2.3, 4–4.1, 4.3; Erickson 1–1.6;
notes

Homework 1 assigned 
Wed, Aug. 30th 
Solving recurrences via transformations, recursion trees, and the master theorem 
CLRS 4.3–4.5; Erickson Appendix II;
notes


Mon, Sept. 4th 
No class; university closed for Labor Day 
Wed, Sept. 6th 
More divideandconquer, quicksort, quickselect, linear time selection 
CLRS 7–7.2; Erickson 1.5–1.7;
notes

Homework 1 due (solutions);
Homework 2 assigned

Mon, Sept. 11th 
HW 1 review, linear time selection, Fibonacci numbers, dynamic programming 
CLRS 9.3; Erickson 1.7, 5.1;
notes


Wed, Sept. 13th 
Dynamic programming, Fibonacci numbers, rod cutting 
CLRS 1515.1; Erickson 5.1, 5.3;
notes

Homework 2 due (solutions);
Homework 3 assigned

Mon, Sept. 18th 
More dynamic programming, longest increasing subsequence, edit distance introduction 
CLRS 15.3; Erickson 5.2–5.5;
notes


Wed, Sept. 20th 
More dynamic programming, edit distance, finding solutions and saving space 
Erickson 5.1.4, 5.5;
notes

Homework 3 due (solutions);
Homework 4 assigned

Mon, Sept. 25th 
Greedy algorithms, tape storage, class scheduling 
CLRS 16–16.2; Erickson 7.1–7.3;
notes


Wed, Sept. 27th 
More greedy algorithms, Huffman codes 
CLRS 16.3; Erickson 7.4;
notes

Homework 4 due (solutions);
Homework 5 assigned

Mon, Oct. 2nd 
Midterm Review: Bring questions about homework or other problems! 


Wed, Oct. 4th 
Midterm Exam: 7:00pm to 9:00pm in
AD 2.232;
questions, solutions

Mon, Oct. 9th 
Graph representations, graph traversal 
CLRS 22–22.1; Erickson 18;
notes


Wed, Oct. 11th 
More graph traversal, depthfirst search, DAGs 
CLRS 22.2–22.4; Erickson 19–19.5;
notes

Homework 5 due (solutions);
Homework 6 assigned

Mon, Oct. 16th 
Topological sort, midterm review 
CLRS 22.4; Erickson 19.5–19.6;
notes


Wed, Oct. 18th 
Minimum spanning trees, Kruskal's algorithm, Borvka's algorithm 
CLRS 23; Erickson 20;
notes

Homework 6 due (solutions);
Homework 7 assigned

Mon, Oct. 23rd 
More minimum spanning trees, Jarník's (Prim's) algorithm, single source shortest paths,
Dijkstra's algorithm 
CLRS 24.0, 24.3, 24.5; Erickson 21.1–21.4;
notes


Wed, Oct. 25th 
More single source shortest paths, Shimbel's algorithm (BellmanFord), shortest and
longest paths in DAGs 
CLRS 24.1–24.2; Erickson 21.6–21.7;
notes

Homework 7 due (solutions);
Homework 8 assigned

Mon, Oct. 30th 
All pairs shortest paths, Johnson's algorithm, dynamic programming, the FloydWarshall
algorithm 
CLRS 25.0, 25.2–25.3; Erickson 22–22.5, 22.7;
notes


Wed, Nov. 1st 
Maximum flows, minimum cuts, the maxflow mincut theorem 
CLRS 26–proof of Theorem 26.6 (in Section 26.2); Erickson 23–23.3;
notes

Homework 8 due (solutions);
Homework 9 assigned

Mon, Nov. 6th 
Maximum flow and minimum cut algorithms, FordFulkerson, EdmondsKarp fat pipes,
EdmondsKarp short pipes 
CLRS 26.2; Erickson 23.4–23.6;
notes


Wed, Nov. 8th 
Applications of maximum flow and minimum cut, edge and vertex disjoint paths, maximum
bipartite matching, the assignment problem, baseball elimination 
CLRS 26.3; Erickson 24.1–24.5;
notes

Homework 9 due (solutions);
Homework 10 assigned

Mon, Nov. 13th 
P vs NP, NPhardness and NPcompleteness, CircuitSAT, SAT 
CLRS 34–34.4.'Formula satisfiability'; Erickson 30.1–30.3, 30.5;
notes


Wed, Nov. 15th 
More NPhardness, 3SAT, MaxIndSet, MaxClique, MinVertexCover, 3Coloring, problem survey 
CLRS 34.4.'3CNF satisfiability'–34.5.2; Erickson 30.6–30.12, 30.14;
notes

Homework 10 due (solutions)

Mon, Nov. 20th 
No class; university closed for Fall Break 
Wed, Nov. 22nd 
No class; university closed for Fall Break 
Mon, Nov. 27th 
Amortized analysis, binary counters 
CLRS 17–17.3; Erickson 15;
notes

Homework 11 assigned

Wed, Nov. 29th 
More amortized analysis, dynamic arrays, splay trees 
CLRS 17.4; Erickson 16.5–16.8;
notes


Mon, Dec. 4th 
Review 
notes


Wed, Dec. 6th 
Review 
Bring questions from homework or readings!

Homework 11 due (solutions)

Mon, Dec. 11th 
Final Exam: 8:00pm to 10:45pm in
AD 2.232;
questions, solutions
