HN Books @HNBooksMonth

I wouldn't do it justice[1], it deserves a blog post or a book [2] but in general solving almost any boolean algebra problem, in hundreds, and hundreds of thousands variables, very efficiently and in very compact representation (via ordered sparse bit vectors[3]).

While with Karnaugh maps you can simplify a boolean function with a few variables, BDDs can solve for thousands, fast.

And no need to explain applications of high-dimensional boolean algebra on HN, with boolean algebra you can solve any logic problem expressed as boolean function, any combinatorial problem (except for those with nasty functions), classic graph theory problems.

Surprisingly it allows to solve optimization problems[4], like boolean programming, SAT solver, max independent set or max cut in graphs, very efficiently, it can be used in something like belief propagation or lattice induction for inference, but if that's not enough you can use it for random number generation, lossless compression, perfect hashing, etc, etc.

I haven't seen such a versatile data structure elsewhere, most of the other things developed in the last 35 years, like the ones in the comment below are solving special cases, BDD is truly one of the most fundamental and severely underrated "swiss army knives" (that is in CS, EE people know it very well in logic synthesis and verification, BDD's first "killer app").

It's probably easier to list what you can't do with BDD, kind of like what you can't do with (high-dimensional) boolean logic.

I think it skipped the radar of CompSci community at large because it was too quickly siloed into "that circuit analysis/verification tool used by electrical engineers".

Yes, it's "just" a DAG but with very particular (and very simple) constraints which allow it to solve infinite variety of problems in a very elegant and surprising way [5].

[1] it's really worth watching the lecture on BDDs by Don Knuth , starting around 13:32, his enthusiasm is contagious: https://www.youtube.com/watch?v=SQE21efsf7Y&t=13m32s

Part 2 on ZDD: https://www.youtube.com/watch?v=-HzQYeqS9Wc

[2] TAOCP, volume 4A, Combinatorial Algorithms, p.202 - 280: https://www.amazon.com/Art-Computer-Programming-Combinatoria...

There is a free preprint here https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz

[3] https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagr...

[4] Bergman, David, et al. "Discrete optimization with decision diagrams." INFORMS Journal on Computing 28.1 (2016): 47-66.

[5] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.

I hope that answers your question, dang, and sorry for title mishap.

⬐ jan_Inkepa

Just watching through the Knuth lecture now. 40 minutes in (~54m mark) and I learned something new (to me) and useful and cool (randomly picking maximal independent sets of graphs). And I'm only half way in. Very nice; thanks for the recommendation :)

Vol 4A was published in 2011: https://www.amazon.com/Art-Computer-Programming-Combinatoria...

Vol 4B was partially published in fascicles: https://www.amazon.com/Art-Computer-Programming-Fascicle-Pre... and https://www.amazon.com/Art-Computer-Programming-Fascicle-Sat...

Instead of the ultimate edition of vols 1-3, so far we've got a "patch" by Martin Ruckert who coordinated the volunteers: https://www.amazon.com/MMIX-Supplement-Computer-Programming-...

⬐ hvidgaard

Thanks for the pointers.

This https://cs.stanford.edu/~uno/taocp.html seems up to date.

http://graphics.stanford.edu/~seander/bithacks.html

Entertaining book: http://www.amazon.co.uk/Hackers-Delight-2nd-Edition-ebook/dp...

The reference: http://www.amazon.co.uk/The-Computer-Programming-Vol-Combina... Section 7.1.3 Bitwise Tricks and Techniques

⬐ Sambdala

Thanks!

While we're posting Amazon links,

http://www.amazon.com/Art-Computer-Programming-Combinatorial...

has a fascinating 200+ page section on Boolean and bitwise tricks and techniques (Knuth: "A trick is a clever idea that can be used once, while a technique is a trick that can be used at least twice.").

And the link:

http://www.amazon.com/Art-Computer-Programming-Combinatorial...

⬐ clyfe

And the affiliate marketing:

http://news.ycombinator.com/item?id=2109543

⬐ clyfe

Note that the post was edited in the mean time. Sadly no history a la stackoverflow.com .

⬐ e40

I did not knowingly post an affiliate link.

Of the parts of the URL, which is it?

http: //www.amazon.com/ Art-Computer-Programming-Combinatorial-Information /dp /0201038048/

And, I did not edit the link. Perhaps some admin removed the affiliate part. However, when I go to the page in my browser, it looks just like it does above. Perhaps I followed a link to Amazon earlier in my session and picked up someone's affiliate link.

⬐ xd

Clyfe is pointing out the blatant money spinner by the parent poster .. in case you didn't see that already.

⬐ gcheong

Is there something other than just "bad form" as to why people would not want to go through an affiliate link if the ultimate purchase price for them is the same?

⬐ gjm11

Yes. Doing so makes it more profitable to post worthless affiliate links in places like this, which encourages people to do so, which makes the web a noisier place.

(Note that this is not a justification for avoiding all affiliate links.)

⬐ robryan

Also it's not adding anything, very easy for us to go through to amazon and search for the book. Might be different if the posted recommended a great book that many hadn't heard of before that really added to the discussion, still though it would be better just to keep them off HN.