Here is a collection of useful material suppplementing the textbooks.
- Polinomiality of 2-CNF-SAT
(slides)
PDF Download
- The Design of Approximation ALgorithms by Williamson and Shmoys.
PDF . Contains i Christofides' Algorithm for the 3/2-approximation of TRIANGLE-TSP.
-
Pomerance's Theorem on the distribution of base-2 pseudoprimes
PDF Download
- Randomized Algorithms (1)
(contains a detailed average case argument for Quicksort and Karger's Min-Cut Algorithm).
PDF Download
- Randomized Algorithms (2)
(contains an excellent review of basic probability theory and useful practice material)
PDF Download
- Randomized Algorithms (3)
Derivation of Chernoff Bounds
PDF Download
- Template exams (only the solutions are in english) Years 2004/05 and 2005/06
PDF Download .
- Template exams (questions only, in italian)
PDF Download .
- Template exams (only the solutions are in english) 2012/13
and 2013/14
PDF Download .
|
