Bart Massey

Basic Idea

Use randomization as a technique for accelerating algorithms * As opposed to expected-case analysis * Usually doesn't improve worst-case performance * Can make expected-case good and worst-case vanishingly unlikely

Generating Random Numbers

  • Definitions of random:

    • Unpredictable
    • Physically random
    • Uncorrelated
  • Construction of PRNGs

    • Linear
    • Crypto-secure

Using Random Numbers in Algorithms

  • Finding approximate median

    • Using this to find actual median
  • Local search

  • Randomizing inputs

The Perfect Shuffle

  • Construct from "obvious" random selection algorithm
    • Replace array shifts with fill-ins
    • Replace output array with blanks in input array
    • Proof of correctness is thus easy

Random Weighted Selection

  • Application: Bayesian Particle Filtering

  • Technique: Start with "obvious" scan through weights

    • Accelerate by DP + binary search
    • Accelerate by merging
    • Fixing the merge order
    • Improving constant factors
Last modified: Thursday, 29 May 2014, 11:37 AM