Don Knuth's Take on the Temptress "goto", from 1974

I was reading a thread on Hacker News the other day about a revival of the "gotos are harmful" argument, and someone referred to an article by Don Knuth from 1974 about goto's that I was not familiar with - "Structured Programming with go to Statements". Although it's 40 pages or so, with more than 100 references, much of it is written in an informal style more akin to something you'd read on a blog today, not a technical journal.

Some Visualizations to Help Understand Quicksort

In the last few weeks, I've put together a few visualizations related to Quicksort, and this post collects the links into one place (mainly for me).

Red-Black Trees - Curious Name Origins

This is old news, I guess, but it was new to me.

The colors "red" and "black" were chosen for the red-black tree data structure because of laser printer capabilities at the time, coupled with the taste of the researchers studying it (Leonidas Guibus and R. Sedgewick).

Also Sprach Wikipedia:

A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC which was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that’s why we picked the color red to distinguish red links, the types of links, in three nodes.

Robert Sedgewick, from Coursera, as cited in Wikipedia

And btw, Sedgewick continues his affection for red and black to this day in his classic Algorithms textbook.

The "Music" of the Quicksort Partitioning Step - an Initial Experiment

I have been experimenting with different ways to appreciate the simple but ubiquitous Quicksort algorithm. My first project dealt with visualizing how the "divide-and-conquer" process works, as described here. The one here delves a little into the partitioning process of the algorithm, in an experiment by which the web audio api is used to sound notes/chords at certain times in the partitioning process. It is a work-in-progress, and apparently sounds different on different browsers. Chrome on the desktop works OK, but Chrome on my Nexus 7 plays the C chord with an odd buzz, as does Safari on the desktop.

It is embedded below from this site on googledrive.

"... a user interface..."

Recently, I have been studying sort algorithms, and thinking about how to create effective interactive visualizations for them. So far, I've done a visualization for Quicksort that kind of shows the power of the divide-and-conquer approach of the algorithm, but does not deal with pivot selection strategy, or deal with the in-place nature of production versions. It seems that a lot of the time, the code for these things is overly concise, static (of course), and stalls deeper appreciation. In the case of Quicksort and pivot selection strategy, this attitude seems supported by this email from (eminent) J Bentley as he was coming up to speed on how a (fairly recent) dual pivot strategy worked; in particular,

Exploration of the Quicksort Algorithm

One of my projects this week has been to play with a visualization of the Quicksort algorithm. This algorithm was developed by Sir Charles Antony Richard Hoare in 1960. It is embedded below from this site on googledrive.

Robert Floyd's Tiny and Beautiful Algorithm for Sampling without Replacement

During the big Powerball drawing last week, I put together a simple web app to let you see how long it might take for your numbers to win. While a simple thing, it is surprising to see how long it generally takes to hit the power ball.  At odds of about one in 175 million, playing twice a week, it takes roughly 1,700,000 years to win, on average.  Sure, someone's going to win (and did last week), but I imagine that there were probably at least 175 million tickets sold.

Anyway, for the little javascript web app, I of course needed to be able to simulate drawing the numbers for the lottery, many many times.

This is a remarkably elementary and basic thing to need to do, right? A few lines of code real quick on the way to getting something going. The small irritation is that this is sampling without replacement, so you need to make sure and deal with potential repeats. No big deal, just kind of irritating.

I came across an elegant little algorithm due to late Robert Floyd for choosing a set S of M unique random samples from a population of size N:

    initialize set S to empty
    for J := N-M + 1 to N do
      T := RandInt(1, J)
      if T is not in S then
        insert T in S
      else
        insert J in S

For the case of drawing the first five numbers for the powerball, this reduces to

    initialize set S to empty
    for J := 55 to 59 do
      T := RandInt(1, J)
      if T is not in S then
        insert T in S
      else
        insert J in S

Does this really work? You'll get five different numbers in the right range, but is it statistically equivalent to drawing five numbers without replacement? I saw a proof by induction and some other fairly technical proofs, but I think the basic idea is intuitive.

We will do five draws, and every number has 5 chances to be drawn. However, for some of the draws, the numbers above 55 have more than once chance to be drawn.

Let n_i be the ith number drawn.

• First draw (n₁), a random number between 1 and 55
• Second draw (n₂), a random number between 1 and 56, with 56 having TWO chances to be drawn:
  • if 56 is drawn
  • if n₁ is drawn
• Third draw (n₃), a random number between 1 and 57, with 57 having THREE chances to be drawn:
  • if 57 is drawn
  • if n₁ is drawn
  • if n₂ is drawn
• Fourth draw (n₄), a random number between 1 and 58, with 58 having FOUR chances to be drawn:
  • if 58 is drawn
  • if n₁ is drawn
  • if n₂ is drawn
  • if n₃ is drawn
• Fifth draw (n₅), a random number between 1 and 59, with 59 having FIVE chances to be drawn:
  • if 59 is drawn
  • if n₁ is drawn
  • if n₂ is drawn
  • if n₃ is drawn
  • if n₄ is drawn

So, each number has five chances to be drawn:

• The numbers at or below 55 have a chance to be drawn each of the five draws
• The number 56 has two chances to be drawn on the second draw, and one for each of the three draws thereafter
• The number 57 has three chances to be drawn on the third draw, and one for each of the two draws thereafter
• The number 58 has four chances to be drawn on the fourth draw, and one the last draw
• The number 59 has five chances to be drawn on the fifth and final draw

This is of course trivial to implement, too.

The tiny algorithm seems a wonderful and efficient thing, and I can see why it would be included in a Jon Bentley's Programming Pearls (which I discovered via this post on StackOverflow).

And Robert Floyd was an amazing person.  A child prodigy.  Without a Ph.D., he became chairman of the computer science department at Stanford in the 70's, and significantly influenced the likes of Don Knuth, who in turn had Robert Sedgewick as a doctoral student, who himself is now championing "Algorithms for the Masses" from Princeton via Coursera courses online.

It is cool what one can learn from implementing little projects.