algorithm design techniques automatically be improved by factor of or more this is discussed in exercise [ ]and [ the discussion of random-number generators is based on [ park and miller attribute the portable implementation to schrage [ the mersenne twister generator was proposed in [ ]the subtract with-carry generator was described in [ skip lists are discussed by pugh in [ an alternativenamely the treapis discussed in the randomized primality-testing algorithm is due to miller [ and rabin [ the theorem that at most ( - )/ values of fool the algorithm is from monier [ in an ( deterministic polynomial-time primality testing algorithm was discovered [ ]and subsequently an improved algorithm with running time ( was found [ howeverthese algorithms are slower than the randomized algorithm other randomized algorithms are discussed in [ more examples of randomization techniques can be found in [ ][ ]and [ more information on - pruning can be found in [ ][ ]and [ the top programs that play chesscheckersothelloand backgammon all achieved world class status in the the world' leading checkers programchinookhas improved to the point that in it provably could not lose game [ [ describes an othello program the paper appears in special issue on computer games (mostly chess)this issue is gold mine of ideas one of the papers describes the use of dynamic programming to solve chess endgames completely when only few pieces are left on the board related research resulted in the change in (later revoked in of the -move rule in certain cases exercise is solved in [ determining whether homometric point set with no duplicate distances exists for > is open christofides [ gives solution to exercise and also an algorithm that generates tour at most optimal exercise is discussed in [ exercise is solved in [ an (knalgorithm is given in [ exercise is discussed in [ ]but do not be misled by the title of the paper abramson"control strategies for two-player games,acm computing surveys ( ) - aggarwal and weincomputational geometrylecture notes for mit laboratory for computer science agrawaln kayaland saxena"primes is in ,annals of mathematics ( ) - alonz galiland margalit"on the exponent of the all-pairs shortest path problem,proceedings of the thirty-second annual symposium on the foundations of computer science ( ) - baloghj bekesiand galambos"new lower bounds for certain classes of binpacking algorithms,theoretical computer science - ( ) - belli wittenand cleary"modeling for text compression,acm computing surveys ( ) - bellmandynamic programmingprinceton university pressprincetonn bellman and dreyfusapplied dynamic programmingprinceton university pressprincetonn bentleyd hakenand saxe" general method for solving divide-and-conquer recurrences,sigact news ( ) -