Please use this identifier to cite or link to this item:
http://arks.princeton.edu/ark:/88435/dsp015t34sn83f| Title: | Random Graphs and Hashing |
| Authors: | Shapiro, Nathan |
| Advisors: | Tarjan, Robert |
| Department: | Mathematics |
| Certificate Program: | Applications of Computing Program |
| Class Year: | 2023 |
| Abstract: | In this paper, we examine data structures for monotone minimal perfect hash functions and show how properties of graphs can dictate how many bits of space these data structures must take up. We then examine how hashing can make the disjoint set union problem more space efficient and show that some forms of random linking have optimal performance. |
| URI: | http://arks.princeton.edu/ark:/88435/dsp015t34sn83f |
| Type of Material: | Princeton University Senior Theses |
| Language: | en |
| Appears in Collections: | Mathematics, 1934-2023 |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| SHAPIRO-NATHAN-THESIS.pdf | 275.5 kB | Adobe PDF | Request a copy |
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.