|
Date
|
Topic
|
Comments
|
|
1390/06/27
|
Introduction - Finding Triangles in Graphs |
Ref: Alon et al.'s paper (1994) |
|
1390/06/29
|
Amortized Analysis - Binomial Heaps |
Ref: CLRS [Ch17], CLRS/2e [Ch19] |
|
1390/07/03
|
Fibonacci Heaps |
Ref: CLRS [Ch19] |
|
1390/07/05
|
Graph Connectivity: Disjoint Sets |
Ref: CLRS [Ch21] |
|
1390/07/10
|
Randomized Algorithms - Quicksort and Min-Cut |
Ref: CLRS [Ch7], MR [Ch1] |
|
1390/07/12
|
From Monte Carlo to Las Vegas: String Matching |
Ref: CLRS [Ch32] |
|
1390/07/19
|
Random Ordering: AND/OR Tree Evaluation |
Ref: MR [Ch2] |
|
1390/07/24
|
Random Sampling: Median |
Ref: MR [Ch3], MU [Ch3] |
|
1390/07/26
|
Backward Analysis: Smallest Enclosing Circle |
Ref: CLRS [Ch5.1], BCKO [Ch4.7] |
|
1390/08/01
|
Random Walk: Satisfiability |
Ref: MR [Ch6.1], Schoening's paper (1999) |
|
1390/08/08
|
Polynomial-Time Reduction |
Ref: CLRS [Ch34.1], KT [Ch8.1] |
|
1390/08/10
|
NP-Completeness Proofs |
Ref: CLRS [Ch34.2-4], KT [Ch8.2-3] |
|
1390/08/15
|
NP-Complete Problems: Circuit Satisfiability, 3-SAT, Hamiltonian Cycle |
Ref: CLRS [Ch34.5], KT [Ch8.4-5] |
|
1390/08/17
|
NP-Complete Problems: TSP, Graph Coloring, Subset Sum, Scheduling |
Ref: KT [Ch8.6-8] |
|
1390/08/29
|
Approximation Algorithms: Vertex Cover, Metric TSP |
Ref: CLRS [Ch35.1-2] |
|
1390/09/01
|
Disjoint Unit Squares (PTAS), MAX 3-SAT |
Ref: CLRS [Ch35.4], Hochbaum and Maass' paper ('85) |
|
1390/09/06
|
Online/Offline Bin Packing |
Ref: V [Ch9] |
|
1390/09/20
|
Online Navigation: The Lost Cow Problem |
Ref: Kao et al.'s paper (1992) |
|
1390/09/22
|
Competitive Analysis: Paging |
Ref: BE, MR [Ch13] |
|
1390/09/27
|
Flow Networks: Max Flow/Min Cut |
Ref: CLRS [Ch26] |
