[Course description
| Schedule and handouts
| Discussion board
| Related material]
| Date | Topic | Reading |
|---|---|---|
| Jan 6 | Administrivia, introduction and stable matching (and demo) | Chapter 1 in [KT]
Chapter 10 here |
| Jan 8 | Asymptotic analysis, poly time, big Oh , etc. | Sections 0.3 in [DPV],
Chapter 2 in [KT] |
| Jan 11 | Greedy algorithms | Sections 4.1-4.4 in [KT] |
| Jan 13 | Greedy cont. | |
| Jan 18 | Minimum spanning trees | Sections 4.5-4.7 in [KT], 5.1 in [DPV] |
| Jan 20 | Application to Clustering, Divide and Conquer intro + demo | Section 2.1, 2.2 in [DPV]
Sections 5.1-5.3 in [KT] |
| Jan 25 | More divide and conquer (multiplication) | Sections 5.5 in [KT], 2.5 in [DPV] |
| Jan 27 | Divide and conquer practice | |
| Feb 1 | Graphs | Chapter 3, 4.1-4.2 in [DPV]
Chapter 3 in [KT] |
| Feb 3 | Graphs cont. | |
| Feb 8 | Articulation points | other slides |
| Feb 15 | Dynamic programming | Chapter 6 in [DPV], Section 6.1-6.2, 6.4, 6.6 in [KT] |
| Feb 22 | More examples | |
| Feb 24 | Bellman Ford | Sections 6.8-6.10 in [KT] |
| Mar 1 | Computability | Great survey |
| March 3 | P vs NP |
Instructor: Anna Karlin,
CSE 594, tel. 543 9344
Time: Wednesdays and Fridays
in MGH 241, 9:00-10:20am
Office hours: Thursdays, 9:00 -- 10:00am and by appointment -- send email.
TAs: Office hours Tuesday, Wednesday 4-5pm; Thursday 5:30 - 6:30pm, Friday 1-2pm and 3-4pm. All office hours in CSE 218, except Friday 3-4pm when the office hours are in CSE 220.
When you have a question, please mail it to *all* staff (instructor + TAs): cse417-staff@cs.washington.edu
Course evaluation: homework (~55%), participation (~5%), final (~40%).
(I might replace a one or two homeworks with a quiz.)
Late homework policy: Homework turned in at most 24 hours late will be penalized 15%; homework turned in at most 48 hours late will be penalized 30%. After 48 hours, homework will no longer be accepted. (Of course, if there are special circumstances, then as long as you let me know about them in advance, we can make special special arrangements.)
Prerequisite: CSE 373
About this course:
We will study principles in the design of efficient algorithms: recursion, divide and conquer, greedy algorithms, dynamic programming etc. We will also explore computational intractability and NP-completeness.