Courses:

Randomized Algorithms >> Content Detail



Calendar / Schedule



Calendar

LEC #TOPICS
1Introduction to Randomized Algorithms
2Min-Cut, Complexity Theory, Game Tree Evaluation
3Adelman's Theorem, Game Theory, Lower Bounds
4Coupon Collecting, Stable Marriage, Markov Inequality
5Chebyshev, Two Point Sampling, Chernoff
6Median Finding, Routing
7Probabilistic Method, Expanders, Wiring, MAX SAT
8Method of Conditional Probabilities and Expectations, Fingerprinting
9Hashing, Perfect Hash Families, Freivald's Technique
10Fingerprints by Polynomials, Perfect Matching, Hashing
11Shortest Paths
12Parallel Algorithms
13Maximal Independent Sets
14Minimum Spanning Trees
15Polling, Minimum Cut, Transitive Closure
16Estimating Min-Cut Size
17Linear Programming
18DNF Counting
19Markov Chains
20UTS, Eigenvalue Analysis, Expanders
21Expander based Pseudo-Random Generator
22Sampling with Markov Chains, Coupling
23Computational Geometry
24Randomized Incremental Construction
25Trapezoidal Decomposition, Treaps
26Online Algorithms

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.