# click the upper-left icon to select videos from the playlist
source: Tim Roughgarden Lectures 2014年9月29日
Beyond Worst-Case Analysis (CS264, Fall 2014)
Course website, with problem sets, lecture notes, and related resources: http://theory.stanford.edu/~tim/f14/f14.html
Course description:
This course has two intertwined goals. The first goal is to survey several important computational problems for which the traditional worst-case analysis of algorithms is ill-suited, because it fails to differentiate meaningfully between different solutions, recommends an empirically "wrong" solution over the "right" one, or gives excessively pessimistic performance predictions. The second goal is to study systematically alternatives to worst-case analysis that nevertheless enable rigorous and robust guarantees on algorithm performance.
List of topics: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models.
Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, scheduling, linear programming, hashing, and auction theory.
1 (Introduction) 55:55 Three motivating examples. Pros and cons of worst-case analysis. Instance optimality.
2 (Instance Optimality) 1:11:16
3 (Resource Augmentation) 1:18:48
4 (Parameterized Paging) 1:19:15
5 (Recoverable Value) 1:14:49
6 (Stable Clustering I) 1:19:05
7 (Single-Link++) 1:13:38
8 (Recovering Graph Cuts) 1:17:08
9 (Compressive Sensing) 57:22
10 (Planted Graph Models) 1:10:14
11 (LP Decoding) 1:13:05
12 (Intro to Smoothed Analysis) 1:16:53
13 (Smoothed Local Search) 1:16:24
14 (Smoothed Pareto Curves) 1:08:47
15 (Pseudopoly = Smoothed Poly) 1:22:34
16 (Hashing + Pseudorandom Data) 1:18:26
17 (Self-Improving Algorithms) 1:25:12
18 (Pricing Using Samples) 1:12:06
19 (Random Permutations) 1:17:26
20 (From Distributions to Instance-Optimality) 1:16:44
No comments:
Post a Comment