hobbit@SHUM.HUJI.AC.IL (yoav gonen) (05/07/91)
Gregory Rawlins wrote, refering to Manber's book (Introduction to Algorithms): > Why the hysteria? Looking at the list of point you give leads me to > suspect that you don't want a textbook, but a handbook or reference book. > Manber's book is an attempt to teach students to think for themselves. I was looking for a book which will help me will the course : Algorithms that I learn in the university. So I bought Manber's. Unfortunately, the book covers only 25% of the material that I learned in class. Diane Musicant wrote: > Manber's book was extremely helpful for me! I was> > told by one of my profs that the book was written for just such a > purpose - to make the learning less intensive. He highly recommended it, > and now, so do I. That was my problem too: my lecturer in the course alse recommended that book. But never mind. I want to show you several examples from the book itself: 1. Page 242: It says: "If the capacities of all edges in the network are INTEGERS, then there is a maximum-flow whose value is an integer..." Now, a man who reads that will soon ask himself: So, what about non-integers? Why can't it work then??? So here is challenge to all of you: Try to find an example of a network, with edges that are NOT integers - that whatever you'll do: there will always be an augmenting path. It is very hard to find such an example. That should have been Manber's job. HE should have shown us the example. But he didn't. 2. Page 189: Manber talks about the problem of Eulerian Circuit. Instead of showing us the complexity of his algorithm (which is O(n^3) - but this is not so trivial to prove it) he goes straightly to the next problem. 3. Page 307: "This algorithm is known as the FOUR-RUSSIANS-ALGORITHM." This is not true. The complexity of the algorithm which is described in the book is O(n^3/logn), while the F-R-A take only O(n^3/(logn)^2). 4. Page 309: The fast fourier transform. Although FTF is the best way to solve the problem of p(x)*q(x), a polynomial product can easily be solved by an algorithm of O(n^1.5) without needing FTF. FTF is used by more complicate problems. ________________________________________ | Yoav Gonen | | The Hebrew University, Givat Ram | | Jerusalem, Israel. | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^