The Top 10 Algorithms

I am teaching a senior undergrad seminar (for Scientific Computing majors) in the Fall semester, and thought it would be a good idea to pick some kind of a theme.

After some thought, I figured that "famous algorithms" may be a good idea. I tried to google "top algorithms" and came up with many lists. Let me begin for bad lists (in my opinion) to good ones.

A.  George Dvorsky has a list of "the 10 algorithms that dominate the world"

1. Google Search
2. Facebook's News Feed
3. OKCupid Date Matching
4. NSA Data Collection, Interpretation, and Encryption
5. "You May Also Enjoy..."
6. Google AdWords
7. High Frequency Stock Trading
8. MP3 Compression
9. IBM's CRUSH
10. Auto-Tune

While the list is interesting, it is somewhat disappointing. It conflates software products with actual algorithms.

HFT is not an algorithm; although the words algorithmic trading and HFT are often used synonymously. Sure, there are important algorithms lurking under many of these "products"

B. Marcos Otero has a better list of "the real 10 algorithms that dominate the world"

This list is a reaction to the one above. The author prefaces his comments with:

Now if you have studied algorithms the first thing that could come to your mind while reading the article is “Does the author know what an algorithm is?” or maybe “Facebook news feed is an algorithm?” because if Facebook news feed is an algorithm then you could eventually classify almost everything as an algorithm.

1. Merge Sort, Quick Sort and Heap Sort
2. Fourier Transform and Fast Fourier Transform
3. Dijkstra’s algorithm
4. RSA algorithm
5. Secure Hash Algorithm
6. Integer factorization
7. Link Analysis
8. Proportional Integral Derivative Algorithm
9. Data compression algorithms
10. Random Number Generation

While this is a better list, in the sense the the items listed are usually "real" algorithms, or something close, it has a strong computer science bias. For example, #4, #5, and #6 are all algorithms for encryption. While encryption is clearly important, it is probably not 30% by weight of the most important algorithms.

C. SIAM has its own list (pdf) of the "top 10 algorithms of the 20th century"

I like this more comprehensive list the best (although I still have some reservations), because the forest in which they hunt is the biggest. Also, the list is a collaboration of two people, which provides some balance on the topics that are touched.

1. Monte Carlo Method
2. Simplex Method for Linear Programming
3. Krylov Subspace Iteration Methods
4. Decompositional Approach to Matrix Computations
5. Fortran Optimizing Compiler
6. QR Algorithm
7. QuickSort
8. FFT
9. Integer Relation Detection Algorithm
10. Fast Multipole Method

Intelligence Squared Debate on Nature of Death

I'm a regular listener of the Intelligence Squared podcast, and its American counterpart, Intelligence Squared US. The podcast is heavily edited, so sometimes it is worthwhile to look up the unabridged video version of the debate on their website.

Recently, they debated the proposition: "Death is Not Final". On the against team (arguing that death is final) were Sean Carroll, and Steven Novella. You can find the full video on YouTube here.

I was against the proposition to begin with, and ended on the same side, with a stronger level of conviction. Here is Carroll's take on the debate, and here is Steve Novella's.

Overall, the debate was somewhat one-sided (that is my bias speaking, perhaps), and the against side articulated their case much more clearly.

There were two salient light-hearted moments.

When Dr. Alexander confronted Dr. Carroll with the potential link between consciousness and quantum mechanics, and the attraction of some of the fathers of quantum mechanics with mysticism, Dr. Carroll quoted Scott Aronson:

“Quantum mechanics is confusing and consciousness is confusing, so maybe they’re the same.” 

The other moment was when Dr. Alexander suggested that Carl Sagan thought that the evidence for reincarnation was overwhelming, and even asked him to look up page 302 of Sagan's book "Demon Haunted World".

Within seconds, the Twitter world exploded.

The skeptical community, when stripped of its predominantly atheistic clothes, treats Carl Sagan as God.

Here's Steve Novella's response on his blog:

Alexander specifically referenced Demon Haunted World page 302. The relevant section has already been posted by many others, including in the comments here, but here it is: 

“Perhaps one percent of the time, someone who has an idea that smells, feels, and looks indistinguishable from the usual run of pseudoscience will turn out to be right. Maybe some undiscovered reptile left over from the Cretaceous period will indeed be found in Loch Ness or the Congo Republic; or we will find artifacts of an advanced, non-human species elsewhere in the Solar System. At the time of writing there are three claims in the ESP field which, in my opinion, deserve serious study: 

