Acknowledqments Therefore will I give thanks to thee PSALM 18:50 First thanks go to my home institution,the Weizmann Institute of Science,for providing the ideal supportive and encouraging environment for this kind of endeavor. My deepest gratitude goes to Yishai Feldman(who was my very first PhD student many years ago,and)who graciously agreed to join me in the preparation of this, the third,edition.I am grateful for the time,energy,and talent he put into this project.There is absolutely no way the revision would have been carried out without him. Parts of the original edition of the book were written while I was visiting Digital Equipment Corporation's Systems Research Center in Palo Alto,California,in the summer of 1985 and Carnegie-Mellon University's Computer Science Department for the 1986/7 academic year.I would like to express my deepest gratitude for these opportunities to work on the book undisturbed.Later visits to Cornell University, Bell Labs,NASA,and Lucent Technologies provided time to work on some of the revisions for the second and third editions. The late T.Yuval,Managing Editor of the Broadcast University programs on the Israeli radio channel "Galei Zahal,"deserves special thanks for convincing me to prepare the 1983-4 lecture series out of which the original version of this book later grew. I am indebted to my colleagues at the Weizmann Institute,A.Pnueli,A.Shamir, and S.Ullman,for discussions related to the material appearing herein.It is amazing how one's whole approach can benefit from being surrounded by researchers of such caliber. A very special thanks goes to R.Rosner,who co-authored the exercises and solutions,which first appeared as part of the second edition,and to Eyal Mashiah for his help in preparing the index for the present edition. I am grateful to the many people who read parts of the original 1987 manuscript or later editions,identified errors,made bibliographic suggestions,or provided helpful
P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Acknowledgments Therefore will I give thanks to thee PSALM 18: 50 First thanks go to my home institution, the Weizmann Institute of Science, for providing the ideal supportive and encouraging environment for this kind of endeavor. My deepest gratitude goes to Yishai Feldman (who was my very first PhD student many years ago, and) who graciously agreed to join me in the preparation of this, the third, edition. I am grateful for the time, energy, and talent he put into this project. There is absolutely no way the revision would have been carried out without him. Parts of the original edition of the book were written while I was visiting Digital Equipment Corporation’s Systems Research Center in Palo Alto, California, in the summer of 1985 and Carnegie-Mellon University’s Computer Science Department for the 1986/7 academic year. I would like to express my deepest gratitude for these opportunities to work on the book undisturbed. Later visits to Cornell University, Bell Labs, NASA, and Lucent Technologies provided time to work on some of the revisions for the second and third editions. The late T. Yuval, Managing Editor of the Broadcast University programs on the Israeli radio channel “Galei Zahal,” deserves special thanks for convincing me to prepare the 1983–4 lecture series out of which the original version of this book later grew. I am indebted to my colleagues at the Weizmann Institute, A. Pnueli, A. Shamir, and S. Ullman, for discussions related to the material appearing herein. It is amazing how one’s whole approach can benefit from being surrounded by researchers of such caliber. A very special thanks goes to R. Rosner, who co-authored the exercises and solutions, which first appeared as part of the second edition, and to Eyal Mashiah for his help in preparing the index for the present edition. I am grateful to the many people who read parts of the original 1987 manuscript or later editions, identified errors, made bibliographic suggestions, or provided helpful xvii
xviii Acknowledgments and insightful feedback.They include:S.Banerjee,M.Ben-Ari,H.Berliner,S.D Brookes,A.K.Chandra,N.Dershowitz,R.Fagin,A.Fiat,J.Gal-Ezer,A.Heydon, C.A.R.Hoare,L.Kari,D.E.Knuth,Q.Limmois,W.Pollock,R.Raz,Z.Reisel, E.Roberts,R.Rosner,S.Safra,J.Seiferas,D.Sherman,R.Sherman,B.Simons, D.Sleator,R.Topor,D.Tygar,M.Vardi,P.Wegner,and L.Zuck. D.H
P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 xviii Acknowledgments and insightful feedback. They include: S. Banerjee, M. Ben-Ari, H. Berliner, S. D. Brookes, A. K. Chandra, N. Dershowitz, R. Fagin, A. Fiat, J. Gal-Ezer, A. Heydon, C. A. R. Hoare, L. Kari, D. E. Knuth, Q. Limmois, W. Pollock, R. Raz, Z. Reisel, E. Roberts, R. Rosner, S. Safra, J. Seiferas, D. Sherman, R. Sherman, B. Simons, D. Sleator, R. Topor, D. Tygar, M. Vardi, P. Wegner, and L. Zuck. D.H
PARTI Preliminaries Nowe,these are the foundations II CHRONICLES 3:3
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 PART I Preliminaries Now, these are the foundations II CHRONICLES 3: 3 1
CHAPTER 1 Introduction and Historical Review Though thy beginning as small,yet thy end will be very or,What's It All About? great JoB 8:7 Computers are amazing machines.They seem to be able to do anything.They fly aircraft and spaceships,and control power stations and hazardous chemical plants. Companies can no longer be run without them,and a growing number of sophisti- cated medical procedures cannot be performed in their absence.They serve lawyers and judges who seek judicial precedents in scores of documented trials,and help scientists in performing immensely complicated and involved mathematical com- putations.They route and control millions of telephone calls in networks that span continents.They execute tasks with enormous precision-from map reading and typesetting to graphical picture processing and integrated circuit design.They can relieve us of many boring chores,such as keeping a meticulous track of home ex- penses,and at the same time provide us with diverse entertainment such as computer games or computerized music.Moreover,the computers of today are hard at work helping design the even more powerful computers of tomorrow. It is all the more remarkable,therefore,that the digital computer-even the most modern and complex one-can be thought of as merely alarge collection of switches. These switches,or bits as they are called,are not"flipped"by the user,but are special, internal switches that are"flipped"by the computer itself.Each bit can be in one of two positions,or,to put it another way,can take on one of two values,0 or 1. Typically,the value of a bit is determined by some electronic characteristic,such as whether a certain point has a positive or a negative charge. A computer can directly execute only a small number of extremely trivial opera- tions,like flipping,zeroing,or testing a bit.Flipping changes the bit's value,zeroing makes sure that the bit ends up in the 0 position,and testing does one thing if the bit is already in the 0 position,and another if it is not(see Figure 1.1). Computers may differ in size (according to the number of available bits),in the types of elementary operations they can perform,in the speed in which these operations are performed,in the physical media that embody the bits and their internal organization,and,significantly,in their external environment.This last item means that two computers,which are otherwise similar in function,might seem very
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 CHAPTER 1 Introduction and Historical Review or, What’s It All About? Though thy beginning was small, yet thy end will be very great JOB 8: 7 Computers are amazing machines. They seem to be able to do anything. They fly aircraft and spaceships, and control power stations and hazardous chemical plants. Companies can no longer be run without them, and a growing number of sophisticated medical procedures cannot be performed in their absence. They serve lawyers and judges who seek judicial precedents in scores of documented trials, and help scientists in performing immensely complicated and involved mathematical computations. They route and control millions of telephone calls in networks that span continents. They execute tasks with enormous precision—from map reading and typesetting to graphical picture processing and integrated circuit design. They can relieve us of many boring chores, such as keeping a meticulous track of home expenses, and at the same time provide us with diverse entertainment such as computer games or computerized music. Moreover, the computers of today are hard at work helping design the even more powerful computers of tomorrow. It is all the more remarkable, therefore, that the digital computer—even the most modern and complex one—can be thought of as merely a large collection of switches. These switches, or bits as they are called, are not “flipped” by the user, but are special, internal switches that are “flipped” by the computer itself. Each bit can be in one of two positions, or, to put it another way, can take on one of two values, 0 or 1. Typically, the value of a bit is determined by some electronic characteristic, such as whether a certain point has a positive or a negative charge. A computer can directly execute only a small number of extremely trivial operations, like flipping, zeroing, or testing a bit. Flipping changes the bit’s value, zeroing makes sure that the bit ends up in the 0 position, and testing does one thing if the bit is already in the 0 position, and another if it is not (see Figure 1.1). Computers may differ in size (according to the number of available bits), in the types of elementary operations they can perform, in the speed in which these operations are performed, in the physical media that embody the bits and their internal organization, and, significantly, in their external environment. This last item means that two computers, which are otherwise similar in function, might seem very 3
4 I.Preliminaries Figure 1.1 if this bit Operations on bits. flip this bit zero this bit is 1,flip this bit 01011 01011 01011 if this bit flip this bit zero this bit is 1,flip this bit 01001 01001 01011 01101 01001 11011 Flipping Zeroing Testing different to an observer:one might resemble a television set with a keyboard,while the other might be buried under the dials and knobs of an automatic knitting machine. However,the outward appearance is of peripheral importance when compared to the bits and their internal arrangement.It is the bits that"sense"the external stimuli arriving from the outside world via buttons,levers,keys on a keyboard,electronic communication lines,and even microphones and cameras.It is the bits that"decide" how to react to these stimuli and respond accordingly by directing other stimuli to the outside via displays,screens,printers,loudspeakers,beepers,levers,and cranks. How do the computers do it?What is it that transforms such trivial operations on bits into the incredible feats we see computers perform?The answer lies in the central concepts of this book:the process,and the algorithm that prescribes it and causes it to take place. Some Gastronomy Imagine a kitchen,containing a supply of ingredients,an array of baking utensils, an oven,and a (human)baker.Baking a delicious raisin cake is a process that is carried out from the ingredients,by the baker,with the aid of the oven,and,most significantly,according to the recipe.The ingredients are the inputs to the process, the cake is its output,and the recipe is the algorithm.In other words,the algorithm prescribes the activities that constitute the process.The recipes,or algorithms,rel- evant to a set of processes under discussion are generally called software,whereas utensils and oven represent what is generally known as hardware.The baker,in this case,can be considered a part of the hardware(see Figure 1.2). As in the case of bit operations,the baker/oven/utensils constellation has very limited direct abilities.This cake-baking hardware can pour,mix,spread,drip,light the oven,open the oven door,measure time,or measure quantities but cannot directly bake cakes.It is the recipes-those magical prescriptions that convert the limited abilities of kitchen hardware into cakes-and not ovens or bakers,that are the subject of this book
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 4 I. Preliminaries 01011 01001 01101 flip this bit flip this bit Flipping 01011 01001 01001 zero this bit zero this bit Zeroing 01011 01011 11011 if this bit is 1, flip this bit if this bit is 1, flip this bit Testing Figure 1.1 Operations on bits. different to an observer: one might resemble a television set with a keyboard, while the other might be buried under the dials and knobs of an automatic knitting machine. However, the outward appearance is of peripheral importance when compared to the bits and their internal arrangement. It is the bits that “sense” the external stimuli arriving from the outside world via buttons, levers, keys on a keyboard, electronic communication lines, and even microphones and cameras. It is the bits that “decide” how to react to these stimuli and respond accordingly by directing other stimuli to the outside via displays, screens, printers, loudspeakers, beepers, levers, and cranks. How do the computers do it? What is it that transforms such trivial operations on bits into the incredible feats we see computers perform? The answer lies in the central concepts of this book: the process, and the algorithm that prescribes it and causes it to take place. ■ Some Gastronomy Imagine a kitchen, containing a supply of ingredients, an array of baking utensils, an oven, and a (human) baker. Baking a delicious raisin cake is a process that is carried out from the ingredients, by the baker, with the aid of the oven, and, most significantly, according to the recipe. The ingredients are the inputs to the process, the cake is its output, and the recipe is the algorithm. In other words, the algorithm prescribes the activities that constitute the process. The recipes, or algorithms, relevant to a set of processes under discussion are generally called software, whereas utensils and oven represent what is generally known as hardware. The baker, in this case, can be considered a part of the hardware (see Figure 1.2). As in the case of bit operations, the baker/oven/utensils constellation has very limited direct abilities. This cake-baking hardware can pour, mix, spread, drip, light the oven, open the oven door, measure time, or measure quantities but cannot directly bake cakes. It is the recipes—those magical prescriptions that convert the limited abilities of kitchen hardware into cakes—and not ovens or bakers, that are the subject of this book