Sunday, February 03, 2008

Bhaskara's proof of the pythagoras's theorem


Bhaskara's Proof

Bhaskara's proof (1114 AD) of the theorem follows from the figure




So simple, elegant and beautiful. I wish I was aware of this proof as a student

Wednesday, January 09, 2008

Favourite Quote for the Day

Loosely speaking we can think of automata, grammar and computability as the study of what can be done by computers in principle, while complexity addresses what can be done in practice.
Peter Linz

Monday, January 07, 2008

Crazy mathematics

As I was shifting my books from one location to another, I found a big heap of books, I had not even started reading or looked at in detail. Being me, I got distracted by them and decided to at-least give them a chance to fulfill their destiny (to be read cover to cover by their owners or the friends of the owners).

I started with Tom Apostol's Mathematical Analysis. It is a wonderfully terse book and I found myself struggling by the time I reached the topic on "Point Set Topology". I had been through a quick journey of the past - real and complex numbers, sets and cardinality, prime numbers and many more things.

I also ran into the famous Cauchy-Schwarz inequality. I remember having proved the inequality in the exercise of Don Knuth's Art of computer programming volume I, but by now I had forgotten it all -- the sum manipulation, the whole of chapter 1 as hiding somewhere in my memory and seeking it was a hard/impossible task. This time, I found myself taking the help of a symbolic computation package - maxima. My dialog was as follows

(%i2) expand((a1^2 + a2^2)*(b1^2 + b2^2));
(%o2) a2^2*b2^2+a1^2*b2^2+a2^2*b1^2+a1^2*b1^2
(%i4) expand((a1b1 + a2b2)^2);
(%o4) a2b2^2+2*a1b1*a2b2+a1b1^2

(%i31) (a1^2 + a2^2)*(b1^2 + b2^2) - ((a1b1 + a2b2)^2);
(%o31) (a2^2+a1^2)*(b2^2+b1^2)-(a2b2+a1b1)^2
(%i32) expand(%);
(%o32) a2^2*b2^2+a1^2*b2^2+a2^2*b1^2+a1^2*b1^2-a2b2^2-2*a1b1*a2b2-a1b1^2

To cut the long output short, I ended up with Lagrange's inequality.

This is just a small part of the mathematics I have to (re)learn, there is also graph theory, game theory, probability theory, Markov chains and theory of computation.

All the mathematics is very exciting, but time consuming. I have loads of other information to read and digest. Let's see where all this I need to learn this crazy math attitude takes me.

Tuesday, January 01, 2008

Have a fantastic new year 2008

It's that time again, a year has gone by, brought happiness and sad moments, but it's gone! Remember to change the year in your dates, make new year resolutions, start afresh, be more positive, thankful and happy that we have a new chance to do/make things right.

HAVE A GREAT NEW YEAR and make every day count

Saturday, December 29, 2007

Rusting Knowledge

Over a period of time, it seems like a layer of dust covers your deep understanding and knowledge of a subject matter, where in once I was considered an expert. My knowledge is rusting and it's time to re-read some old classics and books I used to learn the subject matter from.

I've been trying to learn C#, Python, etc, but I realize that I need to revisit my C skills and my C99 knowledge base again. In summary, knowledge rusts over a period of time, specially the items not practiced very often.

Get ready to clear away the dust from your rusting areas as well, as I explore well known areas and newer areas with a "I used to know, but forgot" perspective.

Monday, December 24, 2007

Digging out of history (longjmp is bad)

I had this program written out a long time back, it shows why some constructs are valid, but do not apply well today. In the evolution of C++, we've left behind some holes


 1 #include <stdio.h>
 2 #include <setjmp.h>
 3 #include <string.h>
 4
 5 class C {
 6 private:
 7         char *ptr;
 8 public:
 9         C (const char *name) {
10                 ptr = new char[strlen(name)+1];
11                 printf("constructed C\n");
12         }
13
14         ~C () {
15                 delete [] ptr;
16                 printf("destroyed C\n");
17         }
18 };
19
20 void funfunction(jmp_buf env)
21 {
22         C c("Hello");
23         /*
24          * Do something, at the end expect destructor to be
25          * called
26          */
27         longjmp(env, 1);
28 }
29
30 int main(void)
31 {
32         jmp_buf env;
33         int ret;
34
35         ret = setjmp(env);
36         if (ret) {
37                 printf("Looks like we jumped a long way\n");
38                 return ret;
39         }
40
41         funfunction(env);
42         return 0;
43 }


