CSE417 - 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

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)

30 Sep

1 Oct

1.4. Gale-Shapley analysis (Glenn)

K&T: 1.1 (p. 7-12 only) and reading

2 Oct

3 Oct

1.5. Running time (Nathan)

K&T: 2.1-2.4

HW1 Intro/Correctness

HW2 Gale–Shapley/Running Time

4 Oct

5 Oct

6 Oct

2.1. Intro to divide and conquer (Nathan)

7 Oct

8 Oct

2.2. The technique of computing more (Nathan)

9 Oct

10 Oct

2.3. Sorting (Nathan)

K&T 5.3-5.4

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

14 Oct

15 Oct

3.2. Implication graphs (Glenn)

K&T: 3.5-3.6

HW1 Intro/Correctness

16 Oct

17 Oct

3.3. Minimum spanning trees (Glenn)

K&T: 4.5

HW3 Divide and Conquer

HW4 Graphs

18 Oct

19 Oct

20 Oct

3.4. Shortest paths (Glenn)

K&T: 4.4

21 Oct

22 Oct

Flex/review (TBD)

HW2 Gale–Shapley/Running Time

23 Oct

24 Oct

Quiz 1

HW4 Graphs

25 Oct

26 Oct

27 Oct

4.1. Intro to dynamic programming (Nathan)

28 Oct

29 Oct

4.2. Adding new parameters (Nathan)

K&T: 6.4, 6.8

HW3 Divide and Conquer

30 Oct

31 Oct

4.3. DP on intervals (Nathan)

K&T: 6.5

HW5 Dynamic Programming

1 Nov

2 Nov

3 Nov

4.4. DP on DAGs (Nathan)

4 Nov

5 Nov

5.1. Intro to greedy algorithms (Glenn)

HW4 Graphs

6 Nov

7 Nov

5.2. Scheduling problems (Glenn)

K&T: 4.1-4.2

HW5 Dynamic Programming

HW6 Greedy Algorithms

8 Nov

9 Nov

10 Nov

5.3. Non-optimal greedy algorithms (Glenn)

K&T: 11.1

11 Nov

Veterans Day (no class)

12 Nov

6.1. Intro to flows (Nathan)

K&T: 7.1

13 Nov

14 Nov

6.2. Flow modeling (Nathan)

HW6 Greedy Algorithms

HW7 Flows

15 Nov

16 Nov

17 Nov

6.3. Flows for matchings (Nathan)

K&T: 7.5

18 Nov

19 Nov

Flex/review (TBD)

HW5 Dynamic Programming

20 Nov

21 Nov

Quiz 2

HW7 Flows

22 Nov

23 Nov

24 Nov

7.1. Intro to NP-completeness (Glenn)

K&T: 8.3-8.4

25 Nov

26 Nov

7.2. Using SAT solvers (Glenn)

HW6 Greedy Algorithms

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)

2 Dec

3 Dec

7.4. Proving problems hard (Glenn)

K&T: 8.1-8.2, 8.7

HW7 Flows

4 Dec

5 Dec

Courses end

Flex/final review (Nathan/Glenn)

HW8 NP and SAT