Randomized Algorithms
6.856J · Electrical Engineering and Computer Science, Mathematics · Graduate · Fall 2002
Prof. David R. Karger
This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Topics covered include: randomized computation; data structures (hash tables, skip lists); graph algorithms (minimum spanning trees, shortest paths, minimum cuts); geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension); approximate counting; parallel algorithms; online algorithm…
The syllabus, on MIT OpenCourseWare
The full course — syllabus, assigned readings, problem sets, exams, and lecture notes — lives on OCW. These open the real thing:
Syllabus ↗
Course overview, grading, schedule
Readings ↗
The assigned reading list, session by session
Assignments ↗
Problem sets and projects
Full course on OCW ↗
Everything, including lecture materials
Attribution
Prof. David R. Karger. 6.856J Randomized Algorithms. Fall 2002. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: CC BY-NC-SA 4.0.
Course materials are © their authors and licensed CC BY-NC-SA 4.0. CurrMana links to the source and does not re-host them.