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. |
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. |
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. |
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. |
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.
|
Tuesday, December 6, 2016 |
Week 13 |
17 |
Presentations:
|
Thursday, December 8, 2016 |
Week 13 |
18 |
Homework 5,
handed out Wednesday, 2016-12-07. |
Tuesday, December 13, 2016 |
Week 14 |
19 |
Presentation: |
Tuesday, December 20, 2016 |
Week 15 |
20 |
Presentations:
|
Thursday, December 22, 2016 |
Week 15 |
21 |
Presentation:
|
Tuesday, December 27, 2016 |
Week 16 |
22 |
Presentations:
|