Monthly Archives: December 2008

Fun with ZDDs: Notes from Knuth’s 14th Annual Christmas Tree Lecture

Don Knuth

In this entry, I’ll attempt to record the important ideas Knuth presented in his 14th Annual Christmas Tree Lecture, part of his regular Computer Musings.

While I wasn’t fortunate enough to attend the lecture in person, I did go through the recording that, thankfully, was quite well done. Like all other “musings”, this one included some fascinating anecdotal bits (no pun intended) and Knuth’s good sense of humor was sprinkled throughout; but most noticeable was his infectious enthusiasm for the topics he spoke about. Continue reading

Analytically evaluating a limiting probability (June 2007 Ponder This)

In this post, I’ll describe my solution to June 2007’s Ponder This. I had felt that my solution was kind of nifty, and different from the one that was published. It had actually taken me several days to work the whole thing out.

Here’s part (2), the tougher part, of the problem: Values for a random variable are generated independently and uniformly over \left[0,1\right). By accumulating these values, your job is to reach a sum between n+x and n+1, where n is a positive integer, and 0\,\textless\,x\,\textless\,1. Continue reading

In lieu of a foreword

In this blog, I plan to write about the fascinating/curious stuff that I come across. My plan, for the moment, is to stick to topics I have some familiarity with: CS/math, programming, tools. I’ve a deep interest in certain areas of mathematics and computer science — analysis, combinatorics, probability theory, design & analysis of algorithms, graph theory & network effects, computational problems. Many of my posts would be on these topics. Some would be about EMACS, the one true editor. The remainder would be on programming languages, performance hacks, bitwise tricks… Continue reading