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.

Distracted

Have you ever felt that you don't have the time do what you want to do right away? You feel your holding yourself back, because there are other important things to be done first. Remember time management. Time Management is a emotionless old bloke, who won't let you enjoy your life as a lazy programmer.

Shifting focus across many things, especially when I do not have time to spare is becoming a common habit with me. I am writing this blog entry, when I have absolutely no time to do so :) The interesting part of this obsession to waste all the valuable time is that the moment I actually have time, to do everything I want to; I'll probably end up lazing around and wasting time.

The good thing about the distracted mind is that when I actually get back to doing "what I am supposed to be doing", I feel refreshed. It's like taking a break, a good one.

I have just one more complain. I think life has been extremely unfair on me. During all my exams in school and especially the important ones, there was something interesting going on around the world.

I have some interesting blog entries in draft stage, I hope to post them as soon as I get a little more free from my pressing workload. Who knows, I might decide to get crazy and post them instead of doing "what I am supposed to do" :)

I got here several times

I got to this page several times to write something new, but unfortunately each time I would get distracted by something else. This blog now looks like a toy that a kid grows out of. No, don't worry, I still love blogging and it's something I am passionate about.



While I am here, I might as well tell you that the second edition of the Dragon Book is out. I have admired Al Aho and J D Ullman all my life. I can't wait to get hold of the Indian Edition of the book.

My first Wiki Page

You might think that I have been up to no good these days; not updating my blog recently. I have been caught in a maze of work and studies. While, I did do a lot of things I want to blog about, I'll start by telling you about my first Wiki Page about the Linux ABI

Read it, enjoy it, complain about it, comment on it or update it. You have full control!

Algorithms course and Video

There's an excellent audio and video presentation of the algorithms course at MIT's Open CourseWare. Don't miss the courses in Electrical Engineering and Computer Science and Mathematics

Blog outage and other updates

Blogspot has been unavailable in India since the last few days. I called up Airtel to find out when access to blogspot will be allowed again. I was told that "the site has been indefinitely blocked".

My growing frustration got me to look into Yahoo 360. I was pleasantly surprised with the blogging facility. I could post formatted HTML and it came out very nicely. As an experiment, I have uploaded my first python program. The really cool thing is that with every post, it is also possible to setup a mini-poll and see what people think.

Please visit my Yahoo 360 blog and give feedback. Through the poll and otherwise.

First major contribution to the Linux Kernel

The code is now in linux-2.6.18-rc2 the feature is called per-task delay accounting. It gives me my first set of copyrighted files in the Linux kernel, download -rc2 and open up kernel/taskstats.c, include/linux/taskstats*, Documentation/accounting/getdelays.c

The Documentation/accounting directory has a lot of details on how to use and extend our feature. The review processes was very informative, learning and entertaining.

If you are interested in seeing how the review happened, the process, let me know and I'll post the relevant URL's. In case you are interested in what's happening in the Linux Kernel front, Andrew Morton gave a talk at OSDL Japan, about the new features and their current status.

Learning a new language

I am usually faced with a problem while trying to learn something new, specially if it is a new computer language. The problem is that some basic language concepts and constructs are very obvious. What I am usually interested in is -- to become productive in the new language as quickly as possible and avoid learning things I already know. I have been trying to put together a language learning template. Here's the first draft of it

Phase 1

1. Learn simplest form of I/O (learn how to accept user input and display output)
2. Learn how to write comments
3. Learn about numeric types and numeric operators
4. Learn about strings and arrays
5. Learn the basic constructs of the language like if, while, for
6. Learn about strings and arrays
7. Learn about functions, classes, error handling
8. Learn about simple File operations (open, read and close)

Keep Phase I as simple as possible. Try the simplest of examples to learn the jist of the language.

I am still working on what one could learn in Phase 2. I would appreciate comments, suggestions to make the list complete. Phase 2 is very language specific and its hard to come up with a good list of things to learn. I'll probably pick a language and see if I can follow Phase 1 and come up with a template for Phase 2.

Simple C tidbits (tasty morsels)

I cam across the term tasty morsels in the book Expert C Programming: Deep C Secrets by Peter Van Der Linden. I have been thinking of accumulating them myself, the challenge is to avoid duplicates and keep them interesting

My friend Phani Babu asked me a simple question

"Can we declare static variables in a struct, if no why; if yes where will it be stored?"

My answer was

"We cannot from what I know. struct is a data type declaration keyword, specifying storage might not be acceptable there. But the case for c++ is different where you can have static variables in the class and later on define them outside with the syntax [type]: [class]:[var] [= value]"

The requirements for both languages are clearly different. C being a structured language had no support for methods within a structure or a class. With the addition of classes came the concept of instances of a class. With instances came the need to share data across instances. This could be done using global variables, but it would be ugly. The solution was to allow shared per class data across instances.

Any add-ons will be credited and appreciated.

Finally they seem to be held together

My bookshelf

The latest addition to my geekdom. It is a good well balanced, self contained beauty. Its decorated with my first love, come by and admire it!

Google Earth for Linux

Google earth for Linux is available for download . Beta 4 looks pretty impressive!

Thanks to Riaz for bringing this to my attention

Books I want to buy

The first one is called Performance by Design. It looks like a really useful book for any computer programmer. Its a bit expensive (in terms of Indian currency), but I can't wait to buy and read it.













The second one is called Digital Typography. It explores the relationship between computers and typography. Again, its a bit expensive, but on the top of my buy and read list.

What's new and geeky on the web (30 May 2006)

1. Jeff Ullman has put up new lecture notes on Advanced Compiling Techniques
2. Chirstos Papadimitriou is working on an undergraduate book on Algorithms. Here is the preview
3. Stroustrup has an article on Specifying C++ Concepts
4. Bruce Eckel Interviews Software Luminaries: Thinking in Code
5. Ronald L Rivest has an interesting set of links for cryptography
6. Bruno R Preiss's collection of Data Structures and Algorithm keeps growing (PHP, Ruby, etc)
7. Ulrich Drepper has an article on SELinux Memory Protection Tests
8. Greg Kroah-Hartman has announced a new Linux Device Driver Kit
9. Scilab has announced version 4.0