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, divide-and-conquer
|
Erickson 1–1.6
;
CLRS 2.3, 4.0
|
|
Mon, Sept. 3rd |
No class; university closed for Labor Day
|
Wed, Sept. 5th |
Solving divide-and-conquer recurrences using recursion trees, Karastuba multiplication
|
Erickson 1.7, 1.9
;
CLRS 4
|
Homework 1 due (solutions);
Homework 2 assigned
|
Mon, Sept. 10th |
More divide-and-conquer, 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, whatever-first-search
|
Erickson 5
;
CLRS 22–22.2
|
|
Wed, Oct. 10th |
Whatever-first-search 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 |
Depth-first 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, Bellman-Ford-Moore-Shimbel
|
Erickson 8
;
CLRS 24
|
|
Wed, Oct. 31st |
Single source shortest paths via Bellman-Ford-Moore-Shimbel, all-pairs shortest paths,
Floyd-Warshall
|
Erickson
8
,
9
;
CLRS 24, 25
|
Homework 6 due (solutions);
Homework 7 assigned
|
Mon, Nov. 5th |
Floyd-Warshall all-pairs shortest paths, maximum flow, minimum cut
|
Erickson
9
,
10–10.3
;
CLRS 25, 26–26.2
|
|
Wed, Nov. 7th |
Maxflow-mincut 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 |
Edmonds-Karp shortest augmenting paths, flow and cut applications, edge-disjoint paths,
maximum matching, exam scheduling
|
Erickson
10.7–10.8
,
11
;
CLRS 26.2–26.3
|
|
Wed, Nov. 14th |
NP-hardness, CircuitSAT, P versus NP, Cook-Levin theorem, SAT, 3-SAT
|
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 |
NP-hardness, 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
|