CSE 417: Algorithms and Computational Complexity (Winter 2016)

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

Important Announcements

Schedule and Handouts

This schedule is tentative.

%
Date Topic Videos discussed Reading
Jan 6 Administrivia, Introduction, Stable Matching Chapter 1 in [KT], Chapter 12 here
Mergesort, Intro divide and conquer I. Introduction (Week 1) Sections 0.3, 2.1-2.3 in [DPV], Section 5.1 in [KT]
Jan 13 Asymptotic analysis II. Asymptotic Analysis (week 1)

III. Divide & Conquer Algorithms (Week I) [First two segments]

 Section 2.2, 2.5 in [DPV]

Sections 2.1-2.2, 5.1-5.3, 5.5 in [KT]
Jan 15 More on divide and conquer

Inversions and Matrix multiplication

III. Divide & Conquer Algorithms (Week I) [Strassen's Subcubic Matrix Multiplication Method];

IX. Graphs and the Contraction Algorithm (Week 3) [First two segments]

X. Graph Search and Connectivity (Week 4) [First two segments]

 Counting inversions
Jan 20 Discussion of HW1
Jan 22 Graph search and connectivity X. Graph Search and Connectivity (Week 4) Chapter 3, 4.1-4.2 in [DPV]

Chapter 3 in [KT]
Jan 27 Basic graph algorithms continued
Jan 29 Graph algorithms continued
Feb 3 Greedy algorithms III. Introduction to Greedy Algorithms (Week 1) and IV. A Scheduling Application (Week 1) Sections 4.1-4.4 in [KT]
Feb 5 Greedy continued V. Prim's MST Algorithm (Week 1) and VI. Kruskal's MST Algorithm (Week 2) Sections 4.5-4.7 in [KT], 5.1 in [DPV]
Feb 10 Minimum spanning tree algorithms, Application to Clustering VII. Clustering (Week 2)
Feb 12 Midterm
Feb 17 Huffman codes IX. Huffman Codes (Week 2) Section 5.2 in [DPV], 4.8 in [KT]
Feb 19 Dynamic programming I X. Introduction to Dynamic Programming (Week 3) Chapter 6 in [DPV], Section 6.1-6.2 in [KT]
Feb 24 Dynamic programming II XI. The Knapsack Problem (Week 3) and XII. Sequence Alignment Sections 6.4-6.6 in [KT]
Feb 26 Additional DP examples Problems 6.2 and 6.7 in [DPV]
Mar 2 All Pairs Shortest Paths XV. All-pairs shortest paths
Mar 4 Bellman Ford XIV. The Bellman-Ford Algorithm (Week 4) Sections 6.8-6.10 in [KT]
Mar 9 NP-completeness XVI. NP-complete Problems (Week 5) Chapter 8 in [DPV]
Mar 11 Fun
Mar 16 Final 8:30 - 10:20am

In PCAR 192

Course Details

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Time: Wednesdays and Fridays in THO 125, 9:00-10:20am
Office hours:  Thursdays, 9:00 -- 10:00am and by appointment -- send email.

Teaching Assistants Office hours Email
Kiana Ehsani Tuesdays, 4:30 - 5:30pm, CSE 220 kianae@cs
Yang (Daniel) Li Wednesdays, 4-5pm, CSE 218 dyli@cs
Robert Weber Thursdays, 5-6pm, CSE 220 rtweber2@cs

Course evaluation: homework (~45%), midterm/quizzes (~30%), final (~25%).

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.

This quarter I will be experimenting with flipping the classroom.

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.

Related Material

Books: