Talks

Update: The 2nd talk is happening 6pm-8pm in Amfiteatrul Pompeiu (= amfiteatrul de la etajul 2).

I am giving two talks in Bucharest this coming week:

• a more practical one at Poly on Monday (December 7) at 6pm in room EC 101 (Fac. Automatică şi Calculatoare)
• a more theoretical one at UniBuc on Friday (December 11). Room and time to be announced here, but it will be earlier in the afternoon.

Abstracts below. Don't forget to vote on Sunday.

1. Funcţii de hash tabulare
   
   Implementarea tabelelor de hash folosind căutare liniară (linear probing) este mai eficientă decât alte implementări dacă funcţia de hash este suficient de alteatoare. Din păcate, linear probing se comportă foarte prost în conjuncţie cu funcţiile de hash bazate pe înmulţire (cele mai folosite în practică), şi ca atare, acest algoritm este deseori evitat.
   
   Voi descrie o funcţie de hash foarte simplă, care este la fel de rapidă ca înmulţirea pe procesoarele actuale, dar se bazează pe indexarea în tabele precalculate. O analiză matematică ne demonstrează că această funcţie garantează timp de rulare constant pentru tabelele de hash.
   
   
2. Rezultate negative pentru structuri de date
   
   Cum demonstrăm că anumite rezultate algoritmice sunt imposibil de obţinut? Spre exemplu, cum demonstrăm că nu există nicio structură de date cu spațiu liniar care poate suporta range queries în timp constant? În acest curs, voi descrie o demonstrație completă a acestui rezultat, trecând prin mai mulți pași simpli, dar interesanți.