Courses:

Randomized Algorithms >> Content Detail



Lecture Notes



Lecture Notes

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

 








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