2 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples 1,1 Introduction To say that a problem is solvable algorithmically means,informally,that a computer program can be written that will produce the correct answer for any input if we let it run long enough and allow it as much storage space as it needs.In the 1930s,before the advent of computers,mathematicians worked very actively to formalize and study the notion of an algorithm,which was then interpreted informally to mean a clearly specified set of simple instructions to be followed to solve a problem or compute a function.Various formal modeis of computation were devised and investigated.Much of the emphasis in the early work in this field,cailed computability theory,was on describing or characterizing those problems that could be solved algorithmically and on exhibiting some problems that could not be.One of the important negative results,established by Alan Turing.was the proof of the unsolvability of the"halting problem."The halting problem is to determine whether an arbitrary given algorithm (or computer program)will eventually hait(rather than,say, get into an infinite loop)while working on a given input.There cannot exist a computer program that solves this problem. Although computability theory has obvious and fundaniental implications for com- puter science,the knowledge that a prohlem can theoretically be solved on a computer is not sufficient to tell us whether it is practical to do so.For example,a perfect chess-playing program could be written.This would not be a very difficult task;there are only a finite number of ways to arrange the chess pieces on the board,and under certain rules a game must terminate after a finite number of moves.The program could consider each of the computer's possible moves,each of its opponent's possible responses,each of its possi- ble responses to those moves,and so on until each sequence of possible moves reaches an end.Then since it knows the ultimate result of each move.the computer can choose the best one.The number of distinct arrangements of pieces on the board that it is reasonable to consider(much less the number of sequences of moves)is roughly 1050 hy some esti- mates.A program that examined them all would take several thousand years to run.Thus such a program has not been run. Numerous prohlems with practical applications can be solved--that is,programs can be written for them-but the time and storage requirements are much too great for these programs to be of practical use.Clearly the time and space requirements of a program are of practical importance.They have become,therefore,the subject of theoretical study in the area of computer science called computational complexiry.One branch of this study, which is not covered in this book,is concerned with setting up a formal and somewhat abstract theory of the complexity of computable functions.(Solving a problem is equivalent to computing a function from the set of inputs to the set of outputs.)Axioms for measures of complexity have been formulated;they are basic and general enough so that either the number of instructions executed or the number of storage bits used by a program can be taken as a complexity measure.Using these axioms,we can prove the existence of arbitrarily complex problems and of problems for which there is no best program. The branch of computational complexity studied in this book is concerned with an- alyzing specific problems and specific algorithms.This book is intended to help readers build a repertoire of classic algorithms to solve common problems.some general design