Hacker News Reader

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.

I fully agree, having been looking into the same papers. It also doesn't help that each author start out with their own version of the basic implementation which often won't match the implementation the other authors use.

I think I finally managed to get the SPPF to get the right structure now, but it is way harder to penetrate compared to the complexity of the underlying idea.

Now I only have to figure out how to actually iterate over the different parse trees..

It’s easy to throw down the theory and some okay-ish pseudocode while in effect saying, “...and the rest is just a minor implementation detail, which I leave as an exercise to the reader...”

I don’t feel that’s really the case with TAOCP. It’s machine language for a fictional machine, but there exist emulators for the machine. The code is runnable.

The Sedgewick text is quite good but even better are his classes on Coursera! Very accessible and built around practical exercises.

Also on Safari (both the books and the classes)

I found the assignments to his class to be really weird and challenging. The first one had you fill in a few functions of a half-complete percolation simulation, but without having written the other part of it, it felt like having to reverse engineer and guess at the solution. There was no real way to measure your progress. Either it runs or it doesn't, and there's no incremental progression towards a solution.

I'm curious if anyone else experienced this or could point out where I went wrong. I really wanted to do the class and I liked the lectures, but i started it after finishing Gardner's Stanford algorithms Coursera class which had some of my favorite exercises ever. They had you write an algorithm in it's entirety, gave you sample data sets to check against, and let you write it in any language. Compared with that, Sedgwick's assignments were like coding with one hand tied behind my back.

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.

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