Materiale On-line





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
    .



Last update: September 10, 2021 Go to index