algorithm design techniques / - this is actually very conservative estimatewhich holds for only few choices of even soone is more likely to see hardware error than an incorrect claim of primality randomized algorithms for primality testing are important because they have long been significantly faster than the best nonrandomized algorithmsand although the randomized algorithm can occasionally produce false positivethe chances of this happening can be made small enough to be negligible for many yearsit was suspected that it was possible to test definitively the primality of -digit number in time polynomial in dbut no such algorithm was known recentlyhoweverdeterministic polynomial time algorithms for primality testing have been discovered while these algorithms are tremendously exciting theoretical resultsthey are not yet competitive with the randomized algorithms the end of references provide more information backtracking algorithms the last algorithm design technique we will examine is backtracking in many casesa backtracking algorithm amounts to clever implementation of exhaustive searchwith generally unfavorable performance this is not always the casehoweverand even soin some casesthe savings over brute-force exhaustive search can be significant performance isof courserelativean ( algorithm for sorting is pretty badbut an ( algorithm for the traveling salesman (or any np-completeproblem would be landmark result practical example of backtracking algorithm is the problem of arranging furniture in new house there are many possibilities to trybut typically only few are actually considered starting with no arrangementeach piece of furniture is placed in some part of the room if all the furniture is placed and the owner is happythen the algorithm terminates if we reach point where all subsequent placement of furniture is undesirablewe have to undo the last step and try an alternative of coursethis might force another undoand so forth if we find that we undo all possible first stepsthen there is no placement of furniture that is satisfactory otherwisewe eventually terminate with satisfactory arrangement notice that although this algorithm is essentially brute forceit does not try all possibilities directly for instancearrangements that consider placing the sofa in the kitchen are never tried many other bad arrangements are discarded earlybecause an undesirable subset of the arrangement is detected the elimination of large group of possibilities in one step is known as pruning we will see two examples of backtracking algorithms the first is problem in computational geometry our second example shows how computers select moves in gamessuch as chess and checkers the turnpike reconstruction problem suppose we are given pointsp pn located on the -axis xi is the coordinate of pi let us further assume that and the points are given from left to right these points determine ( )/ (not necessarily uniquedistances dn between