Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Comparison of Four Algorithms Textbooks (2016)

porgionesanke.wordpress.com

Post reply on HN
Print view View original

41–47 of 47 posts

Re: A Comparison of Four Algorithms Textbooks (2016)

#41

Post by tziki »

Apocryphon wrote: post #27
placebo wrote: post #24

Honestly, I'm blown away that someone has actually read cover to cover Knuth, CLRS, Dasgupta and Skiena. Is this a common thing? Has anyone here done something similar? For years I've had the textbooks of CLRS and Skiena at home (and a pdf of Dasgupta) but they are used only in the event I need to drill down to understand a particular algorithm to solve a particular problem. I feel that the most effective use of my t…

CLRS is the size of a reference manual. Algorithms courses tend to cover material from it, but never the entire book at once. I've always wondered who has the time to read and retain all of CLRS.

I haven't read these particular books but normally I have one "huge" CS book under progress at any time. It's usually a topic I want to know more about and get a basic fundamental understanding of, so mostly driven by the need for knowledge and the feeling that my knowledge is lacking in this area. That said, it usually takes me months to get through with one and often I already know some of the contents which I end up speed reading/skimming.

Re: A Comparison of Four Algorithms Textbooks (2016)

#42

Post by todd8 »

brudgers wrote: post #11
hodgesrm wrote: post #10

Earlier quoted context omitted.

This seems to be a point where reasonable people may differ. I generally go to Knuth when I'm really stuck--not just how to do something but sometimes how to frame the problem so it can be solved. In that sense MIX does not make much difference since it's the discussion and backing mathematics that are most interesting. On the other hand outside of OS and embedded systems people very few people regularly look at asse…

I've got nothing against C. C was not around when Knuth published the first (1968), second (1969), and third (1973) volumes. [1] By inventing a programming language, Knuth was able to avoid syntactic changes between versions (e.g. K&R C looks odd for someone who started with one of the ANSI C's). At the time, 'best practice' might have been Algol 60 or maybe Algol 68 because they were what it meant to be a standard l…

Neither Algol 60 nor Algol 68 were very good choices, but it was basically them or FORTRAN which were used back then in published algorithms.

Algol 60 was the forbearer of most modern programming languages. However, implementations of Algol 60 were all a bit different and even after the the revised report came out a few years later there remained serious ambiguities in the meaning of common Algol 60 constructs, see for example [1]. Other aspects of Algol 60, for example the use of call-by-name argument passing semantics, made it not entirely suitable as a means of communicating algorithms.

Algol 68, had, for many years, essentially no conforming implementations. The language was remarkably orthogonal, every aspect seemed to be fully generalized and usable everywhere in the language, but it was too complicated. At least, it had a concept of I/O, which Algol 60 lacked. Some algorithms were published in Algol 68, but I didn't see many of them.

In this environment, Knuth's books were quite valuable. The algorithms, while not structured or written as we see them now were clear and unambiguous and were written for a time when compilers didn't perform advanced code-optimizations; Knuth's careful designs included optimizations that we would leave to compilers today when talking about algorithms.

