20 March - 26 March

20/3: Δυϊκότητα, Πιθανοτικοί Αλγόριθμοι

• Δυϊκότητα στον γραμμικό πρόγραμματισμό.
• Πιθανοτικοί αλγόριθμοι, ο αλγόριθμος του Karger για το πρόβλημα της Ελάχιστης Τομής. 
  Προτεινόμενη μελέτη: 
  
• R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (Κεφάλαιο 1 και ενότητα 10.2). 
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (Κεφάλαιο 1). 
• Δείτε ακόμη τον αλγόριθμο Miller-Rabin για τον έλεγχο πρώτων αριθμών.