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.
- Data Structures
- Randomized binary search trees.
CS 214: Group Philosophy
- 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.
- Fibonacci heaps.
CS 214: Group -1s.
CS 217: Group Paradox.
David Kempe's
lecture
notes on Fibonacci heaps.
- Flows, cuts, matchings
- Push-relabel algorithms for maximum flow.
CS 214: Group HK Journalists.
Avrim Blum's
lecture
notes on push-relabel algorithms.
- Maximum revenue network flow.
CS 214: S05.
David Karger's
lecture
notes.
- Edmonds' blossom algorithm for
maximum matching in general graphs.
CS 214: Triangle.
Uri Zwick's lecture
notes.
- Karger's probabilistic minimum cut
algorithm for undirected graphs.
CS 214: Group Northern Light.
Sanjeev Arora's lecture notes.
- Stoer-Wagner algorithm for minimum cut in undirected graphs.
CS 214: Group BigNews.
The original paper.
Linear Programming
- Zero-sum games and von Neumann's Minmax Theorem.
CS 214: Group Second++.
CS 217: AlphaGorithm
Here are
some references:
- 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.
- Algorithms for Markov decision processes.
CS 214: Group BugMaker
Thomas Dueholm Hansen's
lecture
notes, course by Uri Zwick.
Miscellaneous
- 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.
- 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.
- A 3n and a 2n algorithm
for d-colorability.
Paper
by Mikko Koivisto and
Paper by Andreas Björklund and Thore Husfeldt.
CS 214: Group Dominantors.
- 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.
- 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.
- 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.
- Intro to online algorithms (pick some cool examples).
CS 214: Fibonado
Survey
by Susanne Albers,
Serge
Plotkin's lecture notes.
- Suffix Arrays and Trees.
Group Karastuba