(1) that by thought alone humans can (barely) affect random number generators in computers;
(2) that young children sometimes report the details of a previous life, which upon checking turn out to be accurate and which they could not have known about in any other way than reincarnation;
(3) that people under mild sensory deprivation can receive thoughts or images “projected” at them. 

I pick these claims not because I think they’re likely to be valid (I don’t), but as examples of contentions that might be true. The last three have at least some, although still dubious, experimental support. Of course, I could be wrong.” 

To put this in context, Sagan is arguing that we have to be open to even unlikely possibilities, and sometimes it is not unreasonable to gamble on low-probability ideas. I tend to agree, within the limits of practicality and resources. But if someone wants to spend their time researching very unlikely ideas, more power to them. Just expect to be held to a very high standard of scientific rigor. 

In the full quote Sagan clearly states that he does not think these propositions are likely to be valid, and the evidence so far for them is “dubious.” But – further research might be interesting. That’s pretty thin gruel on which Alexander is hanging his hat.

Rainbows are beautiful!

After seeing this lecture, I will never see a rainbow with the same eyes:

Pink is for Boys, Blue is for Girls

I was listening to a weekly podcast of the "The Reality Check" by the Ottawa Skeptics, and they had this piece about the history of "pink for girls and blue for boys".

This assignment of colors, which is rather arbitrary, is particularly strong in the United States. Quite interestingly, the associated history is quite fascinating as discussed in the show (and this article at the Smithsonian Magazine).

Apparently before 1900, white was the color of choice for kids of both sexes almost until first World War - partly because colored clothes were more expensive, and partly because whites could be bleached clean (and partly because of social norms).

Here's where things get interesting.

For example, a June 1918 article from the trade publication Earnshaw's Infants' Department said, “The generally accepted rule is pink for the boys, and blue for the girls. The reason is that pink, being a more decided and stronger color, is more suitable for the boy, while blue, which is more delicate and dainty, is prettier for the girl.” Other sources said blue was flattering for blonds, pink for brunettes; or blue was for blue-eyed babies, pink for brown-eyed babies, according to Paoletti. 

In 1927, Time magazine printed a chart showing sex-appropriate colors for girls and boys according to leading U.S. stores. In Boston, Filene’s told parents to dress boys in pink. So did Best & Co. in New York City, Halle’s in Cleveland and Marshall Field in Chicago.

It wasn't until much later that the current practice became the norm. Neither the article nor the show delves into the factors responsible for the reversal. Given how hard it is to change arbitrary norms/formats (QWERTY keyboard, driving on the left/right side) that have gained some currency, this is definitely something interesting.

Deresiewicz on "Scientism"

Deresiewicz laments the notion that "science is the only valid form of knowledge".

[editors] want numbers; studies, sociology. Aristotle, Montaigne, and Emerson are not valid authorities on the topic, say, of friendship, but a study of 50 college students is enough to convince an editor of anything.

There definitely is something that rings true in his argument.

However, I find the example of equating experience and data as equally valid means to arrive at the conclusion "city life is stressful" somewhat problematic.

For example, many people feel that violent crime has increased, while "scientific" data seem to show otherwise (see this TED talk by Steve Pinker on his book on the topic).

When experience and data diverge, data - trust the data!

A Twist in the Prisoner's Dilemma

Prisoner's dilemma is a famous model in game theory, which in a basic form can be asserted as:

Two men are arrested, but the police do not possess enough information for a conviction. Following the separation of the two men, the police offer both a similar deal—if one testifies against his partner (defects/betrays), and the other remains silent (cooperates/assists), the betrayer goes free and the one that remains silent receives the full one-year sentence. If both remain silent, both are sentenced to only one month in jail for a minor charge. If each 'rats out' the other, each receives a three-month sentence. Each prisoner must choose either to betray or remain silent; the decision of each is kept quiet. What should they do?

Despite its apparent simplicity, it is used as a model in places you probably wouldn't imagine it to be.

The solution to this one-off game is quite simple (if depressing). You should not cooperate.

A more interesting version is the iterated prisoners dilemma, where the game is played over and over again. For the longest time (since I took a course in game theory about 10 years ago), it was always assumed that, empirically, a simple strategy like "tit-for-tat" offered a decent balance between simplicity and effectiveness.

Turns out that there is a new twist in the plot.

William Press (of Numerical Recipes fame) and Freeman Dyson ("the") recently published a paper in PNAS (open access) that seems to be getting a lot of attention.

There is a nice commentary (pdf) that is easy to follow for those of us, who have an undergrad-level understanding of the problem.

Paper or Plastic?

