Preface xiii The book could be used as the basis of a one-semester introductory course in computer science or a general computer science literacy course in science and engineering schools.Moreover,it can be used as supplementary reading in many kinds of computer-related educational activities,from basic programming courses to advanced graduate or undergraduate degree programs in computer science.The material covered herein,while not directly aimed at producing better programmers or system analysts,can aid people who work with computers by providing an overall picture of some of the most fundamental issues relevant to their work. The preliminary chapters discuss the concept of an algorithmic problem and the algorithm that solves it,followed by cursory discussions of the structure of algo- rithms,the data they manipulate,and the languages in which they are programmed. With the stage thus set,Part Two of the book turns to some general methods and paradigms for algorithmic design.This is followed by two chapters on the ana- lysis of algorithms,treating,respectively,their correctness and efficiency(mainly time efficiency),including techniques for establishing the former and estimating the latter.Part Three of the book is devoted to the inherent limitations of effectively executable algorithms,and hence of the computers that implement them.Certain precisely defined problems,including important and practical ones,are shown to be provably not solvable by any computers of reasonable size in any reasonable amount of time (say,the lifetime of a person),and never will be.Worse still,it is shown that some problems are provably not solvable by computers at all,even with unlimited time!In Part Four of the book'the requirements are relaxed,for example, by employing concurrent activities or coin tossing,in order to overcome some of these difficulties.These chapters also discuss reactive and distributed systems, and cryptography.Finally,the relationship of computers to human intelligence is discussed,emphasizing the"soft"heuristic,or intuitive,nature of the latter,and the problems involved in relating it to the"hard"scientific subject of algorithmics. The book is intended to be read or studied sequentially,not to be used as a reference.It is organized so that each chapter depends on the previous ones,but with smooth readability in mind.Most of the material in the preliminary Part One should be familiar to people with a background in programming.Thus,Chapters 1 and 2 and parts of Chapter 3 can be browsed through by such readers. Certain sections contain relatively technical material and can be skipped by the reader without too much loss of continuity.They are indented,set in smaller type and are prefixed by a small square.It is recommended,however,that even those sections be skimmed,at least to get a superficial idea of their contents. Whenever appropriate,brief discussions of the research topics that are of current interest to computer scientists are included.The text is followed by a section of detailed bibliographic notes for each chapter,with"backward"pointers connecting the discussions in the text with the relevant literature. ■ 1 See the section below,"New to the third edition,"as there is now a fifth Part and the division is somewhat different.P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Preface xiii The book could be used as the basis of a one-semester introductory course in computer science or a general computer science literacy course in science and engineering schools. Moreover, it can be used as supplementary reading in many kinds of computer-related educational activities, from basic programming courses to advanced graduate or undergraduate degree programs in computer science. The material covered herein, while not directly aimed at producing better programmers or system analysts, can aid people who work with computers by providing an overall picture of some of the most fundamental issues relevant to their work. ■ ■ The preliminary chapters discuss the concept of an algorithmic problem and the algorithm that solves it, followed by cursory discussions of the structure of algo￾rithms, the data they manipulate, and the languagesin which they are programmed. With the stage thus set, Part Two of the book turns to some general methods and paradigms for algorithmic design. This is followed by two chapters on the ana￾lysis of algorithms, treating, respectively, their correctness and efficiency (mainly time efficiency), including techniques for establishing the former and estimating the latter. Part Three of the book is devoted to the inherent limitations of effectively executable algorithms, and hence of the computers that implement them. Certain precisely defined problems, including important and practical ones, are shown to be provably not solvable by any computers of reasonable size in any reasonable amount of time (say, the lifetime of a person), and never will be. Worse still, it is shown that some problems are provably not solvable by computers at all, even with unlimited time! In Part Four of the book1 the requirements are relaxed, for example, by employing concurrent activities or coin tossing, in order to overcome some of these difficulties. These chapters also discuss reactive and distributed systems, and cryptography. Finally, the relationship of computers to human intelligence is discussed, emphasizing the “soft” heuristic, or intuitive, nature of the latter, and the problems involved in relating it to the “hard” scientific subject of algorithmics. The book is intended to be read or studied sequentially, not to be used as a reference. It is organized so that each chapter depends on the previous ones, but with smooth readability in mind. Most of the material in the preliminary Part One should be familiar to people with a background in programming. Thus, Chapters 1 and 2 and parts of Chapter 3 can be browsed through by such readers. Certain sections contain relatively technical material and can be skipped by the reader without too much loss of continuity. They are indented, set in smaller type and are prefixed by a small square. It is recommended, however, that even those sections be skimmed, at least to get a superficial idea of their contents. Whenever appropriate, brief discussions of the research topics that are of current interest to computer scientists are included. The text is followed by a section of detailed bibliographic notes for each chapter, with “backward” pointers connecting the discussions in the text with the relevant literature. ■ ■ 1 See the section below, “New to the third edition,” as there is now a fifth Part and the division is somewhat different