See if you can find the obvious problem with this code

Saturday, December 22, 2007

Sounds in my life

The gentle and shrill sounds in my everyday life, call my attention to them. In earlier days, the only sound that one would hear is of people talking to them, children playing on the street or a baby calling for Mama's attention.

Compare and contrast that with what we hear today; the sound of the TV, the microwave, radio, music player, sound of vehicles zooming on the street, vehicles blowing horns, the telephone, the cell phone trying to tell you someone wants to talk to you (even when you are in the restroom), this someone could be a pre-recorded sales call; the computer buzzing to tell you that someone is trying to reach you through instant chat, the courier person ringing the doorbell, the alarm-clock ringing on my cell phone

How am I supposed to listen to myself and others around me; with these distracting sounds calling for my attention. We have moved into a new era, where we need more sounds to tell us, that we are needed elsewhere. I need to filter these sounds, so that I can hear my heart-beat, the pin-drop and my those around me giggle and laugh.

Thursday, November 22, 2007

Guess what OS Don Knuth runs?

Check out http://www-cs-faculty.stanford.edu/~knuth/news.html

In the section "Wanted: A Name For High-Tech Grief" Knuth states and I quote

"I myself have often cried out for help to colleagues who have generously made house calls, in order to unwedge my highly customized Linux system"

We've known it for a while, looking at the customized fvwm2 configuration on Knuth's website, but it's good to see it in writing.

Some of you must be thinking, he has problems with Linux? We'll look at the keywords -- highly customized. Can't do that with other operating systems without hitting yourself in the head a few times or hitting your head against something. You don't hit yourself because your stupid, you do, because you brought the product :-)

Hmmm.... Now, if we can get everyone who has directly or in-directly been benefited from Knuth's work to run Linux, that would be a wonderful starting place. Of-course regular users are more than welcome to adopt and customize Linux.

Linux is a Trademark of Linus Torvalds

Tuesday, November 06, 2007

FOSS.IN delegate registration is open



Register at http://foss.in/2007/register/delegates/

The fee structure has changed this year. Do read the details before registering. This year we have project days and the main conference

Saturday, November 03, 2007

Talk at VTU

I gave a talk on Introduction to Operating Systems via EDUSAT. The lecture was broadcast to several universities via satellite. I had no live audience, but it was fun to speak into a camera. The video has been stored/archived for students to see later.
Here's a link to the slides

New Code in the Linux Kernel

I got some new code included into the mainline linux 2.6.24-rc1 kernel

cgroupstats - Is an infrastructure to allow sending control group statistics to user space using taskstats/genetlink
cpu_acct - CPU accounting subsystem for control groups

Worked on some other miscellaneous stuff as well. Overall, 2.6.24 was an interesting merge cycle, lots of new stuff went it. Check it out! Please do report regressions

A Quick Estimate

I was trying to estimate how long it would take for a timer, measured in nano-seconds using 64 bits would take to roll over. Here's my quick estimate

It would take 2^64/10^9 seconds = 2^64/2^9*5^9

Approximating on all calculations

= 2^55/5^9

5^3 = 125 ~= 2^7
5^9 = 2^21

= 2^55/2^21

= 2^34 seconds

2^34 seconds = 2^34/86500 days ~= 2^34/80*2^10 = 2^24/2^6 days = 2^18 days

1 year = 365 days, 3 years ~= 2^10 days

That leaves us with 2^8 years * 3 years

= 256*3 years before the timer overflows

With a machine, usually one would expect at-least one reboot in 800 years, if so, we would be fine for a long time to come.

See I need no calculator :-)

Saturday, October 27, 2007

FOSS.IN list of talks announced

Check out http://foss.in/2007/shortlist.php