I have often seriously thought of looking for the "correct" answer to the ubiquitous "paper or plastic?" question that greets so many of us at the end of each grocery trip.

As I've always suspected, it is a trick question: the correct answer is this:

for sale at richarddawkins.net

A little bit of surfing brought up these two links and some startling facts therein. MSNBC also has a decent interactive presentation.

If you have to choose however, my take is that - other than biodegradability - plastic trumps paper.  Biodegradability is certainly important, but perhaps there is some hope.

To make those innocuous paper bags it takes:

• 4x more energy
• 20x more fresh water
• far more toxic chemicals that cause greater air and water pollution

In addition, they aren't recycled significantly more.

MacAttack!

You've probably heard of the recent Flashback infections on Apple Macintoshes. It makes you see the old Mac v/s PC video in new light.

There's an interesting back of the envelope calculation which predicts the market-share "f" at which writing malware for Macs would become "profitable". If you assume that the non-Mac world is all PC, and that the success-rate of an attach is "s" (due to anti-virus protection), then you end up with, f = (1-f)s as the attackers utility equation, which yields f = s/(1+s). Plug in "s=0.2", which is a typical success rate, you get f = 0.16, compared to the current 11% market-share.

Nothing is unbreakable! Not Oracle, not Macs, not Linux!

More Physics Envy

On the heels of a recent related link, comes this talk, in which Andrew Lo deliberates on what physics envy may have done to the dismal science (H/T Farnam Street). From the video:

In physics it takes 3 laws to explain 99% of the data. In finance it takes more than 99 laws to explain about 3%.

Interesting video, especially for those with some knowledge of both fields. Also check out the link (from the Farnam Street blog) to a paper (PDF) by the same title. 

Feynman and Why

As a father of a curious three-year old, I know how hard it is to answer "why" questions, beyond a certain point. Just recently, I had the following conversation with my daughter.

Her: "Why is the cow eating with her mouth?"
Me: "Because she does not have any hands."
Her: "Why does the cow not have hands?"
Me: "Hmmm. Because God did not give her hands." (I shamelessly invoke God all the time)
Her: "Why did God not give her hands?"
Me: "I don't know. Go ask God!"

I bumped into the following Feynman video, in which an interviewer asks him "why do magnets attract/repel each other?" Feynman goes on about how difficult it is to answer such why questions without a framework.

Worth a watch!

Gary Taubes: Why we get fat

In this YouTube video, Gary Taubes of the "Why we get fat" fame, delivers a hour and half long lecture on Google's campus. Somewhere in the first five minutes, Gary Taubes says that this talk is a Cliff Notes version of the book (which apparently is a Cliff Notes version of his more fully fleshed book "Good Calories, Bad Calories").

As if all this was not enough, here's a Cliff Notes version of the talk:

Taubes compiles historical data, and argues that casting fat/weight reduction into a "Eat less, Exercise more" regimen, misses the point. I like the example, where he says that, that is exactly what you would do, if you had to work up an appetite. The primary claims of Taubes' critics seems to be that (i) he edits conversations with experts (many of his interviewees seem to have "recanted"), and (ii) he commits a crime of omission by not engaging the large body of research which contradicts his claims.

Essentially he upsets the implied causal connection between weight loss and negative energy balance, as implied by "accumulation = input - output", by suggesting that the "=" does not tell us what causes what.

The culprit is apparently insulin, which is released when carbohydrates are consumed. Insulin encourages fat cells to store fat. Mice that are injected with insulin, and then underfed, tend to become obese. The message is therefore to avoid carbohydrates, and actually consume fat (like Atkins diet).

It is a compelling point of view, but apparently still quite controversial. Here is a story countering Taubes' initial article in NYT. Here is Taubes' response. Here is the response to the response.

Polygonal kitchen sinks

I heard about this study in Nature (subscription required) in a recent talk. See some pictures here.

When a water jet strikes a flat surface at high Reynolds number, it normally creates a circular hydraulic jump. In the paper linked above, Ellegaard et al. demonstrate that stationary polygonal patterns can be formed (instead of circles) when high viscosity fluids are used.

Fascinating.

Least Squared or Absolute Errors

It is almost impossible to escape linear regression: the act of fitting straight lines through scattered data.

The question of whether it is more appropriate to use minimization of squared or absolute error to determine the straight line, popped up yet again in a recent reviewer comment.

It feels "natural" to use least-squared error, since we have all done it so many times. However, it should be borne in mind that the popularity of this criterion usually arises from the convenience it affords, and not because it lays any special claim to uncovering the truth.

