xii Preface universal agreement on a core of fundamental topics that computer science students should be taught. It would appear that anyone associated with computers ought to be aware of these topics,and not only those who have decided to spend three or four years getting a particular kind of academic diploma.Moreover,given that a revolution is indeed taking place before our very eyes,many of these topics,and the special ways of thinking that go with them,ought to be available to the enquiring person even if that person is not directly associated with a computer at all. Books concerned primarily with computers or programming are intended to fulfill quite different needs.Computers are made of bits and bytes,and programming is car- ried out using languages with rigid rules of grammar and punctuation.Consequently, computer books often suffer from the"bit/byte syndrome"and programming books from the"semicolon syndrome."In other words,the reader becomes predominantly involved in the principles of a particular computer or the syntactic rules of a particu- lar programming language (or both).It would seem that things cannot be explained without first describing,in detail,either a machine or a medium for communicating with one (or both). Many advanced textbooks do treat the fundamentals,but by their very nature they concentrate on specific topics,and do so at an advanced technical level that is usually unsuitable for the general reader.Even professional programmers and systems analysts might lack the background or motivation required to get through books aimed at full-time computer science students. Curiously,there appears to be very little written material devoted to the science of computing and aimed at the technically-oriented general reader as well as the computer professional.This fact is doubly curious in view of the abundance of precisely this kind of literature in most other scientific areas,such as physics,biology, chemistry,and mathematics,not to mention humanities and the arts.There appears to be an acute need for a technically-detailed,expository account of the fundamentals of computer science;one that suffers as little as possible from the bit/byte or semicolon syndromes and their derivatives,one that transcends the technological and linguistic whirlpool of specifics,and one that is useful both to a sophisticated layperson and to a computer expert.It seems that we have all been too busy with the revolution to be bothered with satisfying such a need. This book is an attempt in this direction.Its objective is to present a readable account of some of the most important and basic topics of computer science,stress- ing the fundamental and robust nature of the science in a form that is virtually independent of the details of specific computers,languages,and formalisms. This book grew out of a series of lectures given by the first author on"Galei Zahal," one of Israel's national radio channels,between October 1984 and January 1985.It is about what shall be called algorithmics in this book,that is,the study of algorithms. An algorithm is an abstract recipe,prescribing a process that might be carried out by a human,by a computer,or by other means.It thus represents a very general concept,with numerous applications.Its principal interest and use,however,is in those areas where the process is to be carried out by a computer.P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 xii Preface universal agreement on a core of fundamental topics that computer science students should be taught. It would appear that anyone associated with computers ought to be aware of these topics, and not only those who have decided to spend three or four years getting a particular kind of academic diploma. Moreover, given that a revolution is indeed taking place before our very eyes, many of these topics, and the special ways of thinking that go with them, ought to be available to the enquiring person even if that person is not directly associated with a computer at all. Books concerned primarily with computers or programming are intended to fulfill quite different needs. Computers are made of bits and bytes, and programming is car￾ried out using languages with rigid rules of grammar and punctuation. Consequently, computer books often suffer from the “bit/byte syndrome” and programming books from the “semicolon syndrome.” In other words, the reader becomes predominantly involved in the principles of a particular computer or the syntactic rules of a particu￾lar programming language (or both). It would seem that things cannot be explained without first describing, in detail, either a machine or a medium for communicating with one (or both). Many advanced textbooks do treat the fundamentals, but by their very nature they concentrate on specific topics, and do so at an advanced technical level that is usually unsuitable for the general reader. Even professional programmers and systems analysts might lack the background or motivation required to get through books aimed at full-time computer science students. Curiously, there appears to be very little written material devoted to the science of computing and aimed at the technically-oriented general reader as well as the computer professional. This fact is doubly curious in view of the abundance of precisely this kind of literature in most other scientific areas, such as physics, biology, chemistry, and mathematics, not to mention humanities and the arts. There appears to be an acute need for a technically-detailed, expository account of the fundamentals of computer science; one that suffers as little as possible from the bit/byte or semicolon syndromes and their derivatives, one that transcends the technological and linguistic whirlpool of specifics, and one that is useful both to a sophisticated layperson and to a computer expert. It seems that we have all been too busy with the revolution to be bothered with satisfying such a need. This book is an attempt in this direction. Its objective is to present a readable account of some of the most important and basic topics of computer science, stress￾ing the fundamental and robust nature of the science in a form that is virtually independent of the details of specific computers, languages, and formalisms. ■ ■ This book grew out of a series of lectures given by the first author on “Galei Zahal,” one of Israel’s national radio channels, between October 1984 and January 1985. It is about what shall be called algorithmicsin this book, that is, the study of algorithms. An algorithm is an abstract recipe, prescribing a process that might be carried out by a human, by a computer, or by other means. It thus represents a very general concept, with numerous applications. Its principal interest and use, however, is in those areas where the process is to be carried out by a computer