CS 214: Algorithms and Complexity, Fall 2015

CS 214: Algorithms and Complexity, Fall 2015

Jiaotong University



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

Time:

 Tuesday 14:00-15:40, odd Thursdays 10:00 - 11:40

Location:

 东上院 405 (Dongshangyuan 405)

Teacher:

 Dominik Scheder

Teaching Assistant:

 Xiao Tao

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.



Week Date # TopicMaterial and Assignments
Week 1 Tuesday 2015-09-151 Introduction, Mergesort, Karatsuba Multiplication slides of the first lecture
Week 1 Thursday 2015-09-172 Basic algorithmic paradigms: Dynamic programming, greedy algorithms. A cute combinatorial identity we discovered by chance after the class.
Week 2 Tuesday 2015-09-223 Kruskal's minimum spanning tree algorithm; correctness (cut lemma) and running time; union find data structure Assignment 1 handed out. Here is the .tex version.
Week 3 Tuesday 2015-09-294 Union find data structure: Union by rank; path compression (log*(n) amortized time) Assignment 1 due.
Week 3 Thursday 2015-10-01 No class: National Holiday
Week 4 Tuesday 2015-10-06 No class: National Holiday
Week 5 Tuesday 2015-10-135 Shortest paths in graphs. Introduction to Network Flows: Definitions; residual network; cuts and cut capacity.
Week 5 Thursday 2015-10-156 Network flows, residual networks, capacity of cuts. Ford-Fulkerson method. Maximum flow = minimum cut.
Week 6 Tuesday 2015-10-207 Edmonds-Karp algorithm for Maximum Flow; proof of termination; running time. Matchings in bipartite graphs: algorithm; Hall's theorem. Assignment 2 handed out (due 2015-10-27).
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 7 Tuesday 2015-10-278 Presentation.
  • Group N=NP: Fibonacci-Heaps.
  • Group 007: A tighter analysis of Union-Find.
 Assignment 2 due; presentations.
Week 7 Thursday 2015-10-299 Feed back for presentations; Hall's theorem; Vertex covers; König's Theorem; Graph orientations with in-degree constraints. I made some notes on Hall's and König's theorem.
Week 8 Tuesday 2015-11-0310 Introduction to Linear Programming: Examples; dual program. Assignment 3 handed out.
Week 9 Tuesday 2015-11-1011 Dualization for general LPs (with equalities; with unbounded variables). Integer Program for Maximum Matching and Vertex Cover. LP relaxation. Exactness of the Vector cover LP relaxation if the graph is bipartite. Assignment 3 due.
Week 9 Thursday 2015-11-1212 Exactness of the Matching LP relaxation for bipartite graphs. Existence of optimal solutions in LPs.
Week 10 Tuesday 2015-11-1713 LP duality: Farkas lemma in several versions; proof of the duality theorem. LP complementary slackness theorem. 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 11 Tuesday 2015-11-2414 Presentations.
  • Group 3: Push-relabel algorithms.
  • Group 6: Minmax Theorem.
 I put links to material on push-relabel and minmax on our news page.
I also wrote a ``short'' (15 page) note on linear programming.
Week 11 Thursday 2015-11-2615 Proof of Farkas Lemma using Fourier-Motzkin elimination. Outlook of the remainder of the semester. Assignment 4 due.
Week 12 Tuesday 2015-12-0116 Presentation: Group 8 on Non-zero sum games and Nash equilibria.

Introduction to complexity theory: NP-complete problems and reductions. 		Assignment 5 handed out. The news page has some links to lecture notes on push-relabel algorithms, zero-sum games, and non-zero sum games.
Week 13 Tuesday 2015-12-0817 Formal notion of reduction. Set cover and vertex cover.

Presentation: Group 2 on minimum cost flow.		 Assignment 5 due; presentations.
Week 13 Thursday 2015-12-1018 Presentation:
  • Group CHXZH on a polynomial-time algorithm for counting the number of spanning trees.
  • Group 7: Karger's randomized minimum cut algorithm.
Week 14 Tuesday 2015-12-1519 Presentations:
  • Group 5: Edmonds' blossom algorithm for maximum matching in general graphs.
  • Group ACM: An approximation for Maximum Cut based on semi-definite programming
 		Assignment 6 handed out on Wednesday, 2015-12-16.
Week 15 Tuesday 2015-12-2220 Presentation group 4 on the Stoer Wagner minimum cut algorithm Assignment 6 due; presentations.
Week 15 Thursday 2015-12-2421 Presentations:
  • Bro Huang's group: Maximum independent set using pairwise independence.
  • PY Sun & classmates: Problems from algorithmic geometry.
Week 16 Tuesday 2015-12-2922