27 March - 2 April

27/3: Πιθανοτικοί Αλγόριθμοι

• Πιθανοτικοί αλγόριθμοι: balls and bins, coupons collector, Chernoff-Hoeffding bounds, set balancing, πιθανοτική μέθοδος, πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT και 3-SAT (δείτε ακόμη και αυτές τις διαφάνειες για το 2-SAT και το 3-SAT), secretary problem, prophet inequalities (δείτε ακόμη εδώ για secretary problems και prophet inequalities). 

• Προτεινόμενη μελέτη: 
  
• R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (Ενότητες 3.1, 3.2, 3.6, 4.1, 4.2, 5.1, 5.2, 5.5, 6.1, 6.2, 7.1, 7.2). 
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (Ενότητες 2.1, 2.2, 2.3, 2.4, 3.1, 3.2, 3.3, 4.1, 4.2, 4.4, 5.1, 5.2, 5.3, 6.1, 6.2, 6.4.1, 7.1).