**[Course description**
| **Schedule and handouts**
| **Discussion board**
| **Related material]**

- The final is comprehensive. You are welcome to bring one sheet of notes to the final.
- Our final will be on Wednesday, March 15 from 8:30 - 10:20 am in SMI 120.
**Note unusual location.**

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

- Wenbo Cui, office hour: Wednesday 4-5pm, CSE 218.
- Ziyao Huang, office hour: Thursday 5:45-6:45pm, CSE 218.
- Seokmin Kim, office hour: Friday 1-2pm, CSE 218.
- Kuikui Liu, office hour: Friday 3-4pm, CSE 220.
- Jingyi Yuan, office hour: Tuesday 4-5pm, CSE 218.

**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.

You are allowed to collaborate with your classmates to the extent of formulating ideas. When it comes to writing up solutions,

- [KT]: Algorithm Design by Kleinberg and Tardos.
- [DPV]: Algorithms by DasGupta, Papadimitriou and Vazirani.
- [TR]: MOOCs on Coursera by Tim Roughgarden