Reviews (12)

Good overall.
A well-written book that teaches you how to think about complexity theory instead of just a flat summary of results. Something like Lewis and Papadimitriou's _Elements of the Theory of Computation_ would be more than enough preparation for this (note that the style of these books is quite different- this one is more informal and descriptive). Covers all the material you need in a first text. Has a good little introduction to mathematical logic in it, including a nice succinct version of Godels Incompleteness Theorem.Lots of interesting exercises.

Upon Leaving The Realm Of Sense, For Points Distant
*Computational Complexity* is a great introduction to contemporary formal logic, which is more heavily mathematical than even the great mathematical logicians of the past were.It's a great introduction, even though they put a good-lookin' chick on the *back* cover (what's that about?), because Papadimitriou does not suffer from what Quine called *mathematosis* -- he is not assimilating the material of logic (anything and everything symbolic) to the rigorized abstractions of mathematics.And as such, this book defines what I think *computer science* should be today by choosing the "greater of two evils".If you think that computer science began with Turing like most people, CS is about building machines that do what thinking beings do (problems of detail); but if you think that computer science began with Church's undecidability theorem, CS would be about figuring out why thinking beings fall down on the reasoning job (troubles with principle).

I prefer the second definition; and although I'm a little old-fashioned in my tastes (prove it by me), this book demonstrates such an attitude can be forward-looking.Although Church is not venerated throughout the book, a task handled by Papadimitriou in his earlier CS introduction with Lewis, unlike Hopcroft and Ullman the spirit of Church is very much present in Papadimitriou's teasing-apart of complexity problems from applied CS.Yes, it's never about the physical machine, and Ryle can go away instead of work like this -- which in my opinion could form the basis of a "computational psychology" concerned with the will to truth rather than the will to power.

All in one roof, but presentation very poor
I agree with the review by Arthur Fischer.Papadimitriou might
be an excellent researcher, but his communication skills are
hopeless and horrible.The typos make learning even harder.

Editorial Review

Aimed at any serious programmer or computer science student,the new second edition of Introduction to Algorithms builds onthe tradition of the original with a truly magisterial guide to theworld of algorithms. Clearly presented, mathematically rigorous, andyet approachable even for the math-averse, this title sets a highstandard for a textbook and reference to the best algorithms forsolving a wide range of computing problems.

With sample problems andmathematical proofs demonstrating the correctness of each algorithm,this book is ideal as a textbook for classroom study, but its reachdoesn't end there. The authors do a fine job of explaining eachalgorithm. (Reference sections on basic mathematical notation will helpreaders bridge the gap, but it will help to have some math backgroundto appreciate the full achievement of this handsome hardcover volume.)Every algorithm is presented in pseudo-code, which can be implementedin any computer language, including C/C++ and Java. This ecumenicalapproach is one of the book's strengths. When it comes to sorting andcommon data structures, from basic linked lists to trees (includingbinary trees, red-black, and B-trees), this title really shines, withclear diagrams that show algorithms in operation. Even if you justglance over the mathematical notation here, you can definitely benefitfrom this text in other ways.

The book moves forward with moreadvanced algorithms that implement strategies for solving morecomplicated problems (including dynamic programming techniques, greedyalgorithms, and amortized analysis). Algorithms for graphing problems(used in such real-world business problems as optimizing flightschedules or flow through pipelines) come next. In each case, theauthors provide the best from current research in each topic, alongwith sample solutions.

This text closes with a grab bag of usefulalgorithms including matrix operations and linear programming,evaluating polynomials, and the well-known Fast Fourier Transformation(FFT) (useful in signal processing and engineering). Final sections on"NP-complete" problems, like the well-known traveling salesman problem,show off that while not all problems have a demonstrably final and bestanswer, algorithms that generate acceptable approximate solutions canstill be used to generate useful, real-world answers.

Throughout thistext, the authors anchor their discussion of algorithms with currentexamples drawn from molecular biology (like the Human Genome Project),business, and engineering. Each section ends with short discussions ofrelated historical material, often discussing original research in eacharea of algorithms. On the whole, they argue successfully thatalgorithms are a "technology" just like hardware and software that canbe used to write better software that does more, with betterperformance. Along with classic books on algorithms (like DonaldKnuth's three-volume set, The Art of ComputerProgramming), this title sets a new standard for compiling thebest research in algorithms. For any experienced developer, regardlessof their chosen language, this text deserves a close look for extendingthe range and performance of real-world software. --RichardDragan

Reviews (4)

Excellent Introduction to Combinatorics
A COURSE IN COMBINATORICS covers a great breadth of topics under the label of "combinatorics," including graph theory, enumeration, and some algebra. The book is comprehensive; the instructor can pick-and-choose appropriate material from the huge array provided without detriment to understanding.

Each chapter is written in a friendly, accessible manner: plenty of interesting and instructive examples follow the clear definitions and preliminaries. To give the reader an idea of the topics presented in the book, a list of chapters follows:

1. Graphs
2. Trees
3. Colorings of graphs and Ramsey's theorem
4. Turan's theorem and extremal graphs
5. Systems of distinct representatives
6. Dilworth's theorem and extremal set theory
7. Flows in networks
8. De Bruijn sequences
9. Two (0,1,*) problems: addressing for graphs and a hash-coding scheme
10. The principle of inclusion-exclusion; inversion formulae
11. Permanents
12. The Van der Waerden conjecture
13. Elementary counting; Stirling numbers
14. Recursions and generating functions
15. Partitions
16. (0,1)-Matrices
17. Latin Squares
18. Hadamard matrices, Reed-Muller codes
19. Designs
20. Codes and designs
21. Strongly regular graphs and partial geometries
22. Orthogonal Latin squares
23. Projetive and combinatorial geometries
24. Gaussian numbers and q-analogues
25. Lattices and Mobius inversion
26. Combinatorial designs and projective geometries
27. Difference sets and automorphisms
28. Difference sets and the group ring
29. Codes and symmetric designs
30. Association schemes
31. (More) algebraic techniques in graph theory
32. Graph connectivity
33. Planarity and coloring
34. Whitney duality
35. Embeddings of graphs on surfaces
36. Electrical networks and squared squares
37. Polya theory of counting
38. Baranyai's theorem

The problems in the book are generally very rich and well-written, with helpful hints from the appendix that provide motivation but do not spoil. However, the relative difficulty of the problems is not readily made appparent, so over- or underthinking of problems often occurs with misjudgments.

For the interested high-school student to the beginning graduate, this book is ideal for the study of combinatorics. Truly a nice read that connects many areas of mathematics and combines them into a thing of true beauty.

A nice tour of combinatorics
The first word that comes to my mind when I think of this text is "encyclopedic". It contains around 40 chapters, hitting most of the high points of combinatorics that a graduate student should see. The exposition is generally good with nice examples. The one thing that I fault it for is the number of statements that the authors claim are "obvious". In a way, this is good, because it makes you pay attention and understand the material, but sometimes the statement isn't obvious until you've thought about it for an hour and written out a lengthy proof. At that point, it does become completely obvious and you can't believe that you ever thought it wasn't, so I can understand why van Lint and Wilson fell into the trap so often. (In fact, I've heard that Wilson even stumbles over some of those points in lectures.) This is a great book to have on your shelf if you need somewhere to look up combinatorial ideas.

A gentle introduction to combinatorics
This book was the text for a graduate-level course I took.The presentation is very laid-back, much like the lecturing style of one of the authors (Wilson), and so it was quite readable (unlike many other mathbooks which you have to stop every few pages and pick apart everythingbefore it sinks in).

Combinatorics is a relatively recent development inmathematics, one which is generally easy to explain, but with manydifficult open questions.Van Lint and Wilson do an excellent jobexplaining, but there are a few places where the reader needs to know somebackground to place the particular problem in the appropriate mathematicalcontext.Understandably, if the authors were to include all themathematical machinery needed, the book would be huge!Instead, they havechosen to describe as many facets of the field as possible, and thereforehave written a broad, well-balanced book which approaches the topic in anon-threatening way.

My one criticism, then, is that there is a lack ofdepth in several areas of the book, with further discussion of advancedtopics or open problems.But even so, I can appreciate the omission forthe sake of accessibility.

Editorial Review

This book's introduction features a humorous story of a man with a line of people behind him, who explains to his boss, "I can't find an efficient algorithm, but neither can all these famous people." This man illustrates an important quality of a class of problems, namely, the NP-complete problems: if you can prove that a problem is in this class, then it has no known polynomial-time solution that is guaranteed to work in general. This quality implies that the problem is difficult to deal with in practice.

Reviews (2)

University Level material
I have used this textbook when delivering a second year University class on this topic and found that the thorough coverage of the topics was appreciated by my students. Even more important to them was the large number of examples that are presented, in detail, throughout the text.

This is a University Level textbook, not a Study Guide, and respects the reader's intellectual maturity by preparing them for subsequent classes. The perception of "density" implies that it is best taken with a liberal dose of classroom instruction - not many students seem to intuitively grasp discrete mathematics and learn the material wholly on their own. I know that I certainly did not when I was an undergrad!

For students who feel that the material is difficult, I always suggest using the library for another point of view. I also recommend the Schaum's Outline for Discrete Mathematics as a companion if the student is having significant difficulty with the concepts.

Obviously, I like the book, so why not a 5? Unfortunately, I don't know of any books that I would grant a 5 - the authors can always do something better :-)

Reviews (2)

Good but Brief Book
Buchmann's text provides an excellect introduction to cryptography for those who are comfortable with mathematical rigour, and have some knowledge of number theory.Buchmann does provide a review for each of the number theoretic concepts he introduces throughout the text.However, one who is unfamiliar with number theory and not comfortable with learning by proofs might get lost.The other problem with the text is its brevity.This might be suitable for a class on cryptograpy, but it proves quite detremental to self-study.The brevity is especially problematic in the section dealing with Elliptic Curve Crypto (3 and 1/2 pages)Overall, I would recommend this book to anyone who is comfortable with rigour, and doesn't mind brevity.

Reviews (4)

great book, but not available here
I have this book checked out from a university library, and it is quite wonderful.Despite the fact that Amazon continues to list it for sale, it is not currently available.

Self-contained Encyclopedia! All you need is your patience!
This encyclopedic monograph is now a classic of this field,
lambda-calculus, which is the theoretical basis of practical
functional programming languages such as Standard ML, CAML, Haskell etc.

This book itself is purely theoretical and principally aimed for researchers/students of its field.

This book is very comprehensive. In fact, this book successfully compiles almost all results on type-free lambda-calculus up to the time of its publication (early 1980's).

Surprisingly enough!, however, this very technical encyclopedic monograph is self-contained.

Proofs of all theorems/lemmata are given up to details except for cases that they are intentionally left for excercises.

Therefore, even a novice of its field can follow all of the proofs. The only one thing that such a novice must have is patience. His/her patience will surely be rewarded.

Backgrounds assumed in this encyclopedic monograph is the very beginning level understanding of mathematical logic. If you are not familiar with math logic, you can learn the necessary backgrounds with any introductory textbooks on math logic.

All more technical notions and notations are defined/explained in this book. Many interesting examples are given.

Exercises at the end of each charpter are very helpful and also are very interesting. The author clearly paid much attention and took care on the arrangement of exercises so that readers can tackle easier one at first. Moreover such carefully arranged exercises tell readers more. Readers will understand very delicate but important points during solving exercises by themselves. In other words, the last sentence means the following fact: imagine there are two intuitively similar notions
(it is often the case that very abstract theory has many such pairs of notions) that novices can confuse each other. Solving one exercise tell the novice that one notion is not implied from the other. Also solving another exercise tell vice-versa.

Indices and references are very useful. In fact, indices are carefully designed. Not only the index of technical terms, there are indices for symbols and authors (of references refered in the main text). References are very comprehensive.

There are very few typos (another surprising points! Math books almost always handreds of typos) except for misuses of type-faces which are clearly due to typesetting by the publisher.

This book, as I pointed before, is on pure math logic and its readership is clearly researchers/students of its field.

But, as a computer scientist, I recommend this book to all of the functional programmers, who, at least, are serious about the background of their profession.

If you read this book, you will understand that there is a very beautiful (though abstract) world of theories behind ML/Haskell programming.

If you are a student who wants study lambda-calculus, combinatory logic, type theory, constructive math, etc.,
then, this book is for you, too, of course.
This encyclopedia doubtlessly will give you the basis to become the researcher on such fields.