back to teaching page


CS 214 and CS 217, Fall 2016

Jiaotong University

Topics for Presentations



Here is a list of possible presentation topics. You are also welcome to come up with your own suggestions. Some topics below contain obscure terms (push-relabel???). To find out what it is about, the internet is your friend. Once you settle for a topic, I can help you find material about it.
  1. Data Structures
    1. Randomized binary search trees.
      CS 214: Group Philosophy
    2. The union-find data structure, as needed for example in Kruskal's algorithm.
      CS 214: Group Fantastic Five.
      CS 217: Tarjan, Monday 11:06.
      Dexter Kozen's lecture notes.
    3. Fibonacci heaps.
      CS 214: Group -1s.
      CS 217: Group Paradox.
      David Kempe's lecture notes on Fibonacci heaps.

  2. Flows, cuts, matchings
    1. Push-relabel algorithms for maximum flow.
      CS 214: Group HK Journalists.
      Avrim Blum's lecture notes on push-relabel algorithms.
    2. Maximum revenue network flow.
      CS 214: S05.
      David Karger's lecture notes.
    3. Edmonds' blossom algorithm for maximum matching in general graphs.
      CS 214: Triangle.
      Uri Zwick's lecture notes.
    4. Karger's probabilistic minimum cut algorithm for undirected graphs.
      CS 214: Group Northern Light.
      Sanjeev Arora's lecture notes.
    5. Stoer-Wagner algorithm for minimum cut in undirected graphs.
      CS 214: Group BigNews.
      The original paper.

  3. Linear Programming
    1. Zero-sum games and von Neumann's Minmax Theorem.
      CS 214: Group Second++.
      CS 217: AlphaGorithm
      Here are some references:
    2. Non-zero-sum games and Nash equilibria.
      CS 214: Group Nogg.
      References: Konstantinos Daskalakis' course Games, Decision, and Computation. Chapter 2 is about non-zero sum games and Nash's Theorem.
    3. Algorithms for Markov decision processes.
      CS 214: Group BugMaker
      Thomas Dueholm Hansen's lecture notes, course by Uri Zwick.

  4. Miscellaneous
    1. Counting the number of spanning trees of a graph.
      CS 214: Group Pied Piper.
      See Chapter 8 of "An Invitation to Discrete Mathematics" by Matoušek and Nešetřil.
    2. An approximation algorithm for Maximum Cut using Semidefinite Programming.
      CS 214: Sixth sick sheikh's sixth sick sheep.
      Anupam Gupta and Ryan O'Donnell's lecture notes.
    3. A 3n and a 2n algorithm for d-colorability.
      Paper by Mikko Koivisto and Paper by Andreas Björklund and Thore Husfeldt.
    4. CS 214: Group Dominantors.
    5. Efficient algorithms for 2-Satisfiability.
      CS 217: Group Aha.
      CS 214: Group Captain China.
      See for example Emo Welzl's lecture notes on satisfiability, especially Chapter 3.
    6. Schöning's random walk algorithm for k-SAT.
      CS 214: Group LLWJJ.
      See for example Emo Welzl's lecture notes on satisfiability, especially Chapter 7, or Uwe Schöning's paper.
    7. FKT algorithm (Fisher, Kasteleyn, and Temperley) for counting the number of perfect matchings in planar graphs.
      CS 214, PlusOne.
      The Wikipedia page, Ashley Montanaro's slides, Aaron Gorenstein's notes.
    8. Intro to online algorithms (pick some cool examples).
      CS 214: Fibonado
      Survey by Susanne Albers, Serge Plotkin's lecture notes.
    9. Suffix Arrays and Trees.
      Group Karastuba