Quote of the Day

The creation of standardized, vendor-independent operating systems, such as UNIX and its clone, Linux, lowered the cost and risk of bringing out a new architecture

David Patterson and John Hennessey

A shortcut through time

Written by science writer George Johnson, this book talks about mans quest for the ultimate computing machine, the Quantum Computer.


The books begins with the basic of computing, the language used is quite amusing

"In a typical circuit, there were resistors that, true to their calling, resisted electricity, pinching the flow of electricity"

The book starts off with the authors experience with GENIAC, a mock clone of ENIAC. The author then explains, tinkertoy logic, the book helps the reader discover that computers are more about logic, more than semiconductors that are used to build them. Logic is more important than how it's actually implemented.

The book then dwells into physics, explaining how atoms spin, and how depending on the direction of spin, we can treat the spinning as a boolean quantity as 1, 0 or Φ. Φ represents the state of the atom, when it is spinning in both directions simultaneously.


The introduction to Quantum physics makes a good read and makes me wonder why I slept through Physics in school. Reading further through the book the author aptly states "Human brains are just not equipped to intuitively understand the subatomic rules". The author then takes you to the Aha! Moment, when you realize that the Quantum Computer is so powerful that it can carry out 2ⁿ computations simultaneously, where n is the number of computing bits.

The book then introduces the layman to the Turing Machine and computational complexity, followed by Cellular Automata, Shor's Factoring Algorithm and its application to the world of Quantum Computing. No mathematical proofs are included in the book, but the concepts are well illustrated with examples and supporting diagrams.

Cryptography is then introduced along with the challenge of decrypting code, the computational complexity of cryptanalysis and implications of a quantum computer on current security technology is discussed.

What follows is an elegant description of logic gates and reversible logic. The current and state of the art attempts made at building a quantum computer are described in detail. Quantum error correction, its need and challenges is also discussed.

The book closes with chapters on Quantum secrecy and describes how polarized photons are used to implement quantum cryptography. Real life examples of hard problems, like protein folding is discussed. The reader is introduced to the fact that protein folding is a hard problem to solve (see books on NP-Hard) and the mystery surrounding how nature is able to solve the problem so quickly is discussed.

In summary, this is a great book to read. If you know and understand computer science, it will expose you to how, some of the most complicated concepts can explained without the need for complex mathematics. If you do not understand Quantum computing, the concepts exposed will get you interested in the world of Quantum, where the laws of nature are different. Simple Newtonian physics cannot explain what goes on inside an atom. It is this randomness and uncertainty that can change the way we compute today.

Just my lucky day! (errata in The METAFONTbook)

I got this email as a reply for an errata report I sent out

thanks for your report.

I hope I am emailing the correct people for an errata I found in The MetaFont book Volume C, Page 159

yes. you've come to the right place.

Original Text

For example, Appendix B says

def --- = .. tension infinity.. enddef .

Corrected Text (It should be)

For example, Appendix B says

def --- = .. tension infinity .. enddef;

(Note the change from . to ;)

i've verified this; the reference in appendix b
is on p.262. i don't see any earlier reports on
this, so it looks like you're the first.

should this actually be the case, you will be due
a small reward. to deliver it, we'll need a
postal address. i've received word from knuth
that he expects to be looking at reports about
this time next year, so an address that will be
current at that time is what we'll need.

-- bb

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!