Fall 2016

Office | Office Hours | |
---|---|---|

Prof. Sofya Raskhodnikova | IST 343F | MW 4:30--5:30pm |

Nithin Varma (TA) | IST 359 | Th 3:30--5:30pm |

Date | Syllabus | Reading (reading in advance in bold) | Handouts/Homework | |
---|---|---|---|---|

Mon, Aug 22 | Introduction, stable matching (slides) | KT, Chap. 1 | General Information, Collaboration Policy | |

Wed, Aug 24 | Stable matching analysis, asymptotic growth (slides) |
KT, Chap. 2 (2.1,2.2,2.4) | Homework 1 out (pdf) | |

Mon, Aug 29 | Data structures. Graph traversals. (slides) | KT,
Chap. 3 | ||

Wed, Aug 31 | DFS and applications (slides) | KT, Chap. 3 (also CLRS 22.3) | Homework 2 out (pdf) | |

Mon, Sep 5 | Labor 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 12 | Greedy algorithms: scheduling problems (slides, demo of interval scheduling algorithm) | KT, Chap. 2.5, 4.1-4.3 | ||

Wed, Sep 14 | Greedy 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 19 | Greedy algorithms: MST, max-spacing clustering, and Huffman codes (slides) | KT, Chap. 4.5-4.8 | ||

Wed, Sep 21 | Divide 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 26 | Divide 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. 28 | Midterm 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. 17 | Finish Bellman-Ford, detecting negative-weight cycles, network flow (slides) | KT, Chap. 7.1-7.3 | ||

Wed, Oct. 19 | Peer-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. 2 | Review. Come prepared with questions. | Homework 9 out (pdf) | ||

Wed, Nov. 2 | Midterm 2, 08:15-10:15pm, 073 Willard | |||

Mon, Nov. 7 | Lecture by Nithin Varma (slides) | |||

Wed, Nov. 9 | Review flow. Linear programming: examples, forms (general, canonical, slack) (slides) | Erickson's chapter on linear programming | Homework 10 out (pdf) | |

Mon, Nov. 14 | Linear programming: more examples, started duality (slides), exam 2 is returned | |||

Wed, Nov. 16 | Linear 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. 30 | Classes P, NP and EXP; NP-completeness (slides) | KT, Chap. 8.3-8.4 | Homework 12 out (pdf) | |

Mon, Dec. 5 | 3D-Matching, coping with NP-completness (slides) | KT, Chap. 8.5-8.10, Chap. 10.1 | ||

Wed, Dec. 7 | Approximation algorithms (slides, demo of list scheduling) | KT, Chap. 11 | ||

Mon, Dec. 12 | Final exam, 8:00 AM - 9:50 AM, 067 Willard Bldg |

Sofya Raskhodnikova