Time: every Monday and Thursday,
14:00 - 15:40, week 1 to 12. Location:上院409 |
Teacher:
Dominik Scheder. Teaching Assistant:汤舒扬 (Tang Shuyang, htftsy@gmail.com). |
Textbook: Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani |
Material: This is mostly a blackboard class, but here is some material. |
Grading: 50% final exam, 50% homework. The stundents will form groups of size 4-5. Homework will be handed in by every group. |
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,
November 20, 2018 |
Week 11 |
21 |
Homework 8 handed out; here are the latex sources |
Thursday,
November 14, 2018 |
Week 10 |
20 |
|
Monday,
November 11, 2018 |
Week 10 |
19 |
|
Thursday,
November 7, 2019 |
Week 9 |
18 |
Homework 7 handed out; here are the latex sources |
Saturday,
November 2, 2019 |
Week 9 |
17 |
|
Thursday,
October 31, 2018 |
Week 8 |
16 |
Fourier-Motzkin Elimination and Farkas Lemma more formally. Proof of the Strong LP Duality Theorem.
|
Monday,
October 28, 2018 |
Week 8 |
15 |
How to dualize programs with some equality constraints and
unbounded variables. |
Thursday,
October 24, 2019 |
Week 7 |
14 |
The Vertex Cover LP: proof that there is an optimal solution that is also a 0/1-solution.
Existence of optimal solutions for every feasible and bounded linear program. |
Monday,
October 28, 2019 |
Week 7 |
13 |
Linear programs, formally (variables, constraints, feasible solutions, value).
The dual of a linear program. The Weak Duality Theorem. |
Thursday,
October 24, 2019 |
Week 6 |
12 |
Homework 4.4: an O(m log*(m)) algorithm for
the Maximum Capacity Path problem in directed graphs. An O(m) algorithm
for undirected graphs. |
Monday,
October 21, 2019 |
Week 6 |
11 |
Application of Hall's Theorem:
|
Thursday,
October 17, 2019 |
Week 5 |
10 |
Example where Ford-Fulkerson with maximum capacity path augmentation fails
to terminate (pdf slides). |
Monday,
October 14, 2019 |
Week 5 |
9 |
Running time of Dinic' algorithm on Unit Capacity Networks. Here are the pdf slides |
Thursday,
October 10, 2019 |
Week 5 |
8 |
The Ford-Fulkerson method (FF). An example where FF
takes long time to terminate, if it is unlucky in finding
paths. |
Monday,
September 30, 2019 |
Week 4 |
7 |
Network flows. Two definitions of network flow. Characterization of maximum flows: no s-t-path in the residual network. The Max-Flow Min-Cut Theorem. |
Thursday,
September 27, 2018 |
Week 3 |
6 |
Union-by-rank with path compression; running time analysis
with inverse Ackermann function. |
Monday,
September 23, 2019 |
Week 3 |
5 |
Minimum Spanning Trees: Kruskal's algorithm. |
Thursday,
September 19, 2019 |
Week 2 |
4 |
Quicksort: analyzing the expected running time via
indicator variables Ai,j which are 1
if i is an ancestor of j. |
Monday,
September 16, 2019 |
Week 2 |
3 |
Mergesort, worst case analysis. Determining the exact
number of comparisons in the worst case. |
Thursday, September 12, 2019 |
Week 1 |
2 |
Computing Fibonacci numbers
via fast matrix multiplication. Computing them modulo k.
How does python multiply Big Integers?
How to solve recurrences without remembering the
Master Theorem.
Homework 1 handed out.
Here are the latex sources files
of Homework 1.
|
Monday,
September 9, 2019 |
Week 1 |
1 |
Introdcution, administrative stuff. |