CSE 417: Algorithms and Computational Complexity (Winter 2017)

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


Important Announcements


Schedule and Handouts

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.

+ examples from [TR] here and here

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

Course Details

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

Class mailing list

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.

Academic Integrity and Collaboration:
You are allowed to collaborate with your classmates to the extent of formulating ideas. When it comes to writing up solutions, no collaboration is permitted. On the homework you submit, please include a list of all the people that you discussed the problems with. You may not consult written materials other than the course materials in coming up with your solutions. Needless to say, you are expected to maintain the utmost level of academic integrity in the course.


Books and Resources