The list of talks looks really good and I know a lot of people presenting at FOSS.IN. I am co-presenting on one topic. I'd say this year FOSS.IN is going to rock, so make sure your there.

Monday, October 08, 2007

India vs Australia (quick analysis)

India won the T20 world cup and became champions! The 50-50 games seem to be a different playing ground for the Indian Team. Have you been wondering why India did not fair so well, so far. Here's a quick layman analysis

  1. India have not been batting first, in all the T20 matches we won, we batted first!
  2. The team has changed and so have the rules. Instead of a powerplay for 20 overs with catch in fielders around, T20 has restrictions for just 4 overs. This makes a big difference to players like Sehwag and Gambhir, who I think are more suited to the field being well spread out (survive longer)

Here's some advice for the Indian Team (given that Dhoni reads cricinfo, you never know if he might read this blog as well :-) )

  1. Convert the 50-50 match to a 20-20 match, by keeping wickets in hand till the 30th over
  2. While batting second, get Dhoni in at #3, followed by Yuvraj at #4
  3. Get Dravid to Open the batting while chasing
  4. Tendulkar should come 4/5 down while chasing (when there is a mandatory ball change)
  5. Don't ever get Yuvraj to Bowl :-)
  6. While bowling first, attack aggressively, even if it means that more runs will be conceded

Friday, October 05, 2007

Memory Ordering (Recommended Reading)

I just finished reading this wonderful report on memory ordering. I highly recommend reading it. If you have anything to do with multi-core, multi-processor, parallel programming, you'll find the paper very insightful.

Other good to read papers/articles on memory ordering from Paul Mckenney are
  1. C++ Data-Dependency Ordering. May 2007.
  2. Overview of Linux-Kernel Reference Counting. January 2007.
  3. A simple and efficient memory model for weakly ordered architectures. Makes case for weakly ordered primitives in programming languages. Updated May 2007.

Wednesday, September 26, 2007

Doing the simple things first

I've always been lost trying to understand and do the complex things. I just realized that I miss out on doing and enjoying the simple things in life. Note to self, remember this and change.

Tuesday, September 25, 2007

India are Twenty20 champs




No one expected it, but secretly hoped for it; and it has happened. India are twenty 20 world cup champions. Boy, has this been a good time for sports. For those of you who do indeed know that hockey is our national game, spare a moment for this picture as well


Spare some time and visit http://www.bharatiyahockey.org/ and http://www.indianhockey.com/.

Now shifting back to twenty20, India beat Pakistan twice and the second win won us the cup. Both matches were close, nail biting (warning: watch your hygiene) finishes. Surprisingly, India got extremely lucky and batted first in almost all their encounters which they won. The statistics show a remarkable quality, that has been missing before, this was a true team effort. Everybody chipped in; in the batting department, we had contributions from Gautham Gambhir, Virendra Sehwag, Robin Uttapa, Yuvraj Singh, M. S. Dhoni, Rohit Sharma (who incidentally is yet to be dismissed in this form of the game). Karthik was a weak spot in the team, but boy did he keep well in the game against South Africa. In the bowling department, R. P. Singh, Irfan Pathan, Harbhajan Singh and Sreesanth were the key contributors.

India's fielding has been quite good, thanks to the absence of Saurav Ganguly, V.V.S. Laxman and Munaf Patel.

I am sure Dhoni is thinking मै तो युहीं चाला था बिना जाने मंज़िल मगर लोग आते गये और कारवाँ बंता गया |

Well done, keep up the good work boys!

Friday, September 07, 2007

Kernel Summit Photos - taken by Evgeniy Polyakov


Peter Zijlstra, Ingo Molnar, Venki Pallipadi and Balbir Singh in discussion

More photos will follow, including the group photo. Meanwhile, there are other photos at Evgeniy Polyakov's gallery.

Thursday, September 06, 2007

Kernel summit day 1 updates

Gerrit has some wonderful updates in his blog Linux and Open Source. LWN.net subscribers can read the summit update at 2007 Kernel Summit article right away or wait for a week for it to be available to public.

Friday, August 31, 2007

Off to VM and Kernel Summit

