Update: Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms

I posted an entry about a possible errata in Introduction to Algorithms at
Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms

Well, it's a part of the errata of the book now. Check out http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php the errata reads

Page 85, Problem 4-2. Change the second paragraph of the problem to read, ``Show that if the only way to access information in array A is by this single-bit operation, we can still determine the missing integer in O(n) time. Any entire integer outside of A is still accessible in a single operation.''
Reported by Balbir Singh. Posted 29 November 2006.
Severity level: 3
To be corrected in the eighth printing.

Severity level 3 is "A more significant technical or expository error"

I have not yet figured out how the new solution works (with the new constraint), if anybody else thinks of it, please do comment on it here.

Is Dravid headed down the Ganguly lane?

© Getty Images

An indifferent performance at Durban (a place with a good amount of Indian support) and in his last dozen matches, is Dravid headed down the Ganguly lane? Is captaincy and planning leaving no time to play and enjoy the game. Is the politics of Indian cricket along with the six thinking hats of Greg Chappell getting too hot for Rahul?

I for one am very skeptical of the Indian batting line up. Sehwag is too adamant to listen to anyone - that's his natural style right? Tendulkar, the poor guy sees everyone getting out and goes into a shell (and gets out!). Kaif and Yuvraj, have no technique while batting. Give them a venue that supports swing and they'll lollypop their wicket to the slips. Dhoni might be ranked high, but it's a miracle when he manages to play the ball where he intends to.

Let's not even discuss the tail-enders

Whenever India comes in to bat, nobody can predict how well they'll do? They are prone to collapsing, known to be panicky and have the killer instinct of a Sparrow. The one thing they are good at is acting, look at their advertisements and you'll see that all of them can almost act. May be the BCCI has an acting academy inside the sports complex.

Is the wall wearing out? I hope not to give up so soon, but I am very frustrated.
I am going to protest, not by not watching the cricket matches, but by not purchasing anything advertised by an Indian cricketer.


How's that???? (If the umpires are looking at this blog :))

Problem 4.2 Page 85, Introduction to Algorithms

Here's my first post that's actually a PDF article. It contains a lot of math and I thought it would be best to convert it to PDF and then post the link here.

Comments on Problem 4.2, Introduction to Algorithms

Enjoy!

Off to FOSS.IN

It starts today, see you all there!

Man vs Woman (In Pictures)

Hilarious!! My wife sent them to me




WARNING: there were no copyright notice in the email, I hope I am not violating any :-)

Mathematical Formulae

Ever wondered how large the jungle of Mathematics is? We'll I always loose my way in it, when I try to read through a paper. Mathematics, to me is the plain simple truth, that is put in abstract terms. You get reward points for being terse. It's elegant when you write a premise in one single step. I've been thinking about coming up with a list of simple theorems, I want these to serve as an aid for mapping the more inner paths of the Mathematics jungle.

I have been trying to study discrete mathematics for a while now. Here is one of the most important theorems (see The Art of Computer Programming, Volume 1, Page 41, Third Edition, D.E.Knuth) . The theorem is called Fermat's Theorem and states that

If p is a prime number then





For a good proof, see Knuth's book or Fermat's Little Theorem at Wolfram MathWorld

One of the most interesting applications of this theorem is the RSA algorithm. RSA is used quite extensively in public/private key based cryptosystems.

Checkout the RSA article on Wikipedia

Ten top things to do after installing a new Linux Distribution

Even though most of distributions have gotten better with look & feel and integration of hardware with Linux, here are the top ten things I usually do after installing a new distribution

1. Fix the bootloader to set the order of booting the OS
2. Get the right fonts
3. Download media players like real or helix and mplayer
4. Download and install a DVD player
   
5. Install Java and the Java Plugin
6. Install Acrobat Reader
7. Install Acrobat Flash Plugin
8. Install TeX, Scribus, Xfig and Inkscape
9. Install wxMaxima and Scilab
10. Install development packages like Eric, Kdeveloper & Eclipse

Remember, installing an entirely new distribution requires a lot of patience, googling and sleep. I'll try and walk you through the nuances of the various distributions available. My favourite these days is Ubuntu. It's a great distribution built on top of another great distribution (debian).

Symmetry

The book Discover Physics by Benjamin Crowell, talks about symmetry in Physics and in Nature. Wikipedia defines symmetry as

"In formal terms, we say that an object is symmetric with respect to a given mathematical operation, if, when applied to the object, this operation does not change the object or its appearance. Two objects are symmetric to each other with respect to a given group of operations if one is obtained from the other by some of the operations (and vice versa)"

Of the various types of symmetry described in the article, I find the reflection symmetry and rotation symmetry, the easiest to understand.

Reflective Symmetry

Rotation Symmetry

The interesting thing about symmetries is that they apply not only to nature, physics and mathematics, but to computing as well.

Consider that you are writing an API or developing a programming language or a library. By design, you the code needs to be able to undo, what it's allowed to do.

Consider a "C" program

Let's say we carry out the following steps

1. Allocate memory
2. Copy from user
3. Open a file
4. Write to file

What happens in case there is an error in step 4?
We carry out the following steps

1. Close the file
2. Free the allocated memory

We need to do the same when our we are done writing to the file.

Now compare what we did with reflection symmetry. Did you find anything similar? I think we should as a guideline make our API/code symmetric with respect to reflection. In lay man's terms, the code should be able to undo its own effect.

Most programming languages and API are symmetric. "C" has malloc()/free(), open(), close(). "C++" has a constructor and a destructor for each class, so we are mostly good as far as this rule is concerned. "Java" on the other hand, provides a garbage collector to maintain the symmetry. Consider what would happen if you could just allocate memory and never free it up? Open files, but never close them? The system would soon become unstable, the weight would grow on one side (memory, descriptor leaks) and the system would crash.

The symmetry created by the garbage collector makes life easy for the lazy programmer, but losing control over symmetry can throw a system in a non-deterministic state. Consider the case where a system has a lot of memory, the garbage collector never kicks in (of-course a lot depends on the actual algorithm). When a critical application needs to run, it needs most of memory, but to get free memory, the garbage collector starts running, starving the critical application of CPU time, making it wait for its memory demand. All of this could have been avoided (the CPU time overhead), but being in control of symmetry and freeing the memory when not needed.

Coming to rotational symmetry, I am yet to find a good use case for it in computer science (for an average programmer). For those involved in graphical illustrations, we could exploit it to make it easier to draw illustrations.