CS 217: Algorithm Design and Analysis, Fall 2015

CS 217: Algorithm Design and Analysis, Fall 2015

Jiaotong University



Click here for a page containing all the material (slides and notes made by me) I uploaded.
Click here for slides of the presentations.
Click here for news and announcements.
Click here for presentation topics.

Time:

 Monday 16:00-17:40, even Thursdays 08:00 - 10:40

Location:

 东下院 103 (Dongxiayuan 103)

Teacher:

 Dominik Scheder

Teaching Assistant:

 Li Jiajun, Liu Zhengyang

Textbook:

 Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani

Office hours:

 To be announced. In the meantime, just contact me by email.

Grading:

 40% homework assignment (including presentations), 60% graded final exam

Homework:

Every other week I will hand out homework assignment problems. The students will work on them in small groups (3-4 people) and hand them in the following week. Each group is required to make at least one short presentation of their problem solution during the semester.

Contents:

Contents of this class are: Classical algorithms and algorithmic design paradigms (e.g. divide and conquer, greedy algorithms, dynamic programming); maximum flow and minimum cut; Linear programming (duality, simplex, applications). We will also discuss some important data structures and how to use them in algorithms. Depending on the time frame, we will teach more advanced topics like randomized, approximation, exponential, and streaming algorithms.

We will devote ample time to: (i) the path from a basic idea to the final algorithm; (ii) proofs of correctness; (iii) running time analysis.

Goals: Deep understanding of the mathematical strcuture underlying the algorithms we treat in class. Ability to apply learned methods and paradigms to new problems.



f1
Week Date # TopicMaterial and Assignments
Week 1 Monday 2015-09-141 Introduction, Mergesort, Karatsuba Multiplication. slides of the first lecture
Week 2 Monday 2015-09-212 Recursion with look-up table. Dynamic programming. Greedy algorithms: Kruskal's algorithm for finding the minimum spanning tree. Cut property. Running time of Kruskal's algorithm.
Week 2 Thursday 2015-09-243 Data structures needed for Kruskal's algorithm: Union find.
Week 3 Monday 2015-09-284 Union find: Path compression, log*(n) upper bound. Greedy ln(n) approximation algorithm algorithm for Set Cover. First homework assignment. Here is the .tex version.
Week 4 Monday 2015-10-055 No class: National Holiday!
Week 4 Thursday 2015-10-086 Shortest paths in graphs; Introduction to network flows. Residual networks. Assignment 1 due.
Week 5 Monday 2015-10-127 Network flows, residual networks, capacity of cuts. Ford-Fulkerson method. Maximum flow = minimum cut. Edmonds-Karp algorithm and proof of termination.
Week 6 Monday 2015-10-198 Dinic' algorithm. Better running time on unit capacity networks. Matchings: Algorithm and Hall's theorem. Assignment 2 handed out. I posted some links to lecture notes on Maximum Flow on the news page.
I maded some slides on why the Edmonds-Karp algorithm terminates after O(nm) iterations.
Week 6 Thursday 2015-10-229 Presentation:
Dumb Ways to Die: Fibonacci Heaps.
Wallace: Counting the number of spanning trees.
Week 7 Monday 2015-10-2610 Presentation:
Group "Empty": Stoer-Wagner algorithm for global mincut in undirected graphs.
Second half: Hall's theorem, König's theorem, Mirsky's and Dilworth's theorem for partially ordered sets. 		Assignment 2 due. I made some notes on Hall's and König's theorem.
Week 8 Monday 2015-11-0211 Introduction to linear programming. Upper bounds via linear combinations of inequalities; via an economic interpretation. Formal dualization. Dualization of LPs in general form (inequality and equality constraints, non-negative and unrestricted variables). The Weak Duality Theorem. Assignment 3 handed out.
Week 8 Thursday 2015-11-0512 Practical applications of linear programming: How to write certain problems as an LP. Theoretical applications: LP relaxations, minimum vertex cover, integrality gap, LP is exact for bipartite graphs. I made some notes on Integer programs, relaxations, integrality gap, at the example of Vertex Cover.
Week 9 Monday 2015-11-0913 Integrality gap is 1 for Maximum matching on bipartite graphs. Existence of optimal solutions. First steps towards Strong LP Duality: Farkas Lemma (statement, no proof). Assignment 3 due.
Week 10 Monday 2015-11-1614 From Farkas Lemma to strong LP dualiy. LP complementary slackness theorem. Towars a proof of Farkas Lemma using Fourier-Motzkin elimination. Assignment 4 handed out on Wednesday, November 18.
There is a small typo / ambiguity in the homework file. I corrected it (see the red text in the file).
A bonus exercise
Week 10 Thursday 2015-11-1915 Proof of Farkas Lemma using Fourier-Motzkin elimination. Assignment 4 due on Thursday, November 26.
Week 11 Monday 2015-11-2316 Outlook of the remainder of the term. Karger's randomized mincut algorithm.
We had a poll about the topics for the rest of the term. You can see the results here.		 I also wrote a ``short'' (15 page) note on linear programming.
Week 12 Monday 2015-11-3017 Short review of probability theory: Expectation, variance, independence. Application to hashing: Two-wise independent hash functions.
Week 12 Thursday 2015-12-0318 Streaming algorithms: Estimating the number of distinct tokens. Homework 5 handed out on Saturday, 2015-12-05. It is due on Friday, 2015-12-11
Week 13 Monday 2015-12-0719 Streaming algorithms: More precise estimate of number of distinct tokens.
Week 14 Monday 2015-12-1420 Group Spicy Chicken: Zero-Sum Games
Week 14 Thursday 2015-12-1721 Presentation group "Vegetable" on Push-relabel algorithms for maximum flow.
Week 15 Monday 2015-12-2122 Presentations:
  • Group Xanadu: network flow with flow requirements
  • Group Libeccio: algorithms for geometric problems
 Assignment 6 handed out on Wednesday 2015-12-23.
Week 15 Monday 2015-12-2823 Presentation: Sky big on Edmonds' blossom algorithm for maximum cut Assignment 7 due.
Week 16 Thursday 2015-12-3124