Handbook of Theoretical Computer Science - 2 Vol Set

Rating:
Summary: Massive collection on computer science
Review: This collection of articles on the foundations of computer science is a nice addition addition to the literature and guides the reader to further reading on the subject. I did not read all of the chapters so I will concentrate my remarks on the ones that I did: Chapter 4 on Kolmogorov complexity puts emphasis on the applications and the authors endeavor to bring the reader quickly to the level of understanding needed for applications. The ones discussed are primarily in the area of parallel computation and branching programs. The chapter on algorithms for finding patterns in strings is nicely written and the authors do a good job of summarizing the main results. Computational biologists dealing with string matching algorithms may find the presentation very helpful. The author uses pseudocode to illustrate the main algorithms, such as Knuth-Morriss-Platt, Boyer-Moore, Aho-Corasick, and Commentx-Walter. Concrete examples are given for each of these algorithms. The chapter on computational geometry discusses the main algorithms for finding convex hulls and Voronoi diagrams are discussed in fairly good detail. Linear programming, triangulation, and point locating are given a fast treatment. The author does make use of pictures to illustrate the the algorithms. The only disappointment was that combinatorial geometry was given only a very cursory treatment. Of particular importance to me was the chapter on algorithms in number theory. Interestingly, the authors jump right into a discussion of elliptic curves and actually do a fairly good job (within 4 pages) of summarizing this massive area of mathematics. The authors return to elliptic curves in a later section on factoring integers, after discussing algorithms for finite abelian groups. The Shanks baby-step-giant-step, Pollard's rho method, the Chinese Remainder theorem, and the index calculus algorithm are discussed concisely. Elliptic curves are again used in the section on primality testing. There is a good summary of cryptography in Chapter 13, with the most interesting discussions on probabilistic encryption, "over-the-phone" poker, and zero-knowledge interactive proofs. In Volume B, those interested in the foundations of logic and functional programming, Chapter 6 on rewrite systems covers the main points. The chapter is fairly long an detailed. Functional programming and lambda calculus are contained in the next chapter with proofs given of the main results. The most interesting section is on denotational semantics. LISP is discussed a little at the end of the chapter. Chapter 10 also discusses logic programming in a fairly detailed manner. The most interesting sections are the ones on the completion of programs and deductive databases. The author ends the chapter with a brief history of logic programming. In reading this I found out that there has been work done on developing a theory of logic programming based on 3-valued logic and useful references were given. The theory of relational databases in covered in Chapter 17. This is of overwhelming importance today and the author does a decent job of outlining what relational databases are all about. The section on query optimization is particularly illuminating. Although the text is very formal and very far away from the everday practice of database management, reading it does give a deeper appreciation of the foundations of the subject. Overall, a very fine addition to the literature...I hope the publishers decide to move ahead with an updated edition.