CSE 565: Algorithm Design and Analysis
Fall 2016

Course Staff

Office Office Hours
Prof. Sofya Raskhodnikova IST 343F MW 4:30--5:30pm
Nithin Varma (TA) IST 359 Th 3:30--5:30pm

Lecture Notes, Reading, Homework

DateSyllabusReading (reading in advance in bold)Handouts/Homework
Mon, Aug 22 Introduction, stable matching (slides) KT, Chap. 1 General Information, Collaboration Policy
Wed, Aug 24Stable matching analysis, asymptotic growth (slides) KT, Chap. 2 (2.1,2.2,2.4) Homework 1 out (pdf)
Mon, Aug 29Data structures. Graph traversals. (slides) KT, Chap. 3
Wed, Aug 31DFS and applications (slides) KT, Chap. 3 (also CLRS 22.3) Homework 2 out (pdf)
Mon, Sep 5Labor day -- no lecture.
Wed, Sep 7 Topological sort, strongly connected components (slides) KT, Chap. 3 (also CLRS 22.3-22.5) Homework 3 out (pdf)
Mon, Sep 12Greedy algorithms: scheduling problems (slides, demo of interval scheduling algorithm) KT, Chap. 2.5, 4.1-4.3
Wed, Sep 14Greedy algorithms for graph problems: shortest paths and MST (slides), Erickson's chapter on shortest paths KT, Chap. 4.4-4.5 Homework 4 out (pdf)
Mon, Sep 19Greedy algorithms: MST, max-spacing clustering, and Huffman codes (slides) KT, Chap. 4.5-4.8
Wed, Sep 21Divide and conquer: merge sort, counting inversions, binary search, exponentiation. Solving recurrences: recursion tree method, Master theorem, (optional) Akra-Bazzi method (slides, demos of merge and merge&count) KT, Chap. 5.1-5.3
Mon, Sep 26Divide and conquer: closest pair, integer and matrix multiplication, median and order statistics (slides) KT, Chap. 5.4-5.5, CLRS
Wed, Sep. 28 Review Homework 5 out (pdf)
Wed, Sep. 28Midterm 1, 08:15-10:15pm, 073 Willard
Mon, Oct. 3 Dynamic programming: Fibonacci numbers, weighted interval scheduling, longest common subsequence (slides) KT, Chap. 6.1-6.2, 6.6-6.7; Erickson's book
Wed, Oct. 5 Dynamic programming: segmented least squares, Knapsack problem (slides) KT, Chap. 6.3-6.4 Homework 6 out (pdf)
Mon, Oct. 10 Guest lecture by Piotr Berman on FFT (slides on FFT) KT, Chap. 5.6
Wed, Oct 12 Dynamic programming: RNA Secondary Structure, Bellman-Ford (slides) KT, Chap. 6.5, 6.8-6.9 Homework 7 out (pdf)
Mon, Oct. 17Finish Bellman-Ford, detecting negative-weight cycles, network flow (slides)KT, Chap. 7.1-7.3
Wed, Oct. 19Peer-grading exercise, Max-Flow Min-Cut Theorem, Ford-Fulkerson (slides, demo of Ford-Fulkerson)KT, Chap. 7.1-7.3 Homework 8 out (pdf)
Mon, Oct. 24 Max-Flow algorithms, applications: max bipartite matching (slides) KT, Chap. 7.5-7.6
Wed, Oct. 26 Applications of flow: bipartite matching and disjoint paths (slides)KT, Chap. 7.5-7.6
Mon, Oct. 31 Applications and extensions of flow (slides) KT, Chap. 7.7-7.11
Wed, Nov. 2Review. Come prepared with questions. Homework 9 out (pdf)
Wed, Nov. 2Midterm 2, 08:15-10:15pm, 073 Willard
Mon, Nov. 7 Lecture by Nithin Varma (slides)
Wed, Nov. 9Review flow. Linear programming: examples, forms (general, canonical, slack) (slides) Erickson's chapter on linear programming Homework 10 out (pdf)
Mon, Nov. 14Linear programming: more examples, started duality (slides), exam 2 is returned
Wed, Nov. 16Linear programming: duality (slides) Homework 11 out (pdf)
Week of Nov. 21 to Nov. 25 Thanksgiving break: no lectures
Mon, Nov. 28 Computational intractability: poly-time reductions (slides) KT, Chap. 8.1-8.2
Wed, Nov. 30Classes P, NP and EXP; NP-completeness (slides)KT, Chap. 8.3-8.4 Homework 12 out (pdf)
Mon, Dec. 53D-Matching, coping with NP-completness (slides) KT, Chap. 8.5-8.10, Chap. 10.1
Wed, Dec. 7Approximation algorithms (slides, demo of list scheduling) KT, Chap. 11
Mon, Dec. 12 Final exam, 8:00 AM - 9:50 AM, 067 Willard Bldg

Miscellaneous

Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.
LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a tex editor for Windows; ShareLatex is a web-based latex system (allows you to avoid latex installation on your machine).
Not so short intro to latex; a latex tutorial.
Homework template files: tex, pdf, cls, jpg.

Sofya Raskhodnikova