Program Gallery

View as a github repository

Lists and Sequences

• In-place uniform shuffle
• Dynamic time warping for sequence comparison
• Polynomial Multiplication Using the FFT

Geometry

• Earthmover distance

Hash Tables

• Caching (and memoization)

Data Analysis

• Principal Component Analysis (Dimensionality Reduction)

Randomized Algorithms

• Miller-Rabin Primality Test
• Simulating a Fair Coin with a Biased Coin
• Simulating a Biased Coin with a Fair Coin
• Blum-Blum-Shub pseudorandom generator
• Randomized Response for Surveys of Sensitive Information

Sorting

• Bayesian ranking for rated items

Streaming Algorithms

• Streaming median
• Reservoir Sampling
• Finding the majority element of a stream
• Hashing to estimate the size of a stream