Posts tagged algorithms

December 12, 2011

FXAA

Coding Horror’s excellent overview of not only FXAA, but SSAA and MSAA as well.

October 10, 2011

Today’s acronym: SS2PL

SS2PL stands for strong strict two-phase locking; it’s a locking mechanism widely used in database systems today. It is based on the notion of two-phase locking:

  • Expanding phase: locks are acquired and none are released
  • Shrinking phase: locks are released and no new locks are acquired

In addition to the above requirements, SS2PL requires that both read and write locks are held until the transaction that acquired them has commited. Essentially, this means that there isn’t a shrinking phase — only an expanding phase. May I ask why, then, is it called strong strict two-phase locking and not something completely different?

I love computer science acronyms.

October 1, 2011

A few million monkeys randomly recreate Shakespeare

This project comes from one of my favorite Simpsons episodes which has a scene where Mr. Burns brings Homer to his mansion. One of his rooms has a thousand monkeys at a thousand typewriters. One of the monkeys writes a slightly incorrect line from Charles Dickens “It was the best of times, it was blurst of times.”  The joke is a play on the theory that a million monkeys sitting at a million typewriters will eventually produce Shakespeare.  And that is what I did.  I created millions of monkeys on Amazon EC2 (then my home computer) and put them at virtual typewriters (aka Infinite Monkey Theorem).

So far, Jesse’s virtual monkeys and typewriters have randomly created The Tempest, The Winters Tale, The Merchant of Venice and many more. I  recommend bookmarking his post so you can follow the progress. (via Ars Technica)

April 12, 2011

Bubble sort explained as a dance

The AlgoRyhmics YouTube channel has a few more algorithms such as shell sort. [via Neatorama]

May 19, 2010

The SASI algorithm

From the original paper (PDF):

We experimented on a data set of about 66000 Amazon reviews for various books and products. Using a gold standard in which each sentence was tagged by 3 annotators, we obtained precision of 77% and recall of 83.1% for identifying sarcastic sentences.

September 21, 2009

The official Google Webmaster Blog has confirmed that the “keywords” meta tag isn’t used at all in Google’s web search ranking, and has in fact been disregarded for a few years now.