Skip to content

Latest commit

 

History

History
11 lines (6 loc) · 1.12 KB

README.md

File metadata and controls

11 lines (6 loc) · 1.12 KB

Randomized Algorithms - INF420

Exercises

Common Randomized Algorithms - Implementation of the coupon collector problem and the randomized quicksort and median algorithms.

Balls and Bins & Hamiltonian cycles - Finding the max load in an experiment with n bins and balls. Searching for Hamiltonian cycles in random graphs.

Max-Cut Algorithms & Concentration Inequalities - Implementation of a randomized and a deterministic algorithm for finding large cuts in random graphs. Using a simple balls and bins example to oberve the results of McDiarmid's inequality.

Dimensionallity Reduction & Satisfiability Algorithms - Studying the Johnson-Lindenstrauss Lemma to redduce the dimension of some matrix without losing any information. For the second part a randomized 2-SAT algorithm is implemented.