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

11–20 of 47 posts

Re: A Comparison of Four Algorithms Textbooks (2016)

#11

Post by brudgers »

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…

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 language in those days even though implementations varied widely.

[1]: Whether C would have been a reasonable choice the time of the fourth (2011) volume is another matter.

Re: A Comparison of Four Algorithms Textbooks (2016)

#13

Post by mcguire »

wenc wrote: post #7
dsacco wrote: post #2

I’m surprised, but I like this (I typically don’t like or agree with textbook comparisons, but I think this tour is mostly right). The Sedgewick text, Algorithms should be in there too but the author apparently didn’t read that. My own experience basically agrees: I’ve read and enjoy Skiena, it’s written in clear style and it’s the “cover to cover” text for a working developer or for interview practice. But I also ha…

Segdewick is a breezy read (well as breezy as an algorithms text can be). It has somehow never been considered a canonical tome, but I thought it was a decent introductory text.

I was expecting Sedgewick to be in the list---I've never seen Dasgupta---since it's one of the most commonly seen, at least on the cubicle bookshelves I've browsed. It seems as canonical as any.

Re: A Comparison of Four Algorithms Textbooks (2016)

#14

Post by josinalvo »

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…

> 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!)

Re: A Comparison of Four Algorithms Textbooks (2016)

#15

Post by josinalvo »

dsacco wrote: post #2

I’m surprised, but I like this (I typically don’t like or agree with textbook comparisons, but I think this tour is mostly right). The Sedgewick text, Algorithms should be in there too but the author apparently didn’t read that. My own experience basically agrees: I’ve read and enjoy Skiena, it’s written in clear style and it’s the “cover to cover” text for a working developer or for interview practice. But I also ha…

> I’ve certainly used both of them a lot, but I simply haven’t read all of them because I use them more as reference texts.

If I may ask, what is your line of work? If it requires reading heavy algorithms stuff, it is probably an interesting job!

Re: A Comparison of Four Algorithms Textbooks (2016)

#16

Post by mcguire »

dsacco wrote: post #2

I’m surprised, but I like this (I typically don’t like or agree with textbook comparisons, but I think this tour is mostly right). The Sedgewick text, Algorithms should be in there too but the author apparently didn’t read that. My own experience basically agrees: I’ve read and enjoy Skiena, it’s written in clear style and it’s the “cover to cover” text for a working developer or for interview practice. But I also ha…

Oh, dear lord, the algorithm descriptions and pseudocode in research papers...

A while back, I played around with Earley parsing. The Earley parsing algorithm, the basic one, is pretty simple. In fact, it's almost recursive descent, if you didn't use recursion, but managed the current state of the parse manually.

Unfortunately, the original algorithm was described as dynamic programming, which was the hot new thing at the time. Then, there's a bug in it, it's hard to recover a parse tree from it, and it can be extended to be efficient on left-recursive (?) grammars.

Translating the algorithm out of the dynamic programming world isn't too hard. There's a reasonable description of fixing the bug. But recovering a parse tree (technically, a "Shared Packed Parse Forest", since Earley is context-free and to avoid exponential blow-up when producing multiple parse trees, the trees need to share structure) killed me. That paper's pseudocode was the worse spaghetti I've seen in a long time.

Re: A Comparison of Four Algorithms Textbooks (2016)

#17

Post by hackermailman »

Many grad level algorithm courses still use Dexter C. Kozen's book The Design and Analysis of Algorithms, Springer-Verlag, 1992. It's a timeless book with clear analysis.

There's also this excellent free draft on analysis of common undergrad algorithms for parallelism http://www.parallel-algorithms-book.com/

TAOCP is more than an algorithms book, Knuth even have strategies for writing lengthy programs from scratch, how to build test libraries, how to optimize a program to make it cache memory friendly ect.

Re: A Comparison of Four Algorithms Textbooks (2016)

#18

Post by ehudla »

AlexCoventry wrote: post #12

Which book/website has the best exercises for developing algorithmic problem-solving skill? I've started working through Skiena's exercises, but haven't really looked at much else.

I really enjoyed Udi Manber's /Introduction to Algorithms: A Creative Approach/ when I was starting out. It is not the place for sexy new stuff, but it's a great resource for learning the fundamentals and developing a taste for the subject.

Re: A Comparison of Four Algorithms Textbooks (2016)

#20

Post by tmoertel »

ehudla wrote: post #18
AlexCoventry wrote: post #12

Which book/website has the best exercises for developing algorithmic problem-solving skill? I've started working through Skiena's exercises, but haven't really looked at much else.

I really enjoyed Udi Manber's /Introduction to Algorithms: A Creative Approach/ when I was starting out. It is not the place for sexy new stuff, but it's a great resource for learning the fundamentals and developing a taste for the subject.

+1 to this book. Developing algorithms and their correctness proofs together is a powerful technique and ought to be more widely used.
Post reply on HN