SUNY Geneseo Department of Computer Science

Analysis of Hashing with Chains

Return to List of Lectures

Questions?

Analysis of Hashing with Chains

Expected time for successful and unsuccessful searches

• Notice that the analysis of expected performance of unsuccessful searches averages across two dimensions: different distributions of chains to buckets (different colors below) and then different keys being searched for.

• The expectation is over distributions of chains, reflected in the indicator random variable for one key hashing to the same chain as another; the outer sum is the classical average of search times over all keys

Hand out probability problem set

Backtracking

Hand out backtracking homework

Example: the n queens problem

Next

Develop a backtracking algorithm for the n queens problem

Randomized algorithms