I've been invited to the VM (Virtual Memory) Summit in Cambridge, U.K. I will also be attending the Kernel Summit which is being held along side LinuxConf Europe 2007. Hopefully, I'll have interesting notes and pictures when I am back.

Algorithms dictionary online

http://www.nist.gov/dads/terms.html is a wonderful dictionary of terms and concepts in Algorithms. It's a wonderful dictionary and the references are excellent. I wish they made the content available as a book or a PDF document.

Monday, August 20, 2007

Perl module for taskstats

Way back last year, we developed the taskstats and delay accounting interface for the Linux Kernel. There is now a CPAN module to extract the same information using perl (all our example programs are in C). It's called Linux::Taskstats::Read. It can read the binary dump of taskstats information and interpret it.

Here's the module

I hope to be able to write a python interface for taskstats as well and do it quickly. I am sure someones already done the work.

Friday, August 17, 2007

Celebrating 50 years of IBM Technical Journals

" Since the first publication of the IBM Journal of Research and Development in 1957 and the IBM Systems Journal in 1962, these Journals have provided descriptions and chronicles of many important advances in information technology and related topics ranging from atoms to business solutions. To celebrate the 50th anniversary of the IBM Journals, this report highlights a selection of significant papers published in the Journals, along with brief commentaries. The Journal editors chose papers which were very highly cited in the technical literature, described technologies of historic significance, or provided an important overview of a field"

Get the articles at 50 Years of IBM Technical Journals

Thursday, August 02, 2007

An LWN.net article about my work

LWN is covering my memory controller work this week. The article is subscriber only, but I've managed to get a free link (legally of-course). Please do view the article, the work and consider subscribing to LWN.net

Here's the article Controlling memory use in containers

Thursday, July 12, 2007

This week from the Wikipedia

I've just discovered my favourite Wikipedia page for this week. It's the page on problem solving. Don't wait, go ahead and read it!

I highly recommend glancing through the external links and reading them later at leisure.

Saturday, June 30, 2007

OLS presentation

I just finished my first OLS presentation on Containers: Challenges with Memory Resource Controller and Its Performance

The presentation went well, it's all been recorded. Hopefully the proceedings will show up soon.

Friday, June 22, 2007

Wednesday, June 20, 2007

M.S. Thesis

M.S.Thesis available

I've finished my M.S. Thesis and you can find it here NOTE: The thesis might still have errors and I do not have any immediate plans of fixing the errors. The thesis was typeset using LaTeX. Hopefully, you'll enjoy reading it.

The figures require some fixing, hopefully, I'll redo them in MetaPost later.

Monday, June 18, 2007

MS (Software Systems)

I received my MS degree from BITS Pilani today. Wow! I am now qualified to do more, I feel so energized. As I am writing this blog, I look at the pile of books of my M.S. curriculum and the dissertation report of the final semester. Flashing in front of my eyes are my last minute attempts to read up a whole book in a week, my stupidity in believing that an open book examination can be passed by carrying along enough books.

Anyhow, that is the past and I learnt a lot from it. As I sit here and examine the past, I know that the process of learning never ends, but learning the same thing is rarely fun (a.k.a repeating your mistakes). But as my copy of Don Knuth's The Art of Computer Programming tells me, I'll never learn anything at once, I'll need to learn somethings during the next reading; I realize that I've just completed a small milestone in a long journey.

Thursday, May 24, 2007

TUGboat archives

I recently rediscovered the TUGboat archives

There is a really interesting article in the 2007 archives
"A beginner's guide to METAPOST for creating high-quality graphics", the article points to a metapost previewer at

http://www.tlhiv.org/cgi-bin/MetaPostPreviewer/index.cgi

Any newbie experimenting with MetaPost should use the previewer, it's fun and easy and of-course one need not worry about the installation details.

Part of the inspiration for looking up TUGboat came from Kevin Larson's article on the Technology of Text. The article is well written, but it completely ignores TeX and METAFONT. That reminds me, time for a letter to the editor.

Thursday, April 19, 2007

Blog in Hindi

अब मै हिन्दी मे भी ब्लोग कर सकता हूँ !

