| Time: every Wednesday; Thursdays in weeks 3-8 and 10,12,14,16; always 10:00 - 11:40. Location:下院109 |
| 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. |
|
Date |
Week |
# |
Content |
|
Wedesday, September 28, 2016 |
Week 3 |
|
Introdcution, administrative stuff. Euclid's algorithm. Running time, exact running time. Fibonacci number, linear recurrences; recursive and dynamic programming algorithm or Fibonacci numbers. |
|
Friday, September 30, 2016 |
Week 3 |
|
Computing Fibonacci numbers (maybe modulo k) via fast matrix multiplication. Homework 1 handed out on September 30; it is due October 9 by email to me or the teaching assistant |
|
Wednesday, October 5, 2016 |
Week 4 |
|
No class. Happy National Holiday! |
|
Friday, October 7, 2016 |
Week 4 |
|
No class. Happy National Holiday! |
|
Sunday, October 9, 2016 |
Week 4 |
|
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.
|
|
Wednesday, October 12, 2016 |
Week 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.
|
|
Friday, October 14, 2016 |
Week 5 |
|
Spanning trees in graphs. Kruskal's algorithm for finding
the minimum spanning tree. Good edge sets, cut lemma.
Keeping track of connected components: Union-Find
data structures: naive list
approach; "rename the smaller one" improvement.
|
|
Wednesday, October 19, 2016 |
Week 6 |
|
Shortest path algorithms: breadth-first search and
Dijkstra's algorithm. Longest paths in graphs.
Longest paths in acyclic graphs. The randomized color coding
technique.
|
|
Friday, October 21, 2016 |
Week 6 |
|
Flow networks. Network flows, cuts, residual networks.
|
|
Wednesday, October 26, 2016 |
Week 7 |
|
Maxflow-Mincut theorem. Ford-Fulkerson method and
Edmonds-Karp algorithm.
|
|
Friday, October 28, 2016 |
Week 7 |
|
Improving Edmonds-Karp:
Dinic algorithm finding paths in "O(n)" steps
in a layered digraph. Dinic algorithm on unit capacity
networks. |
|
Wednesday, November 2, 2016 |
Week 8 |
|
Matchings in bipartite graphs. Finding a maximum matching
using maximum flow algorithms (e.g. Dinic' algorithm).
Hall's Theorem.
|
Friday, November 4, 2016 |
Week 8 |
|
König's Theorem (maximum matching equals
minimum vertex cover in bipartite graphs) and
Dilworth's theorem on chains and antichains in
partial orders.
|
|
Wednesday,
November 9, 2016 |
Week 9 |
|
Introduction to linear programming. Feasible solutions,
standard form, dualizations, weak LP duality.
|
|
Wednesday, November 16, 2016 |
Week 10 |
|
How to dualize linear programs with equality constraints
and unbounded variables.
|
|
Friday, November 18, 2016 |
Week 10 |
|
Integrality of the Matching LP and the Vertex Cover LP
for bipartite graphs.
|
|
Wednesday, November 23, 2016 |
Week 11 |
|
Existence of optimal solutions for every bounded feasible
linear program.
|
|
Wednesday, November 30, 2016 |
Week 12 |
|
Farkas Lemma (geometric version) and Strong LP Duality.
|
|
Friday, December 2, 2016 |
Week 12 |
|
Different versions of Farkas Lemma. Proof of Farkas Lemma
by Fourier-Motzkin elimination.
|
|
Wednesday, December 7, 2016 |
Week 13 |
|
Reviewing Linear Programming. Introduction to streaming algorithms.
Approximating the number of different elements. Homework 5 handed out.
|
|
Wednesday, December 14, 2016 |
Week 14 |
|
Introduction to probability theory. Expectation and variance. Two-wise independence.
Approximating the number of different elements in a data stream up to a factor of 6.
|
|
Friday, December 16, 2016 |
Week 14 |
|
Approximating the number of distinct elements in a data stream with arbitrary precision.
|
|
Wednesday, December 21, 2016 |
Week 15 |
|
Presentations:
|
|
Wednesday, December 28, 2016 |
Week 16 |
|
Presentations:
|
|
Friday, December 30, 2016 |
Week 16 |
|
Presentations:
|