Lecture

Hash Tables: Birthday Paradox

In course

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Description

This lecture covers the concept of hash tables, starting with the Birthday Paradox to determine the minimum number of students needed for a 50% chance of sharing a birthday. It then delves into hash functions, collisions, and the implementation of hash tables using direct-address and chained methods.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructors (3)

Mikhail Kapralov

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Official source

Related lectures (31)

Probabilistic Analysis: Hiring & Birthday Paradox

Explores probabilistic analysis in algorithms, covering the hiring problem and the birthday paradox, along with hash tables and functions.

Pairwise Independence: Hashing and Load Balancing

Explores pairwise independence in hashing to avoid collisions and achieve load balancing.

Hash Functions and Tables

Introduces hashing tables, including the Birthday Lemma, Direct-Address Tables, collisions, and Chained-Hash-Search.

Hashing and Sorting Techniques in Database Systems

Provides an overview of hashing and sorting techniques in database management systems, focusing on their implementation and performance optimization.

Hash Tables Analysis

Covers the analysis of hash tables, including search operations and expected collisions.