CSE 417 – Calendar

24 Sep
Courses begin
1.1. Introduction and stable matching (Nathan/Glenn) K&T: 1.1 (p. 1-6 only) and slides(pptx) and slides(pdf) and video
25 Sep
26 Sep
1.2. Algorithm correctness (Glenn) reading and slides(pptx) and slides(pdf) and video and reference
HW1 Intro/Correctness
27 Sep
28 Sep
29 Sep
1.3. Proof techniques (Nathan) reading and slides(pptx) and slides(pdf) and postlecture slides(pptx) and postlecture slides(pdf) and video
30 Sep
1 Oct
1.4. Gale-Shapley analysis (Glenn) K&T: 1.1 (p. 7-12 only) and reading and slides(pptx) and slides(pdf) and video and reference
2 Oct
3 Oct
1.5. Running time (Nathan) K&T: 2.1-2.4 and reading and slides(pptx) and slides(pdf) and video
HW1 Intro/Correctness
HW2 Gale–Shapley/Running Time
4 Oct
5 Oct
6 Oct
2.1. Intro to divide and conquer (Nathan) reading and slides(pptx) and slides(pdf) and video
7 Oct
8 Oct
2.2. The technique of computing more (Nathan) reading and slides(pptx) and slides(pdf) and video
9 Oct
10 Oct
2.3. Sorting (Nathan) K&T 5.3-5.4 and reading and slides(pptx) and slides(pdf) and video(cse421 25wi)
HW2 Gale–Shapley/Running Time
HW3 Divide and Conquer
11 Oct
12 Oct
13 Oct
3.1. Graph traversal (Glenn) K&T: 3.1-3.4 and reading and slides(pptx) and slides(pdf) and video
14 Oct
15 Oct
3.2. Directed graphs (Glenn) reading and slides(pptx) and slides(pdf)
HW1 Intro/Correctness
16 Oct
17 Oct
3.3. Minimum spanning trees (Glenn) K&T: 4.5 and reading and slides(pptx) and slides(pdf)
HW3 Divide and Conquer
HW4 Graphs
18 Oct
19 Oct
20 Oct
3.4. Shortest paths (Glenn) K&T: 4.4 and reading and slides(pptx) and slides(pdf)
21 Oct
22 Oct
Flex/review (TBD) slides(pptx) and slides(pdf)
23 Oct
HW2 Gale–Shapley/Running Time
24 Oct
Quiz 1
25 Oct
26 Oct
27 Oct
4.1. Intro to dynamic programming (Nathan) reading and slides(pptx) and slides(pdf)
28 Oct
29 Oct
4.2. Adding new parameters (Nathan) K&T: 6.4, 6.8 and reading and slides(pptx) and slides(pdf) and implementation
HW3 Divide and Conquer
HW4 Graphs
30 Oct
31 Oct
4.3. DP on intervals (Nathan) K&T: 6.5 and reading and slides(pptx) and slides(pdf)
HW5 Dynamic Programming
1 Nov
2 Nov
3 Nov
4.4. DP on Graphs (Nathan) reading and slides(pptx) and slides(pdf)
4 Nov
5 Nov
5.1. Intro to greedy algorithms (Glenn) reading and slides(pptx) and slides(pdf)
6 Nov
7 Nov
5.2. Huffman codes (Glenn) K&T: 4.8 and reading and slides(pptx) and slides(pdf)
HW5 Dynamic Programming
HW6 Greedy Algorithms
8 Nov
9 Nov
10 Nov
5.3. Non-optimal greedy algorithms (Glenn) K&T: 11.1 and reading and slides(pptx) and slides(pdf)
HW4 Graphs
11 Nov
Veterans Day (no class)
12 Nov
6.1. Intro to flows (Nathan) K&T: 7.1 and reading and slides(pptx) and slides(pdf)
13 Nov
14 Nov
6.2. Flow modeling (Nathan) reading and slides(pptx) and slides(pdf)
HW6 Greedy Algorithms
HW7 Flows
15 Nov
16 Nov
17 Nov
6.3. Flows for matchings (Nathan) K&T: 7.5 and reading and slides(pptx) and slides(pdf)
18 Nov
19 Nov
Flex/review (TBD)
HW5 Dynamic Programming
20 Nov
21 Nov
Quiz 2
22 Nov
23 Nov
24 Nov
7.1. Intro to NP-completeness (Glenn) K&T: 8.3-8.4 and reading and slides(pptx) and slides(pdf)
25 Nov
26 Nov
7.2. Using SAT solvers (Glenn) reading and slides(pptx) and slides(pdf)
HW6 Greedy Algorithms
HW7 Flows
HW8 NP and SAT
27 Nov
Thanksgiving Day (no class)
28 Nov
Native American Heritage Day (no class)
29 Nov
30 Nov
1 Dec
7.3. Backtracking and SAT solving (Glenn) reading and slides(pptx) and slides(pdf)
2 Dec
3 Dec
7.4. Proving problems hard (Glenn) K&T: 8.1-8.2, 8.7 and reading and slides(pptx) and slides(pdf)
4 Dec
5 Dec
Courses end
Flex/final review (Nathan/Glenn) slides(pptx) and slides(pdf)
HW7 Flows
HW8 NP and SAT
HW8 NP and SAT
8 Dec
Final Exam