Randomized AlgorithmsA short list of categoriesRandomized algorithmsPseudorandom numbersGenerating random numbersGetting (pseudo)random numbers in JavaGaussian distributionsShuffling an arrayChecking randomnessRandomly choosing N thingsStupidSortAnalyzing StupidSortZero-sum two-person gamesApproximating an optimal strategyExample of random playThe 0-1 knapsack problemImproving the knapsack solutionQueueing problemsConclusionsThe EndJan 14, 2019Randomized Algorithms2 Also known as Monte Carlo algorithms or stochastic methodsA short list of categoriesAlgorithm types we will consider include:Simple recursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithmsBranch and bound algorithmsBrute force algorithmsRandomized algorithms3Randomized algorithmsA randomized algorithm is just one that depends on random numbers for its operationThese are randomized algorithms:Using random numbers to help find a solution to a problemUsing random numbers to improve a solution to a problemThese are related topics:Getting or generating “random” numbersGenerating random data for testing (or other) purposes4Pseudorandom numbersThe computer is not capable of generating truly random numbersThe computer can only generate pseudorandom numbers--numbers that are generated by a formulaPseudorandom numbers look random, but are perfectly predictable if you know the formulaPseudorandom numbers are good enough for most purposes, but not all--for example, not for serious security applicationsDevices for generating truly random numbers do existThey are based on radioactive decay, or on lava lamps“Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.” —John von Neumann5Generating random numbersPerhaps the best way of generating “random” numbers is by the linear congruential method:r = (a * r + b) % m;where a and b are large prime numbers, and m is 232 or 264The initial value of r is called the seedIf you start over with the same seed, you get the same sequence of “random” numbersOne advantage of the linear congruential method is that it will (eventually) cycle through all possible numbersAlmost any “improvement” on this method turns out to be worse“Home-grown” methods typically have much shorter cyclesThere are complex mathematical tests for “randomness” which you should know if you want to “roll your own”6Getting (pseudo)random numbers in Javaimport java.util.Random;new Random(long seed) // constructornew Random() // constructor, uses System.timeInMillis() as seedvoid setSeed(long seed)nextBoolean()nextFloat(), nextDouble() // 0.0 < return value < 1.0nextInt(), nextLong() // all 232 or 264 possibilitiesnextInt(int n) // 0 < return value < nnextGaussian() Returns a double, normally distributed with a mean of 0.0 and a standard deviation of 1.07Gaussian distributionsThe Gaussian distribution is a normal curve with mean (average) of 0.0 and standard deviation of 1.0It looks like this:Most real “natural” data—shoe sizes, quiz scores, amount of rainfall, length of life, etc.—fit a normal curveTo generate realistic data, the Gaussian may be what you want:r = desiredStandardDeviation * random.nextGaussian() + desiredMean;“Unnatural data,” such as income or taxes, may or may not be well described by a normal curve 33% 33%17% 17% -1.0 0.0 1.08Shuffling an arrayGood: static void shuffle(int[] array) { for (int i = array.length; i > 0; i--) { int j = random.nextInt(i); swap(array, i - 1, j); } } // all permutations are equally likelyBad: static void shuffle(int[] array) { for (int i = 0; i < array.length; i++) { int j = random.nextInt(array.length); swap(array, i, j); } } // all permutations are not equally likely9Checking randomnessWith a completely random shuffle, the probability that an element will end up in a given location is equal to the probability that it will end up in any other locationI claim that the second algorithm on the preceding slide is not completely randomI don’t know how to prove this, but I can demonstrate itDeclare an array counts of 20 locations, initially all zeroDo the following 10000 times:Fill an array of size 20 with the numbers 1, 2, 3, ..., 20Shuffle the arrayFind the location loc at which the 5 (or some other number) ends upAdd 1 to count s[loc]Print the counts array10Randomly choosing N thingsSome students had an assignment in which they had to choose exactly N distinct random locations in an arrayTheir algorithm was something like this:for i = 1 to n { choose a random location x if x was previously chosen, start over }Can you do better?11StupidSortHere’s a related technique:void stupidSort(int[] array) { while (!sorted(array)) { shuffle(array); }}This is included as an example of one of the worst algorithms knownYou should, however, be able to analyze (compute the running time of) this algorithm12Analyzing StupidSortvoid stupidSort(int[] array) { while (!sorted(array)) { shuffle(array); }}Let’s assume good implementations of the called methodsYou can check if an array is sorted in O(n) time (n = size of the array)The shuffle method given earlier takes O(n) time (check this)There are n! possible arrangements of the arrayIf we further assume all elements are unique, then there is only one correct arrangement--so the odds for each shuffle are 1 in n!If the odds of something are 1 in x, then on average we have to wait x trials for it to occur (I won’t prove this here)Hence, running time is O((test + shuffle)*n!) = O(2n * n!) = O((n + 1)!)13Zero-sum two-person gamesA zero-sum two person game is represented by an array such as the following:-28037-16-8235-612-9-8-1437RedBlueThe game is played as follows:Red chooses a row and, at the same time, Blue chooses a columnThe number where the row and column intersect is the amount of money that Blue pays to Red (negative means Red pays Blue)Repeat as often as desiredThe best strategy is to play unpredictably--that is, randomlyBut this does not mean “equal probabilities”--for example,
View Full Document
Unlocking...