Here is a nice post (+comments), which explores the issue more fully. To nudge you to check out the post, here is a fascinating picture.

Can most people be above average?

Can there be truth to the Lake Wobegon "effect": "where all the children are above average"?

The short (and correct) answer is no.

But could there be a town where "the number of above-average children, exceeds the number of below-average children"?

Quite certainly possible!

Without trying to sound like a lawyer, it all hinges on the definition of the word "average". There are at least three commonly used measures of the average or "central tendency" of a bunch of data.

The mean, median, and the mode.

The "mean" is the "average" you are used to, where you add up all the numbers and then divide by the number of data points. When you see somebody's batting average, you are considering the mean:

total number of runs/total number of "outs"

It is quite possible that the number of data-points greater than the mean is larger than half (and vice versa). A common, but interesting example, is the fact that most US mutual funds (70%) under-perform the average benchmark (or passive index funds).

The "median" is the "middle" value in the list of numbers.

To find the median, you sort your numbers in ascending (or descending) order, and make a list. You then pick the guy in the middle of the list. A common example of this measure are "median incomes", which is really a fancy way of saying that you make everybody from Bill Gates to the poorest person on earth stand in order, in one straight line. The income of the guy at the center of the line is the median income.

Thus, if by average you mean median (no pun intended), then there are exactly as many people above average, as they are below it.

Ergo, no Lake Woebegone effect.

The "mode" is the value that occurs most often. If no number is repeated, then there is no mode for the list. It is also non-unique. There can be two or more modes. Again, you can easily have more values above the mode, than below it.

In summary, if average is defined as the mean or the mode, then the "weak form" of the Lake Wobegon Effect can certainly be true.

The Poincare' Conjecture

I spent an entire Sunday afternoon reading up on the Poincare' conjecture, thanks to this link from Abi, and a few "heads up"s from friends on Facebook.

One thing led to the other, I stumbled upon this New Yorker article called "Manifold Destiny", by Sylvia Nasser (of A Beautiful Mind fame) and David Gruber. If you like stories of big egos, monumental leaps in science doused with a certain tabloid appeal, this is an amazing read.

I thoroughly enjoyed it.

Can a human being outrun a horse?

Apparently over long distances.

I was listening to Ira Flatow on NPR, in my car today. Since the New York marathon is tomorrow he was talking about it, and one of his guests claimed that when it comes to long distances, human beings can essentially outrun all other animals - including horses.

Since I heard only that snippet (I reached my destination), and I had a few minutes, I googled, and no kidding! Here is a fascinating NYT link on the topic.

Some interesting numbers.

The fastest marathon was run just under 2:04 hours by Haile Gebrselassie of Ethiopia which translates to an average speed of 12.67 mph, or 4:44 minutes per mile. A horse can gallop at about 25-30 mph over short distances, but like I said before, they often underperform humans in marathons.

Over short distances, Usain Bolt of Jamaica ran a 9:58 at the 100m dash, which translates to 23.35 mph, or 2.57 minutes per mile, while a cheetah can go at a top speed of 60mph, which is about three times as fast.

We clearly weren't built to outrun such predators.

So what tilts the balance in our favor as distance increases? Apparently it has all to do with cooling.

When a horse gallops, it produces heat at a rate greater than what it can easily dissipate. Humans are much better at dissipating energy.

A simple energy balance tells us that if the input is greater than the output, there is accumulation of heat which leads to a rise in temperature - which is clearly undesirable. The evidence for this hypothesis is the fact that humans have a much better chance of beating animals in marathons when it is hot, sunny, and humid - conditions that make heat dissipation even harder for the poor animals.

Differences between boy and girl (kid) brains?

Just read this article via this blog.

In one [study], scientists dressed newborns in gender-neutral clothes and misled adults about their sex. The adults described the "boys" (actually girls) as angry or distressed more often than did adults who thought they were observing girls, and described the "girls" (actually boys) as happy and socially engaged more than adults who knew the babies were boys. Dozens of such disguised-gender experiments have shown that adults perceive baby boys and girls differently, seeing identical behavior through a gender-tinted lens.

I always suspected that the "men are from mars and women are from venus" line, as closer to astrology than to science. Evidently

assertions of innate sex differences in the brain are either "blatantly false," "cherry-picked from single studies," or "extrapolated from rodent research" without being confirmed in people. For instance, the idea that the band of fibers connecting the right and left brain is larger in women, supposedly supporting their more "holistic" thinking, is based on a single 1982 study of only 14 brains. Other baseless claims: that women are hard-wired to read faces and tone of voice, to defuse conflict, and to form deep friendships; and that "girls' brains are wired for communication and boys' for aggression." Eliot's inescapable conclusion: there is "little solid evidence of sex differences in children's brains."

