26 September - 2 October

Eισαγωγή, αλγόριθμος Morris, αλγόριθμος εύρεσης πλήθους διακριτών στοιχείων, ανα k ανεξάρτητες κατανομές.

Είδαμε τα 3 και 5 (εκτός από 5.2) από 

http://people.seas.harvard.edu/~minilek/cs229r/fall15/lec/lec1.pdf,

καθώς και 1 ως 6 (εκτός από το 5 και το δεύτερο παράδειγμα στο 6) από 

http://people.seas.harvard.edu/~minilek/cs229r/fall15/lec/lec2.pdf

Η εργασία του Morris λέγεται "Counting large numbers of events in small registers" (1977).

Για την ιστορία του προβλήματος των διακριτών στοιχείων μπορείτε να διαβάσατε και την εισαγωγή από το https://people.eecs.berkeley.edu/~minilek/publications/papers/f0.pdf (το https://arxiv.org/pdf/1804.01642.pdf περιέχει έναν καλύτερο αλγόριθμο, αλλά σημαντικά λιγότερο λεπτομερή εισαγωγή).