Thanks for the feedback! I recognize the deficiencies of my English writing. Moreover, the current state of the book is, in fact, much-much better than the original manuscript thanks to the efforts of Dr. Robert Strandh, phoe, and Apress proofreaders. As for the residual ugliness -
c'est la vie...
You're quite right that SICP is about the fundamentals. Progalgs is about writing efficient programs. It's for those who already understand the fundamentals.
In the preface, I discuss a bit the topic of how algorithms are taught in the universities versus how they are actually used. I made a choice to lean heavily towards the "practical" approach. So, from the perspective of a student, this shouldn't be your principal manual, the theory isn't presented in the best possible way, to say the least. (As a manual I'd recommend Skiena, or you can use Cormen etc.) But if you read the book as supplementary material it can give you a different perspective on those theoretical concepts and, hopefully, you'll get more value from studying them as you'll see where it all leads and how you might be using the obtained knowledge in your further work.
As for Lisp, I don't think that picking it for any smart student should be a problem.
For those who haven't heard about the book yet: it is a practical description of the main data structures and algorithms in use today. The book is also featuring a presentation of the most important algorithm development techniques, as well a examples of the real-world use cases in each chapter. It uses Common Lisp as an implementation language, and also contains a crash course into the language if you are not yet familiar with it.
Yes, I plan to have a paperback version for $20+shipment. If you send me an email to [email protected] I'll include you in the distribution (and send the details on how to pay and receive a copy in a week or two)
thanks for the notice (my typing habit is such that I often don't press the keys hard enough which results in missing letters - easy to see thanks to the spellcheckers when a normal word is misspelled, not so hard for personal names though). Typo fixed
It depends on what you code and how. I hope the book explains some of the approaches and describes the tools that can be used to reduce that difference and avoid a tragedy :)
I examined Union-Find in more detail and found the critical flaw in my description that you were pointing too. Unfortunately, I forgot about it and had a simplified view of this data structure that focused on improving Find but neglected Union. The funny thing is that it was discussed, at times, at group job interviews that I participated as one of the interviewers, and we didn't go these deep to uncover that flaw :) (or, maybe, it was long ago enough for me to forget).
Surely, that made the example not so bright (as we couldn't reduce everything to a constant-time version with very simple code), but I don't think that the example is inappropriate. It still remains quite simple from the code standpoint. Another reason I picked it was that it didn't require an explanation of any additional data-structure, even, an array, and all the information could be efficiently represented using structs. This still holds.
> This doesn't mention the function slot of the symbol, so one could perhaps argue that therefore the function slot is not meant to be a constant variable
Exactly
> but one could equally well argue the opposite
No, as variables and functions are different parts and there's a more general rule about functions applied to keywords.
Your argument seems to be based on a notion that keywords are something unique and special in CL. They are, but only to the extent that is specified in this section. Otherwise, they are the same as other symbols.
To me, Lisp is not about "forbidden all that's not explicitly allowed", but about "allowed all that's not explicitly forbidden" mentality. And it's, actually, an important trait of the language that makes me value it more than others. So, sorry, I value your opinion, but I think that such things as := need to exist if only to broaden the horizons of people with such opinions :)
Sorry, getting back to the initial point: can you point to a statement in the standard that forbids assigning to symbol-function of keywords or dims it unspecified behavior? I see only this: http://www.lispworks.com/documentation/HyperSpec/Body/t_kwd.... that doesn't state anything like this. Besides these constraints, the keyword symbols are normal symbols so they should abide by the same rules.
> but then just assumes that computational complexity and O-notation are known.
At the bottom, you can find a reference to the previously published chapters. Complexity & big-O was addressed in the initial. (This is part of a book, all the org details are explained in part 1)
> There is no path compression.
The second variant is path compression. Yes, it may also be implemented in find, but it will make the code more complicated, in my view.
> And then, the uf-union operation: No practical union-find implementation accesses the list of all entries in this operation.
You are correct here. I'll make a change, thanks.
> Also, uf-add seems to allow adding new entries to the data structure but does not add them to the points list
This isn't needed here as it is supposed that we already have the list of points, it's just not arranged for efficient disjoint test. I, actually, had the reference to it, initially, but removed as I considered it redundant. I
ll think of adding it back.
This was already discussed in great detail (greater than such minor thing should be) in the comments to the first and next chapter. And, by the way, Lispworks also allows it (see here: https://github.com/vseloved/rutils/pull/39 - a person even bothered to provide a fix to make it work there). So, get over it: this book is not about nitpicking but about trying to explain things in an intelligible and accessible manner. A luxury I didn't always have with these topics...