If you cannot see this well, check out

Wikipedia Article on Indic Fonts
and
Blogger help for Hindi

Monday, April 16, 2007

Balbir's Blog: It's prediction time!

Balbir's Blog: It's prediction time!

I am so excited and in pain to see prediction 5 of this years prediction come true! I am curious to see how the others will turn out :-)

Saturday, March 24, 2007

Reserving space for my good bye to the Indian Cricket Masters

Dravid, Ganguly, Tendulkar should go now! Dravid and Tendulkar must go for sure and so should Mr Greg C. Let's see how the Indian team responds to this defeat.

Thursday, March 01, 2007

Balbir's log 1st March 2007

  1. Read a very interesting algorithm called the Ford-Johnson method for sorting. I ended up opening Knuth's Volume 3: Sorting and Searching and reading through his quite amazing illustration and explanation of the method.
    • References - Don Knuth, vol 3, 3rd Edition, Page 184
    • Horowitz and Sahni, Fundamentals of Computer Algorithms
  2. Read through the introduction in the Algorithms book by Papadimitriou, et.al. See my post on a fun way to multiply numbers
  3. Played around with the python programming language after a big break

Follow up: A fun way to multiply numbers

Here's python code to multiply numbers as mentioned in the A fun way to multiply numbers blog entry.

NOTE: I am not a python expert, so there could be some obvious bugs in this simple piece of code. As always use at your own risk.


print "Input the first number"
a=input()
print "Input the next number to be multiplied with %d" %a
b=input()
res=0
while a:
if a & 0x1:
res = res + b
a = a >> 1
b = b << 1

print "The result is %d\n" %res

A fun way to multiply numbers



Reading through the algorithms book by Papadimitriou, et. al has been great fun. I learn a great fun way to multiply (apparently known from ancient times). Let's say we intend to multiply 13 and 23, the procedure is quite straight forward. Write down 13 and 23 besides each other
13 23
6 46
3 92
1 184

The first column is divided by two (with rounding) and the second one is multiplied by two


13 23
6 46
3 92
1 184

Strike out the numbers with even numbers in the first column

Now we just add up the numbers in the right column to obtain 299. That's quite easy right? The really cool thing about this approach is that is easy to implement using computers (hint: left shift and right shift multiply and divide the number by 2 (with rounding taken care of))

Balbir's log - 28th Feb 2007

  1. Freshly installed FC6 - 32 bit edition, still in the process of setting it up (another blog entry). I hope to get KVM and UML running
  2. Played around with Linux's Connector interface (kernel <-> user communication)
  3. Read through chapter 5 (partially) of Computer Systems Performance Evaluation and Prediction

Tuesday, February 27, 2007

Balbir's log - 27 Feb 2007

  1. Played around with Scilab, used scilab for some simple signal processing work, Amplitude Modulation.
  2. I've started reading a paper on VM entitled Making LRU friendly to weak locality workloads
  3. Added Markov chains to my to-learn list

Saturday, February 24, 2007

Using maxima -- baby steps

The use of symbolic computing makes it easy to visualize and solve problems that were otherwise dry and would put you to sleep. To test the simplicity of a freely available tool called maxima, I tried to solve a common problem with it.

The problem is quite simple, remember high school physics? Well I don't :-). Consider a tuning fork, which oscillates and produces a sound (depending on it's frequency).

We start by entering the mathematical model of the fork

'm*diff(x(t), t, 2)=-k*x(t);

Maxima prints


We now request maxima to solve the equation for us by

desolve([%],[x(t)]);

Maxima asks

Is k * m positive, negative, or zero? We say positive

Maxima prints



We ask maxima to simplify the result for us

radcan(%);

Maxima outputs



That's it, we have our solution.

Tuesday, January 30, 2007

What have I been upto?

I've spread myself quite thin, with a lot of code to write, books to read, things to buy and documentation to write.



For now, I have started reading Structure and Interpretation of Computer Programs. I've started reading it, don't skip the foreword or the preface. Be patient with the author and go read it, it's fun!