Of course the larger picture that the article and the book suggests is that small differences in treatment accumulate to measurable differences eventually.

Children and Languages

Okay, I have a kid, and I grew up in a *really* multilingual environment, which makes this AP story interesting. As a kid myself, I grew up in a language soup of Marathi, Hindi, English, Konkani, and Kannada, and as an adult in Fortran, Octave, and C++.

For those, who hate to read here are some interesting tidbits:

Kuhl offers an example: Japanese doesn't distinguish between the "L" and "R" sounds of English — "rake" and "lake" would sound the same. Her team proved that a 7-month-old in Tokyo and a 7-month-old in Seattle respond equally well to those different sounds. But by 11 months, the Japanese infant had lost a lot of that ability.

and

It's remarkable that babies being raised bilingual — by simply speaking to them in two languages — can learn both in the time it takes most babies to learn one. On average, monolingual and bilingual babies start talking around age 1 and can say about 50 words by 18 months.

I haven't looked at the original research yet, and know the perils of ordinary journalists reporting on science stories, largely because the article (unlike well-written technical documents) does not properly link the sources.

Does cooking in a microwave oven destroy nutrients in food?

Microwaves are electromagnetic waves with a wavelength of around 12.24 cm, which puts them between radio and infra-red waves. You are constantly immersed in radio waves, and infra-red is less energetic than the sunlight that you bathe in everyday. So don't let the word radiation scare you. Not all of it is bad, and a lot of it is natural.

So, a microwave doesn't blast your food, trying to ionize it. It does something smarter. It excites polar bonds like those present in water, and selectively feeds them energy. This energy is released as heat, which is then spread around.

Okay. Okay. Tell me if it is good or bad.

I am so glad you asked.

The quick answer is "it is not bad".

You have to realize that cooking per se robs food of its nutrients. So whether you boil, steam, grill or microwave food, its never going to be as good as it is when it is raw. Once you've decided, you want to cook, the answer sort of depends on what you are cooking.

A 2003 study on broccoli in the Journal of the Science of Food and Agriculture by Garcia-Viguera et al. concluded that microwave cooking lost the highest percentage of flavonoid antioxidants, about 97%. Pressure cooked and boiled broccoli lost 47% and 66%, respectively. With potatoes and tomatoes, the story turned upside down. Microwaving lost 45-65% of the nurtients, while boiling on a stove lost 60-80% of the flavonoids.

As a website with a harvard.edu suffix says:

So, as a general proposition, cooking with a microwave probably does a better job of preserving the nutrient content of foods because the cooking times are shorter.

As far as vegetables go, it’s cooking them in water that robs them of some of their nutritional value because the nutrients leach out into the cooking water. For example, boiled broccoli loses glucosinolate, the sulfur-containing compound that may give the vegetable its cancer-fighting properties as well as the taste that many find distinctive and some, disgusting.

Here, I have only touched upon the loss of nutrition. Some of the fears may be justified, since some of the first microwavable food leaked carcinogens like benzene, and I have heard of diacetyl leaching out of microwave popcorn. I'll probably look at that separately.

So what is the moral of the story:

1. Raw is best!
2. If that is not possible, minimize cooking time.
3. Use as little water as possible in a microwave-safe container.
4. Use the nutrient-rich water from boiled or microwaves vegetables

Why should we use warm water (and soap) to wash dishes?

Does the warm water kill bacteria?
Nope. Unless by warm you mean boiling.

To mindlessly massacre bugs clinging on to your cutlery, you should rely on a good quality anti-microbial soap. Not temperature (below 100 celcius).

If I asked the question slightly differently, then perhaps, the answer would be self-evident. So let me pose it again. "Why should we use warm water to rinse dishes?"

Soap or detergent is a surfactant. A bunch of these surfactant molecules aggregate and surround grime and dirt particles, in interesting structures called micelles. The process is well-understood.

Where warm water comes in, is after all the action between soap and grime has transpired. These micelles I was talking about still reside on the dishes, and we need to rinse them off. Like sugar or salt or most other things, these micelles are also more soluble in warm, rather than cold, water. Hence the "warmth" only helps rinse efficiently.

Is this important?

You bet. Because if you can't rinse off dirt from the plates then it remains on the unclean dry plate, right?

PS: By the way, you could substitute "dishes" in the title with "human body" or any other wild-card.