Space limitations prevent us from including large amounts of video
on this CD-ROM, although we have managed to include the full 30+ hours
of audio algorithm lectures.
Still, we are proud to present the following three short MPEG-2 videos,
which illustrate
particularly dramatic topics in the design and analysis
of algorithms.
Your browser must support MPEG-2 or contain the appropriate
plugin to really watch
the show, but a lower-tech video
is also available.
Binary Search, in action --
Binary search is a fast algorithm for searching in a sorted array of keys.
The number of steps the algorithm takes equals the number of times we
can halve the number of keys until only one is left.
Thus twenty comparisons suffice to find any name in the million-name Manhattan
phone book!
The power of binary search and logarithms is one of the most
fundamental idea in the analysis of algorithms.
Hash Functions, good and bad --
The performance of hashing depends strongly on the ability of
your hash function to deliver a uniform distribution for your set
of keys.
This requires some care, because some functions are not as uniform
as they seem...
The Birthday Paradox, in action --
Regardless of how good your hash function is, collisions are going
to occur.
This is demonstrated by the Birthday paradox, the fact that any group of
23 people is more likely than not to contain a pair who share the same
birthday.