Mon, Aug. 20th 
What is/is not an algorithm, describing algorithms, administrivia

Erickson 0;
CLRS 2–2.2


Wed, Aug. 22nd 
Proof by induction

Erickson I


Mon, Aug. 27th 
Analyzing running time, asymptotic analysis, important functions

Lecture notes;
CLRS 3

Prerequisite form due;
Homework 1 assigned
(LaTeX solutions template)

Wed, Aug. 29th 
Recursion, Tower of Hanoi, Mergesort, divideandconquer

Erickson 1–1.6
;
CLRS 2.3, 4.0


Mon, Sept. 3rd 
No class; university closed for Labor Day

Wed, Sept. 5th 
Solving divideandconquer recurrences using recursion trees, Karastuba multiplication

Erickson 1.7, 1.9
;
CLRS 4

Homework 1 due (solutions);
Homework 2 assigned

Mon, Sept. 10th 
More divideandconquer, Quicksort, linear time selection

Erickson 1.5, 1.8
;
CLRS 7–7.2, 7.4.1; 9.0, 9.3


Wed, Sept. 12th 
Backtracking, n queens, game trees, string segmentation

Erickson 2

Homework 2 due (solutions);
Homework 3 assigned

Mon, Sept. 17th 
Dynamic programming, Fibonacci numbers, faster string segmentation

Erickson 3.1–3.5
;
CLRS 15–15.1, 15.3–15.4


Wed, Sept. 19th 
Sequence dynamic programming, edit distance, greed is bad

Erickson 3.5–3.9
;
CLRS 15.4

Homework 3 due (solutions);
Homework 4 assigned

Mon, Sept. 24th 
Dynamic programming with more interesting memoization, longest increasing subsequence,
maximum independent set in trees

Erickson 3.6–3.10
;
CLRS 15.2, 15.5


Wed, Sept. 26th 
Greedy algorithms, class scheduling, Huffman codes

Erickson 7
;
CLRS 16–16.3

Homework 4 due (solutions)

Mon, Oct. 1st 
Midterm review

Problems from previous homework assignments, lecture notes, or the textbook


Wed, Oct. 3rd 
Midterm Exam: 1:00pm to 2:15pm in
ECSS 2.306;
questions, solutions

Mon, Oct. 8th 
Graph basics, representations, data structures, whateverfirstsearch

Erickson 5
;
CLRS 22–22.2


Wed, Oct. 10th 
Whateverfirstsearch analysis, counting and labeling components, graph reductions, flood
fill

Erickson 5
;
CLRS 22–22.2

Homework 5 assigned

Mon, Oct. 15th 
Midterm debrief, midterm instructor feedback

Midterm questions and solutions


Wed, Oct. 17th 
Depthfirst search, detecting cycles, topological sort

Erickson 6
;
CLRS 22.3–22.4

Homework 5 due (solutions);
Homework R assigned

Mon, Oct. 22nd 
Topological sort, minimum spanning trees, Borůvka's algorithm

Erickson
6
,
7
;
CLRS 22.4, 23


Wed, Oct. 24th 
minimum spanning trees continued, the Prim–Jarník algorithm, Kruskal's algorithm,
single source shortest path properties (algorithms next week)

Erickson
7
,
8
;
CLRS 23, 24

Homework R due (solutions);
Homework 6 assigned

Mon, Oct. 29th 
Shortest paths, Dijkstra's algorithm, BellmanFordMooreShimbel

Erickson 8
;
CLRS 24


Wed, Oct. 31st 
Single source shortest paths via BellmanFordMooreShimbel, allpairs shortest paths,
FloydWarshall

Erickson
8
,
9
;
CLRS 24, 25

Homework 6 due (solutions);
Homework 7 assigned

Mon, Nov. 5th 
FloydWarshall allpairs shortest paths, maximum flow, minimum cut

Erickson
9
,
10–10.3
;
CLRS 25, 26–26.2


Wed, Nov. 7th 
Maxflowmincut theorem, maximum flow and minimum cut algorithms

Erickson 10.3–10.8
;
CLRS 26.2

Homework 7 due (solutions);
Homework 8 assigned

Mon, Nov. 12th 
EdmondsKarp shortest augmenting paths, flow and cut applications, edgedisjoint paths,
maximum matching, exam scheduling

Erickson
10.7–10.8
,
11
;
CLRS 26.2–26.3


Wed, Nov. 14th 
NPhardness, CircuitSAT, P versus NP, CookLevin theorem, SAT, 3SAT

Erickson 15.1–15.3, 15.5–15.6
;
CLRS 34–34.4.'Formula satisfiability'

Homework 8 due (solutions)

Mon, Nov. 19th 
No class; university closed for Fall break

Wed, Nov. 21st 
No class; university closed for Fall break

Mon, Nov. 26 
NPhardness, MaxIndSet, MaxClique, MinVertexCover, 3Color

Erickson 15.6–15.9
;
CLRS 34.4–34.5.3

Homework 9 assigned

Wed, Nov. 28th 
Approximation algorithms, load balancing, vertex cover

Erickson 31.1–31.5
;
CLRS 35–35.1


Mon, Dec. 3rd 
Review

Everything(?)


Wed, Dec. 5th 
More review

Problems from past homeworks, the lecture notes, and the textbook.

Homework 9 due by 1:15pm
(solutions)

Wed, Dec. 12th 
Final Exam: 2:00pm to 4:45pm in
ECSS 2.306;
questions, solutions