Meanwhile, I hope to get back to productive coding soon, instead of just reading hundreds and hundreds of papers.

Tuesday, January 23, 2007

One of the hardest problems software faces today

I think the biggest problem is to get users to read the documentation associated with the software.

Try answering these questions and score yourself.

  1. How many times have you seen a question about a problem being repeated?
  2. Why do you they created FAQs?
  3. How many FAQs have you read?
  4. What was the last release notes you read?
  5. Which book did you read last (not related to your course)?
  6. What new techniques did you read and discover in the last two years?
  7. What kind of documentation did you write and share for your last project?
  8. What was the last software manual you read?
  9. What was the ratio of comments to code in
  • Programs you wrote
  • Programs you read


The answers to these questions might not be a simple yes or no, but it will give you a fair idea of how we programmers are lazy and totally ignore documentation.

Sunday, January 14, 2007

Some pictures from our New year and Lohri celebration (A Story!)


Me and my gorgeous wife before we left for the new year party

I sparked off the Lohri celebrations

Popcorn and Peanuts in fire
A Lohri ritual



The flames got higher, lohri had now begun

Ritual walk around the fire

The crowd got bigger as the flames got higher

My brother enjoyed the heat

My in-laws got involved as well
(My brother-in-law, his wife and son)

I had to keep encouraging people

The last round

There was only so much firewood!

It was time for dinner
(The chef was ready!)

Dinner was served, the food was awesome!

My wife's nephew, he came, he saw

He bowed!

Saturday, January 13, 2007

Happy Lohri

Mufli ki khusbu, gurh ki mittaas
Makki ki roti aur sarson ka saag
Dil ki kushi aur apno ka pyar
Mubarak ho apko Lohri ka thyohar!

If the whole thing bounced over you, see http://www.lohrifestival.org/. We are celebrating our first Lohri

Friday, January 12, 2007

Article: A Conversation with John Hennessy and David Patterson

Read A Conversation with John Hennessy and David Patterson published in ACM Queue. It's one of the best articles, I've read lately. They talk about the challenge with parallelism, the free ride software has had, their new book, new projects and much more.

I highly recommend reading the article

Sunday, January 07, 2007

It's prediction time!

It's come a little late this year, but here goes anyway. The list includes technology, business and other predictions for the year 2007

  1. Apple will go back to using the PowerPC
  2. Intel will gain an upper hand over AMD in the 64 bit space
  3. Microsoft (R) Vista (TM) will not be widely accepted, people will expect too much from it
  4. Internet Explorer 7 will do well, but will begin to loose out gradually towards the end of the year
  5. India, Dravid, Chappel and Tendulkar will have a rather forgivable (we'll loose out before the semi-finals) world cup
  6. The world will get ready to move to 128 bit computing, there will be rapid growth towards 1024 bit computing machines
  7. Adobe, Google and Apple will continue to do well
  8. Open source movement will slow down for this year

These predictions are not very scientific, they are based on gut feeling. Feel free to comment on any of the predictions. I'll try and keep the list up to date or add your predictions if I really like them

Monday, January 01, 2007

Have A Great New Year!


Let's all welcome the new year with a big smile! I hope it turns out to be a great year for us, our families and friends, and all of mankind. There are so many things to do, so let's get started!

Thursday, December 28, 2006

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

Monday, December 25, 2006

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 2n 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.

Friday, December 01, 2006

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

Thursday, November 30, 2006

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.

Saturday, November 25, 2006

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!

Monday, November 20, 2006

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 :-)

Monday, November 13, 2006

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

Thursday, November 09, 2006

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).

Tuesday, November 07, 2006

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.

Tuesday, October 24, 2006

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" :)

Monday, September 25, 2006

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.

Friday, August 11, 2006

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!

Friday, July 21, 2006

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.

Sunday, July 16, 2006

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.

Wednesday, July 05, 2006

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.

Monday, July 03, 2006

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.

Sunday, June 18, 2006

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!


Tuesday, June 13, 2006

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

Sunday, June 11, 2006

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.

privacy

Some of the policy from the app automation refers to https://rclone.org/privacy/ if you are a general blog reader, follow Google's polic...