COMP670R: Topics in Theory: Hashing
(Fall 2009)

Course Information
Schedule & Notes

Week

Date

Topic

Presenter

References

Remarks

1

 

No class

     

2

09-09

The Basics: models, the dictionary problem, chaining, linear probing, universal hashing

Ke Yi

Randomized Algorithms, Section 8.4

 

3

17-09

Perfect hashing, Bloom filters

Ke Yi

Section 8.5, wiki link

 

4

24-09

Linear-time closest pair

Mordecai Golin

slides  

5

01-10

Public holiday

     

6

08-10

Bin-ball analysis, Cuckoo hashing

Mordecai Golin

Cuckoo hashing for undergrads

 

7

15-10

Dynamic perfect hashing: upper and lower bounds Jiongxin Jin

paper

 

8

22-10

The power of two random choices

Zengfeng Huang

survey

 

9

29-10

Why simple hash functions work: exploiting the entropy in a data stream

Hao Hu

paper

 

10

05-11

Locality sensitive hashing

Jian Xia

see below

 

11

12-11

Analysis of linear probing

Zhewei Wei

   

12

19-11

Linear Probing with Constant Independence

Zhewei Wei

paper

 

13

26-11

Hashing in streaming

Lu Wang

 

 

14

04-12

On the cell probe complexity of dynamic membership

Qin Zhang

 

Theory seminar

List of papers to choose from (you can also pick anything that you are interested in!)

Dictionaries

External hashing

Locality sensitive hashing

Hashing in streaming

Cryptography

Miscellaneous