Analysis of Algorithms : An Active Learning Approach

9.2 PROBABILISTIC ALGORITHMS 243 hits = 0 for i=1 to dartCount do x = uniform(0, 1) y = uniform(0, 1) if y ≤ f(x) then hits = hi ...

244 OTHER ALGORITHMIC TECHNIQUES be called a number of times, averaging the answers it returns. For our birthday example (N = 36 ...

9.2 PROBABILISTIC ALGORITHMS 245 function would be looking for a series of repeated true answers to increase the chance that tru ...

246 OTHER ALGORITHMIC TECHNIQUES This function randomly picks an element and checks to see if it appears in a majority of locati ...

9.2 PROBABILISTIC ALGORITHMS 247 This equation is saying that if we succeed, the overall time is the time it takes to get a succ ...

248 OTHER ALGORITHMIC TECHNIQUES row = 1 repeat // at this point we have placed queens in rows 1...row - 1 spotsPossible = 0 for ...

9.2 PROBABILISTIC ALGORITHMS 249 Let’s look at what this algorithm is doing. The repeat loop will take us through each of the ei ...

250 OTHER ALGORITHMIC TECHNIQUES element each time, but the chances of that happening are very small. The down side of this is t ...

9.2 PROBABILISTIC ALGORITHMS 251 9.2.6 On a recent outing in the woods, you found a cave that had a map, a large computer, and ...

252 OTHER ALGORITHMIC TECHNIQUES returned. How many times do you have to call this function before you get the correct answer? ( ...

9.3 DYNAMIC PROGRAMMING 253 if (N = 1) or (N = 2) then return 1 else return Fibonacci( N-1 ) + Fibonacci( N-2 ) end if If we use ...

254 OTHER ALGORITHMIC TECHNIQUES This example is not very complicated, and you should see that it would even be possible to acco ...

9.3 DYNAMIC PROGRAMMING 255 BiCoeff[N, k]. The following algorithm gives the dynamic programming solution to this problem: for i ...

256 OTHER ALGORITHMIC TECHNIQUES a matrix called trace that is used by the next algorithm to actually determine the order of the ...

9.3 DYNAMIC PROGRAMMING 257 end if end for k costi,loc = tempCost tracei,loc = tempTrace end for j end for i Once the trace arra ...

258 OTHER ALGORITHMIC TECHNIQUES 9.4 Programming Exercises Write a program for the traveling salesperson approximation algorith ...

Appendix A Random Number Table This table has random numbers between 0 and 1. If you need a random num- ber between 0 and N, jus ...

260 APPENDIX A 60 0.32764 100 0.47643 140 0.90770 61 0.62633 101 0.93607 141 0.27310 62 0.96292 102 0.48024 142 0.98280 63 0.344 ...

Appendix B Pseudorandom Number Generation Random numbers are useful in a number of computer applications. Any algo- rithmic proc ...

262 APPENDIX B Because of the mod operation, the seed value will always be between zero and m
1. The division of the seed by m ...