back to teaching page



CS 214: Algorithms and Complexity, Fall 2016

Jiaotong University


Time: every Tuesday, 14:00 - 15:40; odd Thursdays, 10:00 - 11:40. Location:东下院100
Teacher: Dominik Scheder. Teaching Assistant: To be announced.
Textbook: Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani
Presentations: A list of suggested topics.
Material: This is mostly a blackboard class, but here is some material.

Grading: 40% final exam, 30% homework, 30% presentation. The stundents will form groups of size 4-5. Homework will be handed in by every group. Every group will give one 30 minutes presentation on a technical topic during the semester. For topics, you can contact me but are also welcome to come up with your own suggestion.

Contents and Goals: 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.

Date

Week

#

Content

Tuesday, September 13, 2016

Week 1

1

Class given by Yu Yu

Tuesday, September 20, 2016

Week 2

2

Class given by Yu Yu

Tuesday, September 27, 2016

Week 3

3

Euclid's algorithm, analyzing its running time. Fibonacci numbers, linear recurrences, and recursion versus dynamic programming. See some example python programs for computing Fibonacci numbers.

Thursday, September 29, 2016

Week 3

4

Homework 1 handed out on September 30; it is due October 9 by email to Xiao Tao

Tuesday, October 11, 2016

Week 5

5

Mergesort, worst case and best case; quicksort, worst case and expected case. Indicator variables Ai,j which are 1 if i is an ancestor of j.

Thursday, October 13, 2016

Week 5

6

In-class exercise: finding max and min with much fewer than 3n/2 - 2 comparisons; finding the second largest element with n+log(n)-2 comparisons.
Finding the kth largest element in linear time: quickselect (probabilistic) and median-of-medians (deterministic).

Homework 2 online since Friday, October 14.

Tuesday, October 18, 2016

Week 6

7

Graph algorithms. Kruskal's minimum spanning tree algorithm. Does it return a spanning tree? Is it of minimum cost? Implementing a union-find data structure: naive list approach and the "rename the smaller one" improvement; union by rank (without path compression).

Tuesday, October 25, 2016

Week 7

8

Shortest path algorithms: Breadth-first search, Dijkstra's algorithm. Priority queue data structures: binary heap.

Thursday, October 27, 2016

Week 7

9

Flow networks. Flows and cuts. Residual networks. The Ford-Fulkerson method for finding maximum flows.

Homework 3 handed out on Friday, October 28.

Tuesday, November 1, 2016

Week 8

10

Ford-Fulkerson plus shortest path: the Edmonds-Karp algorithm. Correctness: it returns a maximu flow; efficiency: it terminates after at most nm iterations of the while-loop. Proof of the maxflow-mincut theorem.

Tuesday, November 8, 2016

Week 9

11

Discussing parts of homework 3: the cut lemma.
Bipartite graphs. Matchings. How to find a maximum matching using maximum flow.

Homework 4 handed out.

Thursday, November 10, 2016

Week 9

12

Matchings and vertex covers: Hall's and König's Theorem.

Tuesday, November 15, 2016

Week 10

13

Introduction to linear programming. Feasible solutions, standard form, dualizations, weak LP duality.

Tuesday, November 22, 2016

Week 11

14

How to dualize linear programs with equality constraints and unbounded variables. Maximum Matching and Minimum Vertex Cover formulated as linear programs.

Thursday, November 24, 2016

Week 11

15

Proof that optimal solutions of Matching linear program and Vertex Cover linear program are integer for bipartite graphs.

Tuesday, November 29, 2016

Week 12

16

Farkas Lemma, Proof of Linear Programming Duality.

Presentation:

  • HK Journalists: Push-relabel algorithms. Slides.

Tuesday, December 6, 2016

Week 13

17

Presentations:

  • BigNews: The Stoer-Wagner algorithm for Global Minimum Cut. Slides.
  • Northern Lights: Karger's mincut algorithm Slides. .

Thursday, December 8, 2016

Week 13

18

Homework 5, handed out Wednesday, 2016-12-07.

Presentation:

  • Fantastic Five: Union-find data structure. Slides.
  • Minus One Second: Fibonacci heaps. Slides.
  • S05: Maximum Revenue Flow. Slides.

Tuesday, December 13, 2016

Week 14

19

Presentation:

  • LLWJJ: Schöning's random walk algorithm for k-SAT. Slides.
  • Captain China: Algorithms for 2-SAT. Slides.
  • Dominators: The Björklund-Husfeldt algorithm for Chromatic Number. Slides.
  • sixth sick sheik’s sixth sick sheep: Maximum Cut via SDP.

Tuesday, December 20, 2016

Week 15

20

Presentations:

  • Second++: Zero-sum games and Minmax Theorem. Slides.
  • Nogg: Non-zero-sum games. Slides.
  • Fibonado: Online Algorithms. Slides.

Thursday, December 22, 2016

Week 15

21

Presentation:

  • Bugmaker: Algorithms for Markov decision processes. Slides.
  • Philosohpy: Randomized Binary Search Trees. Slides.
  • Karatsuba: Suffix arrays and suffix trees Slides. .

Tuesday, December 27, 2016

Week 16

22

Presentations:

  • Pied Piper: Counting the number of spanning trees. Slides.
  • PlusOne: Counting Perfect Matchings Slides.
  • Triangle: Edmonds Blossom


back to teaching page