Section outline

  • Διάλεξη 29/3

    Κατακερματισμός (hashing) II

    (διαφάνειες U. Zwick από μάθημα Advanced Algorithms, Tel Aviv University): 

    • Επιθυμητές ιδιότητες. Καθολικότητα και k-ανεξαρτησία. Carter-Wegman Universal hash family. 
    • Ανάλυση χρόνου βασικών πράξεων στην κλειστή και ανοιχτή διεθυνσιοδότηση.
    • Μέθοδοι διερεύνησης στην ανοιχτή διευθυνσιοδότηση.
    • Τέλειος κατακερματισμός (perfect hashing). Κατακερματισμός κούκου (Cuckoo hashing). 

    Παρουσιάστηκαν οι διαφάνειες 14-20 (επανάληψη) και 21-54.

    Προτεινόμενη μελέτη: σημειώσεις (και αναφορές που περιέχονται).