CS3000: Algorithms & Data

Syllabus

Schedule
This schedule will be updated frequently—check back often!


# Date Topic Reading HW
1 Mon 1/6 Welcome!
Slides		 --- HW1 Out: pdf, tex
Due Fri 1/17
2 Wed 1/8 Divide and Conquer: Mergesort, Asymptotic Analysis
Slides		 KT 5.1, 2.1-2.2 ---
3 Mon 1/13 Divide and Conquer: Karatsuba's Algorithm, Recurrences
Slides: Before Class, After Class		 KT 5.2, 5.5
Erickson II.1-3		 ---
4 Wed 1/15 Divide and Conquer: Selection, Binary Search
Slides: Before Class, After Class		 Erickson 1.5-1.7 HW2 Out: pdf, tex
Due Fri 1/24
- Mon 1/20 No Class (MLK Day) --- ---
5 Wed 1/22 Dynamic Programming: Key Concepts, Interval Scheduling
Slides: Before Class, After Class		 KT 6.1-6.2 HW3 Out: pdf, tex
Due Fri 1/31
6 Mon 1/27 Dynamic Programming: Segmented Least Squares, Adding Variables
Slides: Before Class, After Class		 KT 6.3-6.4 ---
7 Wed 1/29 Dynamic Programming: Knapsack, Edit Distance
Slides: Before Class, After Class		 KT 6.6-6.7 HW4 Out: pdf, tex
Due Fri 2/7
8 Mon 2/3 Dynamic Programming: More Examples
Slides: Before Class, After Class		 --- ---
9 Wed 2/5 Graph Algorithms: Key Definitions, DFS
Slides: Before Class, After Class		 KT 3.1-3.3, 3.5-3.6 ---
- Mon 2/10 No Class (Illness) --- ---
- Wed 2/12 Midterm I (In Class) --- ---
- Mon 2/17 No Class (President's Day) --- ---
10 Wed 2/19 Graph Algorithms: Finish DFS, Topological Sort
Slides: Before Class, After Class		 KT 3.4 HW5 Out: pdf, tex
Due Fri 2/28
11 Mon 2/24 Shortest Paths: BFS, Start Dijkstra
Slides: Before Class, After Class		 KT 3.4, 4.4, 2.5 ---
12 Wed 2/26 Shortest Paths: Finish Dijkstra, Bellman Ford
Slides: Before Class, After Class		 KT 6.8-6.10 HW6 Out: pdf, tex
Due Fri 3/20
- Mon 3/2 No Class (Spring Break) --- ---
- Wed 3/4 No Class (Spring Break) --- ---
13 Mon 3/9 Graph Algorithms: Minimum Spanning Trees
Slides: Before Class, After Class		 KT 4.5-4.6 ---
14 Wed 3/11 Network Flow: Flows, Cuts, Augmenting Paths
Slides: Before Class, After Class		 KT 7.1-7.2 HW7 Out: pdf, tex
Due Fri 3/27
- Mon 3/16 No Class (All Hell Broke Loose) --- ---
15 Wed 3/18 Network Flow: Choosing Good Augmenting Paths
Lecture Recording		 Erickson 23.6 ---
16 Mon 3/23 Applications of Network Flow: Reductions, Bipartite Matching
Lecture Recording, Slides		 KT 7.5-7.6 ---
17 Wed 3/25 Applications of Network Flow: More Applications
Before Class, After Class, Lecture Recording		 KT 7.8-7.12 ---
18 Mon 3/30 Greedy Algorithms: Proof Strategies
Before Class, After Class, Lecture Recording		 KT 4.1-4.3
19 Wed 4/1 Midterm II (In Class) --- HW8 Out: pdf, zip
Due Fri 4/10
20 Mon 4/6 No Class (Technical Difficulties) --- ---
20 Wed 4/8 Greedy Algorithms: Huffman Codes
Before Class, After Class, Lecture Recording		 KT 4.8 ---
21 Mon 4/13 Stable Matching
Before Class, After Class, Lecture Recording		 KT 1.1 ---
- Fri 4/24 Final Exam: 8am-10am Location TBD --- ---