Preface XV The first noticeable difference is that for this revision I needed real help..., and was fortunately joined by Yishai Feldman.He has taken part in all aspects of the revision,but most significantly took upon himself the thorough revision of the material on programming languages and the writing of the new chapter on software engineering. The main changes are as follows: The book now has five Parts,rather than four.In Part I(Preliminaries)Chapter 3 has been completely rewritten,and is now titled"Programming Languages and Paradigms."The list of languages discussed has been revised and is organized into paradigms,thus giving a more informative and updated exposition of the media we use when we program computers.Discussions of some languages (e.g.,APL and SNOBOL)have been dropped altogether and those of others (e.g.,C,C++and JAVA) have been added. Part II(Methods and Analysis)and Part III(Limitations and Robustness),i.e., Chapters 4 through 9,required no sweeping changes.This can again be attributed to the "classical"nature of the topics chosen for these,as mentioned in the "New to the second edition"section above. The first chapter of Part IV (Relaxing the Rules)was previously titled"Paral- lelism and Concurrency"and is now called"Parallelism,Concurrency,and Alterna- tive Models."It incorporates new sections on quantum computing,including Shor's factoring algorithm,and a discussion of molecular computing.These topics may be considered to be additional forms of parallelism,albeit more radical ones.The re- maining two chapters of Part IV were constructed by separating out the material on probabilistic algorithms(Chapter 11)from that on cryptography(now Chapter 12) presented together in a single chapter in the previous editions-and extending both by discussions of some of the new developments in these fields. Part V(The Bigger Picture)ends with the closing chapter of the previous edi- tions,"Algorithmics and Intelligence,"which is now Chapter 15.However,this is now preceded by two new chapters:Chapter 13,"Software Engineering,"and Chapter 14,"Reactive Systems."The first of these is an attempt to provide a general introduction to the issues and problems arising in the development of large soft- ware systems.The second new chapter zeros in on the particular difficulties arising in the special case of reactive systems,as a result of their complex behavior over time. Besides these more noticeable changes,the entire text has been brought up to date in many less subtle and more subtle ways.There are discussions on abstract data types,on the nonapproximability of certain NP-complete problems,on proba- bilistically checkable proofs,and on the brand new AKS polynomial-time algorithm for primality.The final chapter has been modified in many places too,e.g.,with a discussion added on the Chinese room argument. While we have left the exercises and solutions essentially as they were in the second edition,the bibliographic notes were a completely different story.Twelve years in Computer Science is almost an eternity...The format of the notes is the same as in the previous editions;i.e.,a general section at the start of each chapter, which lists relevant books and periodicals,followed by detailed notes that progress with the text of the chapter itself and point back to its page numbers.In revising them,we had to prepare new notes for the large amount of newly added material, of course,but we also had to painstakingly reconsider and thoroughly revise the entire set of existing notes.Hopefully,the result of all of this will turn out to be aP1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 Preface xv The first noticeable difference is that for this revision I needed real help ... , and was fortunately joined by Yishai Feldman. He has taken part in all aspects of the revision, but most significantly took upon himself the thorough revision of the material on programming languages and the writing of the new chapter on software engineering. The main changes are as follows: The book now has five Parts, rather than four. In Part I (Preliminaries) Chapter 3 has been completely rewritten, and is now titled “Programming Languages and Paradigms.” The list of languages discussed has been revised and is organized into paradigms, thus giving a more informative and updated exposition of the media we use when we program computers. Discussions of some languages (e.g., APL and SNOBOL) have been dropped altogether and those of others (e.g., C, C++ and JAVA) have been added. Part II (Methods and Analysis) and Part III (Limitations and Robustness), i.e., Chapters 4 through 9, required no sweeping changes. This can again be attributed to the “classical” nature of the topics chosen for these, as mentioned in the “New to the second edition” section above. The first chapter of Part IV (Relaxing the Rules) was previously titled “Paral￾lelism and Concurrency” and is now called “Parallelism, Concurrency, and Alterna￾tive Models.” It incorporates new sections on quantum computing, including Shor’s factoring algorithm, and a discussion of molecular computing. These topics may be considered to be additional forms of parallelism, albeit more radical ones. The re￾maining two chapters of Part IV were constructed by separating out the material on probabilistic algorithms (Chapter 11) from that on cryptography (now Chapter 12)— presented together in a single chapter in the previous editions—and extending both by discussions of some of the new developments in these fields. Part V (The Bigger Picture) ends with the closing chapter of the previous edi￾tions, “Algorithmics and Intelligence,” which is now Chapter 15. However, this is now preceded by two new chapters: Chapter 13, “Software Engineering,” and Chapter 14, “Reactive Systems.” The first of these is an attempt to provide a general introduction to the issues and problems arising in the development of large soft￾ware systems. The second new chapter zeros in on the particular difficulties arising in the special case of reactive systems, as a result of their complex behavior over time. Besides these more noticeable changes, the entire text has been brought up to date in many less subtle and more subtle ways. There are discussions on abstract data types, on the nonapproximability of certain NP-complete problems, on proba￾bilistically checkable proofs, and on the brand new AKS polynomial-time algorithm for primality. The final chapter has been modified in many places too, e.g., with a discussion added on the Chinese room argument. While we have left the exercises and solutions essentially as they were in the second edition, the bibliographic notes were a completely different story. Twelve years in Computer Science is almost an eternity ... The format of the notes is the same as in the previous editions; i.e., a general section at the start of each chapter, which lists relevant books and periodicals, followed by detailed notes that progress with the text of the chapter itself and point back to its page numbers. In revising them, we had to prepare new notes for the large amount of newly added material, of course, but we also had to painstakingly reconsider and thoroughly revise the entire set of existing notes. Hopefully, the result of all of this will turn out to be a