Note de curs, clasele 11-12, 12 octombrie 2012

Teme din urmă

• discuția implementărilor pentru ce am predat ultima dată:
  • structuri de mulțimi disjuncte
  • parcurgeri Euler
  • LCA offline / online
  • RMQ
• discuție despre importanța implementării, ca să nu fie prima implementare chiar în timpul concursului

Tabele hash

• definiție
• proprietate fundamentală: dorim căutare rapidă
• exemplu: se dau V(n), S, să se spună dacă există a, b în V pentru care a + b = S
  • idem pentru suma a trei numere
• reprezentare cu vector direct (pentru spațiu mic de chei)
  • problemă: Se dă un arbore cu rădăcină reprezentat printr-un vector de tați. Să se găsească înălțimea arborelui
• când spațiul de chei U ≫ n, convertirea cheii k în h(k)
• coliziuni -> înlănțuire
• inserare: O(1) dacă nu trebuie căutat în prealabil
• căutare cu succes: O($\alpha$).
  • listele mai lungi (acolo unde există mai multe coliziuni) vor fi căutate mai des, dar tot O($\alpha$)
• funcții hash, proprietăți: să fie independente de pattern-uri în date, să folosească toți biții
  • rele: % 9 (permutarea cifrelor), % 2^p (numai ultimii doi biți)
  • împărțire: un număr prim nu prea apropiat de puteri ale lui 2.
  • înmulțire: $\lfloor m(kA\mod 1)\rfloor$, A recomandat golden ratio
• compromisuri pentru mărimea tabelei: mică -> coliziuni, mare -> risipă de memorie
• birthday paradox: când mă aștept să am prima coliziune?
• open address hashing

Teme

• design la un LRU cache care să facă operațiile de inserare / căutare / evacuare în O(1)
• cele mai mici k elemente dintr-un vector de n, cu două variante (se cer sortate sau nesortate).
  • enumerați câte metode vă dau prin cap și analizați complexitățile (sortare, select, min-heap, max-heap)
• să se inițializeze un vector cu o valoare implicită x în O(1) (evident, este o inițializare lazy).