The Lumber Room

"Consign them to dust and damp by way of preserving them"

Posts Tagged ‘CS

A non-intuitive(?) fact

with 5 comments

This seems counter-intuitive, at least to me, but if you can find an intuitive explanation for it, please comment!

Fact: Let G be a cycle (connected graph where every vertex has degree 2: you know what I mean) of length n (i.e., n vertices and n edges). Start a random walk on G from any node u. Then the probability that v is the last node visited (i.e., the random walk hits all other nodes before hitting v) is the same for every v other than u!

[Such a property is obviously true for the complete graph, and apparently it's true only for cycles and complete graphs.]

I do not know a probabilist’s proof; what I could think of is a distinctly ComputerSciencey (Dynamic Programming / recurrence relation) proof.

Written by S

Fri, 2008-07-25 at 01:54:50 +05:30

Simplexity of songs

leave a comment »

Knuth’s paper The Complexity of Songs
Paper by Broder and Stolfi, Pessimal Algorithms and Simplexity Analysis.

More generally, there is a paper A Stress Analysis of a Strapless Evening Gown which led to an apparently good book of the same name.

Apart from The Worm-Runner’s Digest which was the source of the above, there was Manifold (and a book), source of excellent stuff such as this, there is the Journal of Irreproducible Results, its rival Annals of Improbable Research (which awards the Ig Nobel Prizes), and (found through Wikipedia) Null Hypothesis. Sigh, there is competition in every market.

Written by S

Mon, 2006-12-04 at 07:47:08 +05:30

Posted in funny

Tagged with

Writing for Computer Science

leave a comment »

There is a book with that title. Other good related resources are the links here, and (more general) here. Also, maybe at this course home page.

Written by S

Mon, 2006-11-27 at 13:08:03 +05:30

Posted in Uncategorized

Tagged with

The “Singleton” in “Singleton bound”

leave a comment »

Is a person. Might seem hard to believe, though.
Searching for [R C Singleton "Singleton bound"] throws some references.
Probably Maximum distance q-nary codes is the paper.

Written by S

Thu, 2006-09-21 at 15:16:07 +05:30

Posted in Uncategorized

Tagged with

Follow

Get every new post delivered to your Inbox.

Join 72 other followers