Eventually, Pascal came along and it became possible to publish algorithms in an easy to read and unambiguous way. (It was still uncommon to see code formatted in any consistent way. See Wirth's own books!) Pascal wasn't perfect, but it was easy to understand and implementations were portable and widely available.

[1] Knuth, The remaining trouble spots in Algol 60*, https://atlas.cs.virginia.edu/~asb/teaching/cs415-fall05/doc...

Re: A Comparison of Four Algorithms Textbooks (2016)

#43

Post by todd8 »

placebo wrote: post #24

Honestly, I'm blown away that someone has actually read cover to cover Knuth, CLRS, Dasgupta and Skiena. Is this a common thing? Has anyone here done something similar? For years I've had the textbooks of CLRS and Skiena at home (and a pdf of Dasgupta) but they are used only in the event I need to drill down to understand a particular algorithm to solve a particular problem. I feel that the most effective use of my t…

Yes, well, once upon a time in the dark ages, we didn't have HN or even the Internet to spend our time on. At home I didn't have a computer, no one did in the 60's or early 70's. I did have a few books so I read a lot including Knuth and the publications of the ACM that I subscribed to when they arrived in the mail. I wrote my code out on paper when I worked on it at home.

Re: A Comparison of Four Algorithms Textbooks (2016)

#44

Post by mathgeek »

sigjuice wrote: post #32
placebo wrote: post #24

Honestly, I'm blown away that someone has actually read cover to cover Knuth, CLRS, Dasgupta and Skiena. Is this a common thing? Has anyone here done something similar? For years I've had the textbooks of CLRS and Skiena at home (and a pdf of Dasgupta) but they are used only in the event I need to drill down to understand a particular algorithm to solve a particular problem. I feel that the most effective use of my t…

Where does it say that he has read all these books cover to cover?

Generally when someone writes a review this in-depth, this is assumed. Not always accurate, of course.

Re: A Comparison of Four Algorithms Textbooks (2016)

#45

Post by derefr »

hodgesrm wrote: post #10
brudgers wrote: post #4

The criticism of Knuth's use of MIX seems a bit off because: + Assembly language level instruction execution is a good way of talking about the running time of algorithms at a finer level of detail than Big O notation. Finer grain than Big O is helpful when analyzing and optimizing programs. + MIX is a good abstraction of the Von Neumann architecture and that's where the analysis of actual programs occurs. + MIX prog…

This seems to be a point where reasonable people may differ. I generally go to Knuth when I'm really stuck--not just how to do something but sometimes how to frame the problem so it can be solved. In that sense MIX does not make much difference since it's the discussion and backing mathematics that are most interesting. On the other hand outside of OS and embedded systems people very few people regularly look at asse…

> On the other hand outside of OS and embedded systems people very few people regularly look at assembler

Make that OS, embedded systems, and standard platform runtime libraries. The people implementing the algorithms in your programming-language-of-choice's stdlib certainly know what those algorithms are compiling down to. And they're the vast majority of the people who write out algorithm implementations at all, any more.

Re: A Comparison of Four Algorithms Textbooks (2016)

#46

Post by hodgesrm »

josinalvo wrote: post #14
hodgesrm wrote: post #10

Earlier quoted context omitted.

This seems to be a point where reasonable people may differ. I generally go to Knuth when I'm really stuck--not just how to do something but sometimes how to frame the problem so it can be solved. In that sense MIX does not make much difference since it's the discussion and backing mathematics that are most interesting. On the other hand outside of OS and embedded systems people very few people regularly look at asse…

> I generally go to Knuth when I'm really stuck--not just how to do something but sometimes how to frame the problem so it can be solved. If I may ask, what do you work in that requires reading heavy algorithms stuff? (sounds like an interesting job!)

I currently work on disaster recovery and used to do a lot of work on DBMS replication internals. Both fields have problems requiring compact, efficient solutions that work at scale. What I like about Knuth is that he treats algorithms in depth including trade-offs, which are often quite subtle.

For example, you might not think there's much to sequential search but after reading Knuth Vol 3, Section 6.1 it's clear that view is the mark of a greenhorn. ;)

Re: A Comparison of Four Algorithms Textbooks (2016)

#47

Post by josinalvo »

hodgesrm wrote: post #46
josinalvo wrote: post #14

Earlier quoted context omitted.

> I generally go to Knuth when I'm really stuck--not just how to do something but sometimes how to frame the problem so it can be solved. If I may ask, what do you work in that requires reading heavy algorithms stuff? (sounds like an interesting job!)

I currently work on disaster recovery and used to do a lot of work on DBMS replication internals. Both fields have problems requiring compact, efficient solutions that work at scale. What I like about Knuth is that he treats algorithms in depth including trade-offs, which are often quite subtle. For example, you might not think there's much to sequential search but after reading Knuth Vol 3, Section 6.1 it's clear th…

Disaster recovery like recovering servers from crashes/recovering 'lost' databases?
Post reply on HN