Skip navigation
Please use this identifier to cite or link to this item:
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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2023

Files in This Item:
File Description SizeFormat 
SHAPIRO-NATHAN-THESIS.pdf275.5 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.