DeeKaying - Geekiness @ IIT Roorkee

Blogs mature over time

2012-01-07T13:15:00.002+05:30

It's interesting to look at how my blog has grown over the years. It shows how lopsided the internet is in terms of traffic. The data speaks for itself:

Recurrences in Computational Complexity

2011-12-11T14:01:00.001+05:30

Manish Sharma asked me an interesting question over chat regarding recurrences and computational complexity estimation. The question was interesting enough that I thought that the answer would be of use to many more people in general so I'm posting it to my blog. In any case, a post to my blog was long overdue. So, here it is:

The original question was:

How do you find the computational complexity of the recurrence:

T(n) = a.T(n . r) + b.T(n (1 - r)) + O(n)
or, when pretty printed:

Well, technically speaking, this question is phrased slightly ambiguously, so I'm phrasing it as below:
T(n) = a T(n r) + b T(n (1-r)) + cn + d
a > 0, b > 0, c > 0, d belonging to R

Pretty print:

and while I'm at it, I'll point out to you that without loss of generality, I can impose the additional restriction that r is in the range of 0.5 to 1.0.
Pretty print:

This is possible because I can simply take a recurrence equation where this isn't true and transform it to a recurrence where this is true by swapping the values of a and b and replacing the value of r with (1-r).

Given that the restrictions that I've imposed onto the original recurrence are valid, here are a few observations:

T(n) is atleast linear. This is because it already contains a cn term in the recurrence.
r > (1-r) in all cases given the valid range of r. A corollary of this fact is that n r > n (1- r) is always valid.
Since T(n) is atleast linear (and positive for n > 1 with a positive first derivative - which are the standard assumptions in such a problem), T(n r) > T(n (1 - r))

Now comes the tough part:

Case 1: T(n) is linear.

Assume T(n) = A n + B with A > 0
Therefore,
T(n) = a T(nr) + b T(n(1-r)) + cn + d = a { A nr + B } + b { A n(1-r) + B} + cn = {Aar + Ab(1-r) + c} n + {aB + bB + d}

Equating parts of the equation:
Aar + Ab(1-r) + c = A
aB + bB + d = B

Simplifying,
A = c/(1 - ar - b(1-r))
B = d/(1 - (a+b))

To satisfy our original assumption, A > 0 - we require that 1 - ar - b(1-r) > 0. That means, if ar + b(1-r) < 1 then T(n) is linear. This, of course, need not be true for all valid values of a and b, so for those values, our linearity assumption is violated.

Case 2: T(n) is superlinear.

If T(n) is a superlinear increasing function of n, then for sufficiently large values of n,
there are 3 subcases:

a T(nr) > b T(n(1-r)) for n > K1
a T(nr) = b T(n(1-r)) for all n > K2
a T(nr) < b T(n(1-r)) for n > K3

Subcase 1: a T(nr) > b T(n(1-r)) when n -> infinity then

T(n) < 2a T(nr) + cn + d

If 2a < 1 then the solution is O(n) - valid?
If 2a = 1 then the solution is O(n log n)
else the solution is O(n ^ log_(1/r)(2a))

Subcase 2: aT(nr) = b T(n(1-r)) for all n then

T(n) = 2a T(nr) + cn + d

If 2a < 1 then the solution is again O(n) (tight bound) - valid?
If 2a = 1 then the solution is again O(n log n) (tight bound)
else the solution is O(n^log_(1/r)(2a)) (tight bound)

Subcase 3: a T(nr) < b T(n(1-r)) then

the solutions are similar to subcase 1 except that r is replaced by 1-r and a is replaced by b.

Special case: When a = (1-r) and b = r.

The complexity should be O(n) under limit.

Note: Case 2 seems sufficient to solve the problem but I've kept Case 1 for clarity. I think there might be bugs in the analysis too. If you notice any, please comment!

The Case Against GM Foods: Putting our food security at the hands of an American Corporation

2011-08-04T00:50:00.007+05:30

I've always looked at Genetically Modified foods with a wary eye. Also, the fact that the US GM seed market is dominated by a single company - Monsanto - makes me even more suspicious (the obligatory Wiki Link - http://en.wikipedia.org/wiki/Monsanto). It is well known that Monsanto spends tons of money lobbying the US Food and Drug Administration (US-FDA) to ensure legal status for GM foods and to guide American legislation such that GM foods remain legal and no adverse regulatory laws are passed against GM foods.

Source: http://www.panacea-bocaf.org

Nowadays, every supermarket I've been to in the US keeps GM foods next to non-GM foods. There are no clear label markings mandated by law that would allow a consumer to distinguish between GM and non-GM foods at a glance. Consumers are forced to read fine print on labels to determine if GM products have been used in the food chain of the product they're buying. Then too, things are hampered by the fact that there is no clear way to determine if a long chemical-sounding-name is a natural, nature-identical or artificially created ingredient. Things have gotten so bad that while I was in the US, I heard of a case where a company using the term - "no GM foods used for feeding chicken" for marketing purposes was sued and asked to include a disclaimer that GM foods have not been proven to cause any harm whatsoever and that GM foods are safe for use. Extreme measures like these make me much more distrustful of companies promoting GM foods.

By the way, here's a chart from Wikipedia that show's Monsanto's astronomical profits.

Source: http://en.wikipedia.org/wiki/File:Monsanto_stock_price_2000-2010.jpg

These profits are generated year after year and are only growing as acres and acres of farmland come under GM crop cultivation. GM crops typically are modified so that they are not self-replicating due to concerns about wild, unchecked replication. Though introduced for the right reasons, this constraint has set up a monopolistic market, one that cannot be shut down very easily. The fault lies in the fact that since the crops cannot be propagated season after season from the seeds, the farmer needs to approach the company holding the patents to the GM crops every single year in order to plant his crop. Also, since the seeds are patented (and the Intellectual property is vigorously defended by lawsuits) and there is a very very long approval process for GM foods, there is huge bar for companies that intend to enter this space and the incumbent - Monsanto - enjoys a virtual monopoly in this space. Not only is this disruptive to the natural cycle of (free) seed generation used by farmers, in the Indian context, it is tantamount to handing the base of our agricultural pyramid to an American company (Monsanto controls 90% of the GM seed market in America).

Image courtesy: http://www.planetsave.com

Right now, Indian farmers are responsible for the cost of vegetable production based on the cost of production, seed storage, fertilizer costs etc. The government controls market prices by setting a minimum support price (MSP) at which it will buy produce from farmers. Now, alter the situation and put an American corporation on the other side of the fence. Monsanto will have price control over the seeds that it supplies to farmers. Since there is virtually no cost to replicating seeds year after year (the R&D cost has probably been recouped by now), every rupee charged by the monopoly of Monsanto will go straight to its profit margins and to the bottom line cost of foodgrains in our country. As a corollary, our government (which procures over 50% of our foodgrains) will be paying farmers so that they can pass on some of the money to an MNC as the cost of seeds. Just imagine, every single man, woman and child in India will effectively be paying a food tax to an American corporation. This money will be money that will be leached from our country, just like the way the Britishers leached money through their Manchester Cotton mills while using raw cotton from India. Frankly speaking, it's a terrible idea.

Courtesy: Greenpeace

Now, let's come to the obvious question - "why would people buy GM crops?" The answer is quite obvious - there is a market for foods such as seedless brinjals (the Bt Brinjal product) just as there is a market for seedless watermelons. Also, GM crops are like drugs - first - show the public the high of high quality blemish-less, super-sized onions, brinjals, oranges, wheat etc. The public will get hooked onto the product and will generate high demand. Farmers will then cave into market forces and will be forced to plant GM crops in order to realize higher margins from their farmland. They will abandon their traditional methods of hybridization and seed selection and start buying seeds off-the-shelf from Monsanto. Monsanto could start off with supplying seeds for free to get farmers onboard (after all, besides the initial R&D cost, they really don't have large recurring costs in seed generation). Farmers would try it out and sell the GM produce on the market (they could even start a black market for GM crops on the sly if they so wished). Once the farmers are hooked onto the seeds, Monsanto - being a monopoly - could revise the rates citing XYZ concerns (as most monopolies are wont to do) and then you end up with an American corporation leaching supra-normal profits from us. And once the floodgates of GM crops open for this country, there is no going back because GM crops will freely intermingle with natural crops (a recent study showed that 80% of wild canola crop in North America had atleast 1 artificial gene after a few years of the introduction of GM Canola into the country). This is a really disturbing scenario. Monsanto will start out small, but will quickly grow into a mammoth agricultural concern having control over large swathes of our food supply chain. See the chart embedded below to see how a single company can take over a country's entire crop acreage.

But before getting too far ahead of ourselves, let us analyze the Bt Brinjal issue. Farmers had opposed the Bt Brinjal project because of 2 major reasons - a dependence on a corporation for seeds every year and unproven health risks from GM foods. Indian farmers are smart in a way. But. if you notice, recently, the opposition to Bt Brinjal has quietened down and the images of demonstrating farmers have faded from public memory. Besides, Monsanto has been in India for about 3? years now and they have had plenty of time to figure out ways to win farmers over to their cause. However, despite all their efforts, there is bound to be opposition to the introduction of GM crops in India. So, how do they intend to overcome that? The answer is: "Lobby the government".

Now, the Indian government can't be lobbied overtly. So, let's do it the Indian way: bribe a few ministers, pull in a few favours and get an independent authority created by an act of Parliament. (After all, the multitude of scams involving our MPs has clearly demonstrated that more than a few of them are for sale). That independent body will function like the US-FDA and grant approvals for all GM crops intending to be introduced into India. Also, by making it an autonomous non-profit body, they could conceivable claim exemption from the Right to Information Act by virtue of it not being a "public authority" as defined under the act. Then, it would remain a simple matter of getting just a few officials to fall into line and you'll have a green light for all kinds of GM crops being introduced into India. Not only that, to go one step further, India would become a testing ground for all kinds of GM crops that have to be introduced into other countries. Given the extremely lax oversight of our government departments, this is sure to lead to lots of issues for us in the future and when things start to go wrong in the country, we will conveniently have yet another government department to blame for not performing its job properly. The only difference is that this department is being brought into being for one and only one reason - to give Monsanto a crack in the wall to introduce GM foods into our country.

Reviewing all this, you - my casual, tech inclined reader will feel that this scenario is quite far-fetched. So let me put forth a few supporting facts:

1. Two reporters from Fox news set out to research Monsanto and their claims on GM food safety. Monsanto literally buried their report under a threat of a lawsuit. It's a really explosive video (one that I'd seen some time ago). You need to watch this to get the full context of what's happening in the GM world today.

Link: http://www.youtube.com/watch?v=axU9ngbTxKw

2. Greenpeace states that there is a "secretive bill" that is likely to be tabled in the monsoon session of the Indian Parliament that seeks to create a Biotechnology Regulatory Authority of India (BRAI) that will be an authority for clearing the introduction of GM foods into India. There has been no notable public discussion on the contents of this bill. More details here: http://www.greenpeace.in/take-action/save-your-food/stop-the-brai-bill.php?tyf

3. Monsanto has been trying out GM Wheat since before 2004. The plans to introduce it in North America were abandoned in 2004. Source: http://www.gmo-compass.org/eng/grocery_shopping/crops/22.genetically_modified_wheat.html . However, recently, Monsanto has carried out trials of GM wheat in Australia (which is one of the largest exporters of Wheat in the world). Source: http://www.crikey.com.au/2010/09/17/gm-seed-for-australian-wheat-great-initiative-or-costly-experiment/. India is one of the world's largest wheat growing nations and the introduction of GM wheat would give the reigns of our food supply to single corporation's products.

4. It is also important to note that there are virtually no alternative companies in the marketplace to put out contradictory claims and act as whistleblowers. The ones selling the products are also the ones certifying them as safe. That's hardly something that would put your mind at ease. To make things worse, Monsanto has a history of bringing large and costly lawsuits against companies and individuals that challenge the safety of their products - after all - their entire market base depends on the faith that the people have in the food that they are consuming and it would be highly detrimental to their plans if someone conclusively demonstrated that GM foods had an adverse impact on human health.

After seeing all this, would you trust this company with your food? Take your time and think it over.

See these other articles to read more about this as portrayed in the media:

A law unto itself, www.outlookindia.com, March 8, 2010
http://www.outlookindia.com/article.aspx?264454
India says no to Bt brinjal, for now, www.rediff.com, February 9, 2010
http://business.rediff.com/report/2010/feb/09/india-says-no-to-bt-brinjal-for-now.htm
No GM trials in State: Katti, Deccan Herald, July 20, 2011
http://www.deccanherald.com/content/177877/no-gm-trials-state-katti.html
Biotech Bill: Sweeping powers, glaring omissions, www.rediff.com, March 11, 2010
http://business.rediff.com/column/2010/mar/11/guest-biotech-bill-glaring-omissions.htm

Remember, Monsanto is a multi-billion dollar company and has deep pockets to buy out the media through advertising dollars. This negative coverage might change substantially in the future to become positive coverage. So keep your eyes open for it.

Facebook Goes the Google+ way - tries out Google+ style comment formats

2011-07-22T02:46:00.002+05:30

I was just browsing on Facebook and I was surprised to see a link to a video posted in the comments being shown inline. Here's how the new interface looks:

Suprisingly, the video player also seemed to be updated.

See the new style controls?

Hmm... It seems okay... Though the whole site could do with a big makeover...

The FBI Chargesheet for ISI Lobbying via Americans

2011-07-20T02:34:00.001+05:30

I just came to know of the FBI chargesheet against Americans for channeling funds from the ISI for lobbying purposes. Read the entire chargesheet below.

Fai Ahmad Complaint Affidavit

Solved? LaTeX Error: pdf file is damaged - attempting to reconstruct xref table

2011-06-21T12:56:00.001+05:30

Update: Greater experience with this issue has given me greater clarity. The issue is not related to LaTeX. Getting this error message simply means that evince tried to access the PDF file while it was being written to by pdflatex or latex and found it in a damaged state. This happens if you have a large pdf file being generated with lots of text or a number of figures. There's nothing to worry about if you get this error message. You can safely ignore it.

---- Original Post Below ---

This is just a short note for anyone coming across this problem while doing LaTeX work.

Google doesn't have a decent explanation for why this message occurs. I don't have one either

but I have isolated the cause for my particular issue and I hopefully have a fix.

The error under discussion is:

Error: PDF file is damaged - attempting to reconstruct xref table... Error: Couldn't find trailer dictionary Error: Couldn't read xref table Error: PDF file is damaged - attempting to reconstruct xref table... Error: Couldn't find trailer dictionary Error: Couldn't read xref table

I hit this error while importing a PNG file exported from GIMP into my LaTeX thesis using the

\includegraphics command. The PNG file probably had a few transparent pixels inserted due to

the editing process because the base image (which was unmodified) was imported without any

issue into the LaTeX PDF and this is something that LaTeX doesn't like.

I fixed this issue by simply removing the obnoxious PNG and converting that to a JPG. The

problem got solved.

If it helps you, let me know in the comments! :)

What is the difference between a mutex and a semaphore?

2011-06-17T22:08:00.000+05:30

Okay. This is another common interview question. Here are a few of the points you should keep in mind:

Q1: What is a semaphore?

* A semaphore is a mechanism to convey events between two or more cooperating processes. Now what does this mean exactly?
In a typical multiprocessing machine, many processes are being timeshared on a single CPU. The degree to which computation will proceed in one process depends on how big a time slice it has been given by the OS CPU Scheduler. Thus, different processes will be at different stages of computation at any point of time. So, how do we coordinate across processes? We use semaphores to tell other processes that we've reached certain stages in our processing (via a sem_post) or to wait for other processes to tell us that they've reached certain well defined stages in their computation (via a sem_wait). These two major functions allow us to synchronize computation across process boundaries and this is the main function of a semaphore.

Effectively, you can think of a semaphore as a click lock with many keys. Anybody who holds a key can open the lock. There can be multiple keys and multiple people can open the lock at any time. Anybody can lock the lock.

Q2: What is a mutex?
* A mutex is a mechanism to ensure mutual exclusion. In simple terms, this means that one and only 1 process will be allowed to execute a particular piece of code guarded by a mutex. This particular piece of code is called the critical section. A mutex has 2 major properties:
1. Only one of the cooperating processes gains access to the critical section.
2. Only the process that holds access to the critical section (called the owner of the mutex) can revoke its access to the critical section. (This is called ownership of the critical section or mutex).

Effectively, a mutex is the concept of a lock + owner. There is a lock and only 1 key. Whoever uses a key to open the lock is called the owner of the mutex. Only he can lock the lock or open it. Thus, there can be at max 1 person at any time in the locked room.

By ensuring that no more than 1 process can ever own and release the mutex, mutual exclusion is ensured.

* A semaphore can be used to implement a mutex. This is possible if we associate the concept of an "owner" to a binary semaphore (a click lock with 1 key only). Look at the following pseudocode:

Global Initialization:
sem_init(&sem, 1); // Binary Semaphore (ensures that only 1 process can enter the Critical Section)
owner = 0; // No pid

Mutex Lock Code:
sem_wait(&sem);
owner = getpid();

// Critical Section

Mutex Unlock Code:
if (owner != getpid()) {
abort(); // non-owner is trying to unlock the mutex. Invalid state - abort. (Ensures Mutual Exclusion)
}
sem_post(&sem);

Note how the unlock code verifies the owner of the lock and thus fulfills the function of a mutex. This is a requirement for ensuring that only the owner of the lock is able to unlock the code.

This is in sharp contrast to some other uses of a semaphore.
Consider the following example:

Global:
sem_init(&sem1, 1);
sem_init(&sem2, 0);

void f() {
while(true) {
sem_wait(&sem1);
// CS1
sem_post(&sem2);
}
}

void g() {
while(true) {
sem_wait(&sem2);
// CS2
sem_post(&sem1);
}
}

If f() and g() are 2 processes cooperating via the 2 semaphores, the way that the code is written ensures that the critical sections will be executed one after the other (CS1 - CS2 - CS1 - CS2 etc).
This example illustrates the fact that semaphores can be used to convey events between 2 cooperating processes. In this case, the events being conveyed are the completion of the critical sections of f() and g(). Also note that in this example, the process that waits on a semaphore isn't the one that is posting to the semaphore. This is a major difference between a semaphore and a mutex because a mutex is unable to achieve such a behaviour.

Q3: What are counting semaphores?

* Semaphores also come in a variety of flavours. One such flavour is called a counting semaphore. A counting semaphore is one that is able to allow more than one process to successfully wait on it. It lets through some "count" number of processes through sem_waits. This makes a counting semaphore more useful than a mutex - for example, it can be used to implement reader-writer locks or allow a fixed level of concurrency in a piece of code. Note that mutexes only allow for one process/thread in a critical section.

* Please remember that mutexes need to be acquired and released by the same thread. A request release a mutex currently held by another process should be treated as invalid code. This is different from the behaviour of a semaphore. A semaphore may be WAIT-ed upon by one thread/process and be POST-ed by another. This is usually by design. Otherwise mutual exclusion cannot be guaranteed in all cases.

I hope this makes the differences between semaphores and mutexes very clear. If you have any more doubts, just put in your questions in the comments!

An approach better than Pancake Sorting for a restricted sort

2011-06-16T04:26:00.006+05:30

The original source of the question for this blog post is again Algo Geeks.

Here's the problem description:

There is an array in an external system which cannot be accessed directly.
The system exposes 3 functions whose complexity is O(1) :
length() - returns the length of the array.
get(i) - returns the element at index i.
reverse(i,j) - reverses the elements in the array from index i to index j (both indexes inclusive).

Sort the array in the best possible way using only these 3 operations?

The direct solution to sorting in this case is a Pancake Sort (see the video embedded below).

Pancake sort has a direct implementation complexity of O(N2) as locating the max element in the unsorted section of the array is an O(N) operation. Besides this, it is obvious that one cannot use standard quicksort or heapsort directly since a swap operation

isn't supplied. However, we can simulate a swap operation using the reverse operator. It's easy to do:

swap(i, j) = reverse(i + 1, j) reverse(i, i+1), reverse(i+1, j) where i, j are indices to the array.

Given this swap operation, we can then implement any O(n log n) sort that we desire since we already have random access via the get(i) function.

However, we can do better:

Let us define a run as a sequence of consecutive values in the array.

1. Go through the array and reverse descending runs - O(n) as reverse(i, j) is supplied. Now you have an array with many runs in ascending order. It looks something like a0, a1 ... ak, b0, b1, ... bl, c0, c1, ... cm ...

2. Perform a merge procedure pairwise for consecutive runs in the array. The merge is performed as follows:

If a0, a1, a2 ...ak b0, b1, b2... bl are consecutive runs, then:

a) Compare a0, b0 (using get() operation to get the values).

--- Else If b0 < a0 then perform step (b).

--- Else a0 is in its correct place, increment pointer to the 'a' array and repeat step 2 for a1... ak, b0 ... bl

b) reverse(a0 ... b0) and then reverse (ak ... a0) - giving b0, a0, a1 ... ak, b1, b2 .. bl. Repeat step 2 for the run a0, a1 ... ak, b1, b2 ... bl

Complexity analysis:

Step 1 can be done in O(n) time. Using 2 indices to locate boundaries of runs and an O(1) reverse call, this is easy to achieve.

Step 2 The merge procedure requires 2 get() operations (one of which may be optimized away with careful coding) and (in the worst case) 2 reverse(i,j) operations. Therefore, the cost of putting 1 element in its correct position is O(1). Hence 2 sequences of lengths n and m can be merged in O(min{n, m}) swaps and O(max{n, m}) time.

Overall complexity:

Let us assume that we end up with K runs of lengths L1 - Lk from step 1. Cost of this step O(N)

Cost of merging adjacent runs = O(min{Li, Li+1}) (in terms of swaps), O(max{Li, Lj}) in terms of comparisons.

Total number of merges that will take place = K

The worst case for the problem will occur when all the arguments to min{ Li, Lj } are the same. This happens when the runs are of size N/K.

Therefore, cost of merge = O( N/K ) swaps (rather reverse(i,j) calls) and total number of merges = K. Hence overall swaps complexity is O( K * N/K ) = O( N ). However, overall comparison complexity remains O(N log N). So using the reverse operation, we've be able to optimize the number of swaps. However, we cannot breach the lower bound of Omega(n log n) for the number of comparisons required for sorting as this is a comparison based sort.

Comments invited!

Also, make sure you follow me on Twitter at http://twitter.com/divyekapoor

A combinatorial game problem

2011-06-16T01:38:00.002+05:30

So, I was lurking on the AlgoGeeks group when I came across this interesting question posted by Piyush from IIIT-Allahabad. Apparently, it came in a DE Shaw interview.

The original question is:

Given N heaps numbered sequentially from 1 to N that contain atleast 1 counter each, players move in turns to pick counters from the heaps. The rules of the game are such that counters can only be picked from the lowest numbered heap that is not empty. The question is: design an algorithm for optimal play that will determine which player will win given a configuration of heaps.

Here's my answer:

There are only 2 types of heaps in this problem:

1. Optional heaps -> have > 1 coins

2. Non-optional heaps -> have = 1 coins

For optional heaps, optimal play dictates that you either pick all the elements from the heap or leave just one element in the heap when you play your turn. This is an obvious constraint because otherwise, you're putting your opponent in the driving seat with a heap configuration that is similar to yours and if he can force a win, he will! :)

So, to repeat: there are only 2 things you can do with an optional heap - pick all or leave 1. Now, to get the solution for the game, read on:

Start from the rightmost heap.

This is base case - whoever gets this heap surely wins.

Look at the heaps before it.

If it is a non-optional heap (1 element only), then the assured outcome is the

inverse of the assured outcome of the next heap.

If it is an optional heap, then the assured outcome for whoever is first is a win - irrespective of the

assured outcome of the next heap. This is because the player whose turn

it is to move can either pick up all the elements of the heap thus converting it

into the assured outcome of the next heap (if that is a loss for the other player)

or can leave 1 element in the heap, thus getting a win by optimal play.

When there are multiple optional heaps in sequence, the optimal play is

to always force your opponent to keep picking the last element from each heap

so that you retain control over the fate of the game. Hence, a sequence of

optional heaps is the same as a single optional heap.

Unroll the loop till the first heap and output the assured outcome as the answer.

For example 1 2 2 2 1:

1 - Win

2 1 - Win for Player 1 at this stage

2 2 1 - Win for Player 1 at this stage

2 2 2 1 - Win for Player 1 at this stage

1 2 2 2 1 - Loss for Player 1 at this stage...

Outcome: Loss

This is equivalent to 1 2 1

For eg.

For the heap: 1 2 3 1 2

2 - win for player 1

1 2 - Loss for player 1

3 1 2 - Win for player 1

2 3 1 2 - Win for player 1

1 2 3 1 2 - Loss for player 1

This is equivalent to 1 2 1 2

For all the games discussed above:

Game 1: 2 3 -> is the same as game 2 2 which is equivalent to 2 -> Player 1 wins

Game 2: 1 2 -> is a loss for player 1 for obvious reasons

Game 3: 2 1 -> is a win because of the optional heap

Game 4: 1,2,3,1,4 -> Loss for player 1. Equal to 1 2 2 1 2 -> 1 2 1 2 -> Loss

Game 5: 1,1,2,3 -> Win for player 1. Equal to 1 1 2 2 -> 1 1 2 -> Win

Game 6: 2,1,3,4,5 -> Equal to 2 1 2 2 2 -> 2 1 2 -> Win for player 1

Nice question. Hope you enjoyed the solution too! :)

Feel free to leave a comment if you liked it and

don't forget to follow me on Twitter at: http://twitter.com/divyekapoor

Printing all permutations of a string containing duplicate characters (C/C++)

2011-06-12T12:14:00.003+05:30

This is a follow up post to my earlier post on printing all possible permutations of a string (also called Anagrams) using the C++ Standard Library. The earlier post is located here. This post should have come on this blog about 3 years ago. I'm no longer interested in solving problems like this but I wanted to put this up for the millions of people who get this problem in interviews and the like and to retain the same for posterity.

So, previously we've discussed how to print all possible permutations of a string without duplicates using the standard C++ library functions. That's all fine and dandy if we want to use the standard libraries – especially next_permutation, but what happens if we have to write our own code to do so?

In this blog post I'll present recursive solutions to the problem of printing all the possible permutations of a string. I'll even take up the case where the input string contains repeated letters later on in this post. The resultant function will be able to print all possible distinct permutations of a string containing duplicate characters.

Printing all permutations of a string containing no duplicate characters

Code 1: The recursive solution for a string with no duplicate characters in C/C++

char * full_string;

void permute(char * str, int length) {

if(length == 0) {

printf(“%s\n”, full_string);

return;

} else {

for(int i = 0; i < length; ++i) {

swap(str[0], str[i]);

permute(str+1, length-1);

swap(str[0], str[i]);

}

Call like: permute(full_string, strlen(full_string));

To understand how this works, just look at the string “ABC”.

Let us assume that we have a magic function permute2 that generates all possible permutations of a given string of length 2.

Then, the permutations problem for the string “ABC” can then be broken down as:

These permute2 values themselves can be broken down to smaller subproblems.

Here, it is obvious that permute1(any char) = char itself. This is the base case of this recursion. Unrolling the recursion for the 3 required values yields:

permute2(“BC”) = { “BC”, “CB” }

permute2(“AC”) = { “AC”, “CA”}

permute2(“AB”) = {“AB”, “BA”}

So the resultant sets of strings are:

permute3(“ABC”) = {“ABC”, “ACB”} U {“BAC”, “BCA”} U {“CAB”, “CBA”}

which is the set of all permutations of the string “ABC”. It is obvious to see that we are in fact just choosing the starting prefix of the permutation and then requesting the permute function to run on a smaller subproblem of permuting a smaller string.

To generalize, we can state that we can get all the permutations of a string using the general recurrence:

This formula basically means that you select a character sk from the string S of length n to represent the first character of the permutation, find all the permutations of the smaller string formed by removing sk from S and extend the permutations thus obtained by prefixing sk.

This is essentially what the code above is implementing. The two swap statements perform the work of selecting an element sk from the string S and replacing it back after permuting the smaller string

Printing all distinct permutations of a string containing duplicate characters

To achieve this, we just modify the above code a little. To avoid duplicates, we need to enforce the constraint that no character will be selected twice to place in the prefix before calling the subproblems. So, the resulting recursion gets modified as:

This simply means that at every stage of the recursion, pick only distinct characters. So, how do we do that? We pick the sk in ascending order.

Code 2: C/C++ code for finding all distinct permutations of a string with duplicate characters in it

char* full_string;

int counter = 0;

void permute(char *str, int length) {

if(length == 0) {

printf("%s\n", full_string);

++counter;

return;

} else {

// Find the smallest char in the string set it to be the first character. Solve the subproblem for the smaller string.

char *smallest = min_element(str, str + length);

iter_swap(str, smallest);

permute(str+1, length-1);

// Look for the smallest element greater than the first element of the current string

char *smallest_greater = str + length;

for(char *i = str+1; i != str+length; ++i)

if(*i > *str && (smallest_greater == str + length || *i < *smallest_greater))

smallest_greater = i;

while(smallest_greater != str+length) {

// If such an element is found, swap it into the first slot and recurse

iter_swap(str, smallest_greater);

permute(str+1, length-1);

// Repeat the loop if possible for the next greater character

smallest_greater = str + length;

for(char *i = str+1; i != str+length; ++i)

if(*i > *str && (smallest_greater == str + length || *i < *smallest_greater))

smallest_greater = i;

}

Code Explanation:

The fact that we are selecting the character to put at the beginning of the string str in strict ascending order gives us 2 major guarantees:

No character will be selected more than once. Hence the distinct selection requirement is satisfied.
All distinct characters in the string str will be selected. Hence, all the permutations will end up being generated

A small bonus of selecting the sk character in this fashion is that the permutations generated in the output will be in lexicographical order (dictionary order). This makes it easy to verify the correctness of the program.

This code uses two functions that you might not be aware of :

The functions iter_swap and min_element are provided by the standard C++ library. They are really simple and you could code your own versions easily.

iter_swap – it just swaps the elements pointed to by the respective pointers without changing the pointers themselves. So, it's basically equivalent to the function:
void iter_swap(char *ptr1, char *ptr2) {
}
min_element – finds the location of the minimum element that exists in the given range. In this case, it is the char* pointer pointing to the location of that element. It can be implemented like:
char * min_element(char *start, char *end) { // end is 1 beyond the last valid element
}

Of course, the standard library implements these as template functions so that they can be used with a variety of datatypes.

Code 3: The iterative solution.

The C++ standard library is an elegant repository of algorithms. You can also use the iterative next_permutation function to generate all the permutations of a string which might contain duplicates. Mark Nelson has done a superb job of explaining how next_permutation works at http://marknelson.us/2002/03/01/next-permutation/ - do take the time to go through his complete blog post. It is the best description of this algorithm till date. Sample code on how to use that function has already been provided in my previous post.

Code for this and many other algorithms can be found at the github archive: http://github.com/swagatata/ds_and_algos
However, all this is a work in progress.

C++ BigIntegers: Installing GMP with the C++ class extensions (gmpxx.h)

2011-06-12T05:49:00.003+05:30

So I was spending some time with GMP today, trying to install it on my Ubunty Natty (11.04). [1] I wanted to finally get BigInteger support for C/C++ in a hassle free manner. Naturally, I turned to my trusty Synaptic to get and install the libraries. A quick search for libgmp in the repository turned up some old versions of GMP and some modified packages. I was surprized! I was expecting libgmp to be in the Ubuntu repository. A quick Google confirmed that Ubuntu doesn't ship with GMP 5 (which was the latest at the time of this blog post). So I set down to install the library from source. So, first things first:

1) Get the gmp-5.0.2 library (or whatever's the latest now) from http://www.gmplib.org

2) Verify the file using gpg (Always a good practice)

gpg --verify gmp-5.0.2.tar.bz2.sig gmp-5.0.2.tar.bz2

You might get an error at this stage saying that the public key is not available. To fix that, issue

gpg --search-keys

and select the SWOX key from the options you get. The KEY_ID is mentioned right below the download link on the gmplib download page. The gmp-5.0.2.tar.bz2.sig file can be downloaded from the downloads area of the site.

Alternatively, you could check the SHA-1 or SHA-256 cryptographic checksum by extracting the .tar file from the .tar.bz2 or .tar.gz file and running sha1sum gmp-5.0.2.tar or sha256sum gmp-5.0.2.tar

3) Extract the files from the archive

tar -xvjf gmp-5.0.2.tar.bz2

4) Follow the installation instructions: Now here's the catch.

If you follow the standard installation instructions which ask you to follow the 3 step procedure: ./configure , make , sudo make install then you'll end up with only the C library built and installed. I did this and I spent quite a bit of time today messing around with GMP, trying to get it to install the C++ classes for enabling BigInteger support. Unfortunately, Google didn't help in fixing this problem. I couldn't find a thread which mentioned the installation of the C++ extensions. However, reading miscellaneous blog posts on issues with installing GMP, I figured out that the switch to install the C++ extensions is --enable-cxx and it has to be passed to ./configure. It seems obvious in hindsight but was really unobvious when I was figuring out the installation issues. So, here are the correct set of commands that you need to follow to get GMP to install with the C++ extensions.

./configure --enable-cxx

make

make check

sudo make install

This will install GMP to your /usr/local/include and /usr/local/lib directories. I prefer this because you can easily remove the files and folders later with minimal system modifications should you so desire. Also, this is the recommended way for non-system installed packages (read install from source packages) to install themselves on a linux system.

5) Verify that GMP has installed correctly

Create the following 2 programs to test out GMP:

test1.c:

#include <stdio.h>

#include <stdlib.h>

#include <gmp.h>

int main() {

mpz_t a, b, c;

mpz_inits(a, b, c, NULL);

mpz_set_si(a, rand());

mpz_set_si(b, rand());

mpz_add(c, a, b);

gmp_printf("%Zd + %Zd = %Zd\n", a, b, c);

// If you're not quitting, use mpz_clears(a, b, c, NULL)

return EXIT_SUCCESS;

}

Compile and test with: gcc test1.c -lgmp -static -o test1 && ./test1

test2.cc:

#include <iostream>

#include <cstdlib>

#include <gmpxx.h>

using namespace std;

int main() {

mpz_class a, b, c;

a = rand();

b = rand();

c = a + b;

cout << a << " + " << b << " = " << c << endl;

return EXIT_SUCCESS;

}

Compile and run with: g++ test2.cc -lgmpxx -lgmp -static -o test2 && ./test2

I've added the static flag to compile with the library included in the executable. If you want to use a shared library version of GMP, then omit the -static flag and make sure your LD_LIBRARY_FLAGS variable has /usr/local/lib present in it.

[1] GMP is the GNU Multi Precision computing library (Home page: http://www.gmplib.org) that provides unlimited precision computing support for C and C++. (Actually, the maximum limit of precision is 41 billion digits but by the time you get to that... hmm... you'll probably run out of space). Their code is very optimized and if you *ever* need BigInteger support in C or C++ - that's the way to go.

Of Parting Friends

2011-05-14T20:45:00.001+05:30

Life goes on much as before,

The characters change but the books are old

The books, they speak; the words unfold

Life's sweetest melodies.

~~ Divye Kapoor, 14 May 2011

Swagat's Testimonial

2011-05-09T13:38:00.001+05:30

It feels really good once in a while to receive a testimonial from a person you've worked with, one who truly understands you and your abilities. Swagat has been a dear friend - one with whom I've spent countless hours and from whom I've learnt a lot. As part of the usual rituals before passing out from campus, he wrote me a testimonial. Here's what he had to say:

Swagat Konchada says:

In a few days, we'll go our ways out of this place. In a few months, you'll start a new life and all this

would be nothing but a memory. However, I think our memories would be the best of the lot in my mind.

I learned more from Divye than from the rest of the campus. He's a treasure of uncalculable amount of knowledge. And the best thing is there is no mystery behind why he is the DK. Many people have a superstition that hard work is for someone who has no ability/skill. DK is the first person who shattered such orthodoxy in me by proving how a combination of passion, ability and perseverance can make wonders in your life. Of many, I thank him for this one particularly.

Everyone knows the geeky side of DK. They remember him whenever they face with any problem regarding computers. They know he is the go to guy for all tech problems. They feel insecure at the sight of his confidence and knowledge. If only they'd look beyond the beauty of his brain into the beauty of his heart. To anyone who still doubt it, I can assure you that DK is human like you and me :). For me he is the goto guy for any problem.

He is my best friend.

I only wish the times we solved puzzles together, we discussed current affairs, we had dinner/rolls

together, we participated in COGNI, we experimented with the piano, and a lot more... if only they'd last

forever... I'll miss you man...

DK's addendum: I won't miss you. You know why? Because we'll stay in touch. I don't let friends get away so easily. BTW, you're awesome! And thanks! :D

An Introduction to Unity Keyboard Shortcuts

2011-05-07T06:02:00.007+05:30

Credit: http://www.tuxmachines.org/node/50311

So, a number of people have posted that they don't like the new Unity Desktop interface so much on the new Ubuntu 11.04. You're reading this guide because you probably are having trouble adjusting to it. I, on the other hand, am starting to find Unity quite an improvement over the so called Ubuntu Classic interface. So, to help you out, here are a couple of tips that will push you along on the path of becoming a Unity fanboy.

Observation: The main menu bar for all applications has been shifted into the title bar. This is quite similar to the way the Mac handles things. The currently running application's title bar is hidden in the top bar. To show it, you can either move your mouse over to the top bar or you can press the Alt key. I personally prefer the Alt key as it's a keyboard friendly way of accessing the menu.

Many people have gripes with the left sidebar present in the Unity interface. The primary problem being that the default softwares on the left menu are not the ones they might be using the most. So, here are a few tips I've used to improve my experience with the sidebar.

Tip 1: Open the applications that you use frequently and locate their icons on the left panel. Right click on them and check mark the "Keep in Launcher" menu item. They end up being very readily available.

Tip 2: You can open the launcher menu from the keyboard by using the shortcut key Alt+F1. The topmost launcher icon gets highlighted and you can use the keyboard to navigate to the application that you want to switch to or start. If you want to directly start an application, use the Alt+F2 shortcut. (In Ubuntu Class this would bring up the Run box. Now, it brings up a sleeker interface to search for and open folders or applications).

Tip 3: The icons present in the launcher menu are rearrangable. Long click on the icons to make the icons draggable and modify the menu to suit your taste. A pro-tip here is that the top 10 menu items are accessible directly from the keyboard. So make sure you put your frequently used icons there. My suggestions are that you should have a Chrome/Firefox, Gedit, Terminal, Totem and Synaptic present in the top 10 icons.

Tip 4: As alluded to in Tip 3, the top 10 launcher icons are accessible via keyboard shortcuts. Press the Windows Key (Win key) along with a number to launch the corresponding icon. This will launch the application if it hasn't started or switch to it if an instance of it already exists. This is pretty handy for switching between applications as you don't need to go through the Alt+Tab mechanism and you can directly switch if you remember the launcher number of the application that you want to switch to.

For example, I frequently open a number of windows and when I want to switch over to my web browser (Chrome) whose icon is present at location 2 in my launcher, I just press Win+2. That's it! I'm now in Chrome. Now if I want to go back to my code in Gedit, I just press Win+4 and I'm in Gedit. No messy Alt+Tab business.

So that concludes my short introduction to Unity and it's keyboard shortcuts. I hope you liked it. A complete list of the keyboard shortcuts for Unity is in the image below. Feel free to comment if you have any tips of your own.

Image Credits: http://soumalyaray.blogspot.com/2011/04/ubuntu-unity-keyboard-shortcut-as.html

Sadi Gali - Punjabi Lyrics and Meaning (in English) - Tanu Weds Manu

2011-02-25T22:28:00.003+05:30

Another superb song makes its appearance on the Bollywood scene. Sadi Gali from Tanu Weds Manu is a perfect Punjabi Dance track. Performed by Lehmber Husainpuri from RDB, words aren't sufficient to describe it. Just listening to it makes you want to jump up and start tapping your feet to the music. It's even garnered over a million plays on Youtube. In an effort to make this song's lyrics accessible to the masses, here's the meaning of the song in English paragraph by paragraph. I made it while listening to this song non-stop on loop. Hope you enjoy it!

Kudiyan de vich phir hassdi khed di
[Hasdi] x 4 Khed di
Ho, gutt di parandi teri naujawanu meldi
[Naujawa-] x 4 -nu meldi

Again you're smiling and playing in the midst of girls
Ho, Your "gutt da paranda"* ties up youngsters (in your love)

gutt da paranda = An artificial hair extender often worn by Punjabi women to increase the length of their locks.

Kudiyan de vich phire hassdi khed di
College nu jaave ni tu naujwanu meldi
Aashiqan nu darsh dikhaya karo
Ni kadi sadi gali bhul ke vi
[Aaya karo ji kadi sadi gali bhul ke vi] x 3 times

Again you're smiling and playing in the midst of girls
You go to college and you meet youngsters
Show yourself to your umpteen lovers
Oh, Come by my way sometime, even if by mistake
[Oh, please do come by my way sometime, even if by mistake] x 3

Goriyan gallan 'ch tere toye badey fabde
[Toye] x 4 badey fabde
Mitran pyaaran nu sohne badey lagde
[Sonhe be] x 4 badey lagde

Your dimples look superb on your fair cheeks
Friends and Near-Dear ones find them really pretty
[Toye = Dimples]

Goriyan gallan 'ch tere toye badey fabde
Mitran pyaaran nu sohne badey lagde
Thoda saade utte taras bhi khaya karo
Ni kadi sadi gali bhul ke vi
[Aaya karo ji kadi sadi gali bhul ke vi] x 3 times

Your dimples look superb on your fair cheeks
Friends and Near-Dear ones find them really pretty
Have some pity on me too
Oh, Come by my way sometime, even if by mistake
[Oh, please do come by my way sometime, even if by mistake] x 3

Jidro vi lange munde maarde seetiyan
[Maarde] x 4 seetiyan
Ho kar de ishaare koi maarda geetiyan
[Maarda] x 4 geetiyan

Wherever you pass by guys whistle at you
Somebody makes passes and runs rings around you (Pun: throws small pellets at you)

Jidro vi lange munde maarde seetiyan
Kar de ishaare koi maarda geetiyan
Sajna nu aina na sataya karo
Ni kadi sadi gali bhul ke vi
Aaya karo ji kadi sadi gali bhul ke vi

Wherever you pass by guys whistle at you
Somebody makes passes and throws pebbles at you
Don't trouble your lovers so much
Oh, come by my way sometime, even if by mistake
Oh, please do come sometime, even if by mistake

Rab ne husn ditta maan nai karida
[Maan ni] x 4 karida
Aakkadan di agg vich ainwe nai sadee da
[Ainwe ni] x 4 sadee da

God has given you looks, don't be proud
Don't burn so in the fire of arrogance

Rab ne husn ditta maan nai kari da
Aakkadan di agg vich ainwe nai sadee da
Kade pyaar wala meeh barsaya karo
Ni kadi sadi gali bhul ke vi
[Aaya karo ji kadi sadi gali bhul ke vi] x 3

God has given you looks, don't be proud
Don't burn so in the fire of arrogance
Do shower your droplets of love
Oh, come by my way sometime, even if by mistake
[Oh, please do come sometime, even if by mistake] x 3

Lehmber ne ban jana tera manmeet ni
[Tera ma] x 4 manmeet ni
Sacchi succhi ohde naal pala tu preet ni
[Pala tu] x 4 preet ni

Lehmber (the singer) is going to become your lover
Get involved with him absolutely truly (with a pure heart)

Lehmber ne ban jana tera manmeet ni
Sacchi succhi ohde naal pala tu preet ni
Saareyan nu mangar na laaya karo
Ni ji kadi sadi gali bhul ke vi
[Aaya karo ji kadi saadi gali bhul ke vi] x 7

Lehmber (the singer) is going to become your lover
Get involved with him absolutely truly
But don't bring everyone with you (when you come by)
Oh, come by my/his way sometime, even if by mistake
[Oh, please do come sometime, even if by mistake] x 7

Song Name: Sadi Gali
Film/Album: Tanu Weds Manu
Singer(s): Lehmber Hussainpuri
Music Director: Krsna
Lyricist: Rajshekhar
Length: 4:24
Picturised on: R Madhavan, Kangna Ranaut

If you find any errors - just let me know. Comments welcome! :)

How do you prevent other linux users from listing your files in a directory?

2011-02-03T19:50:00.002+05:30

I'd got this question from Ahmet from Turkey via Aardvark. I'd known this answer for a while and it was trivial to reply. For posterity, here's my answer:

The short and sweet answer:

1) Use the chmod tool to remove the "others read/write/execute" permission bits from the directories that you don't want others to be viewing. A command like

chmod 750 /path/to/directory/root

should do the trick. You might even want to consider the -R option for recursive application of these permissions.

Note: if you don't use the recursive option, you might be able to ls or cd into a subdirectory even if the parent directory has the permissions disabled.

2) For an explanation of why this works, just have a look at this site: http://www.perlfect.com/articles/chmod.shtml - the directory permissions section should make things clear.

A short synopsis is:

Read permission on a directory - Allows ls to list the files in the directory

Write permission on a directory - Allows files to be deleted

Execute permission on a directory - Allows a user to cd into the directory

Technically:

Read - Read the directory inode and hence list the files and related info

Write - Modify the directory inode

Execute - Allow a chdir(...) system call to succeed on the particular inode

Removing these permissions is akin to saying that you don't want anybody else messing around with this inode (that you own).

If you want to know more about inodes, check out Inodes on Wikipedia.

Thank you from the Wikimedia Foundation

2010-12-08T14:24:00.000+05:30

From: Sue Gardner <...@wikimedia.org>
Date: Wed, Dec 8, 2010 at 1:41 PM
Subject: Thank you from the Wikimedia Foundation

Dear Divye,

Thank you for your gift of USD 100 to the Wikimedia Foundation, received on December 8, 2010. I'm very grateful for your support.
Your donation celebrates everything Wikipedia and its sister sites stand for: the power of information to help people live better lives, and the importance of sharing, freedom, learning and discovery. Thank you so much for helping to keep these projects freely available for their more than 400 million monthly readers around the world.

Your money supports technology and people. The Wikimedia Foundation develops and improves the technology behind Wikipedia and nine other projects, and sustains the infrastructure that keeps them up and running. The Foundation has a staff of about fifty, which provides technical, administrative, legal and outreach support for the global community of volunteers who write and edit Wikipedia.
Many people love Wikipedia, but a surprising number don't know it's run by a non-profit. Please help us spread the word by telling a few of your friends.

And again, thank you for supporting free knowledge.

Sincerely Yours,

Sue Gardner
Executive Director

* To donate: http://donate.wikimedia.org
* To visit our Blog: http://blog.wikimedia.org
* To follow us on Twitter: http://twitter.com/wikimedia
* To follow us on Facebook: http://www.facebook.com/wikipedia

Wikipedia - A big "Thank you"

2010-12-08T13:47:00.000+05:30

I just made a donation of $100 to Wikipedia in recognition of the shared treasure of knowledge it maintains on such a huge wealth of topics. Thank you so much Wikipedia for all that you've done for me. I am indebted to you.

Google Interview Questions and the Google Campus Interview Process 2011

2010-12-03T02:42:00.000+05:30

Hi Guys,

I know I'm not really writing a letter, but I really felt that I should jot down my impression of the Google Campus Placement process of 2010 before I forgot most of it. As a lot of my Facebook friends know by now, I've been given a campus placement offer by Google. Naturally, I'm really excited about it. Here's the story of how it all happened - a blow by blow account. (Tip: The interview questions are well marked out in the narrative and you can skip to them if you're not really interested in the campus process narrative).

Google's hiring process is known to be pretty tough and their engineers are counted among the best in the world. The first whiff of that came through when a couple of young techies and an HR landed on campus sometime in November to carry out their written test. 50 eligible candidates for the test and 50 copies of the question paper: +3 -1 was the scoring scheme - so no guessing! (or atleast very calculative guessing). Most of the interview questions were pretty standard in nature - probability, expectation, some coding questions. Judge for yourself. Here are the questions for 2010 (reconstructed from collective memory of all the candidates that gave the test).

Google Placement Paper 2010
10th November 2010
Eligibility : B Tech/IDD/M Tech/PHD-CSE
CGPA-7.0 for B Tech, 7.5 for M Tech
Time Allocated : 65 mins

There were 17 objective questions and 1 subjective question.

1) Given preorder traversal of a Binary Search Tree. From the given options you have to select which one can possibly be the inorder traversal of the tree.

[If it is indeed a BST, then the correct answer should be the one which is in sorted order]

2) If u could find the (n/4)th element of an array in O(n) time, then what is the worst time complexity of quick sort algo if this algo is used to decide the pivot element.

Answer : It's O(nlogn), since we can write the execution time as

T(n) = . T(n . r) + T(n (1 - r)) + O(n)
where r is 1/4 for this case.
for any r < 1, we have the expression recursively approaching
T(n ) = T(n * r^2) + 2 T(n * r * (1 - r)) + T(n * (1 - r)^2) + 2O(n) ; [O(n) = O(nr) + O(n(1-r))]
the number of O(n)s adds = log n/log r or logn/log(1-r) whichever is higher... but just logn times

3) find the min no of comparisons required to find both the max and min elements of an array containing 20 elements.

Ans) Can be done in a total of 28 comparisons.

4) If an array[0...m-1,0....n-1] is stored in column major format how will u find the (i,j) element?
a)i*n+j
b)i*m+j
c)j*n+i
d)j*m+i

5)If an insurance company pays $5000 for complete loss, $1500 in case of a loss of $2000 and more and nothing in case the loss is less that $2000. It obviously pays nothing in case of no loss.
If the probability of the first 3 events are 0.02,0.10 and 0.3 , find what should the company charge in order to make a profit of $50 from each customer

6) the prob of finding the parking slot occupied is 1/3.
U find it empty for 9 consecutive days.
Find the prob that it will be empty on the 10th day.

7) consider a NxN matrix in which the elements are either 0 or 1.
Find how many such matrixes are possible that are symmetric in nature(the matrix and its transpose count as 1.

8) 1<=i,j,k<=300.
Find (i,j,k) pairs such that their sum is divisible by 3.
(2,2,1) and (2,1,2) are counted as different.

9) in the loop
int counter=0;
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
   for(k=j+1;k<10;k++)
     for(l=k+1;l<10;l++)
       for(m=l+1;m<10;m++)
         counter++;

Find the value of counter in the end.
Ans. 10C5
i,j,k,l,m can be any 5 different numbers between [0-9] such that i<j<k<l<m. So, choose any 5 numbers and there is only one way to arrange.

10) Consider a set S of the first 10 natural numbers.
Find the number of subsets that do not contain consecutive elements.
Ans)

Subsets of length 0 = 1

Subsets of length 1 = 10

Subsets of length 2 = 36

Subsets of length 3 = 56

Subsets of length 4 = 35

Subsets of length 5 = 6

Total = 144

11) A question on TestandSet(), which are used as locks.....taught in OS course.
enter_CS() //This is what I remember
{
while(TestandSet(X));
}
Exit_CS()
{
X=0;
}

12) A disk contains 16 partition unit , each unit contains 128 subunits, and each subunit contains 256 sectors of 512 byte each.
Find out what is total storage capacity?
Also find out the no of bits required to identify each sector?
Ans) 256 MB, 19 bits

13) Which of the following is not a Regular Language :
a)None given
b)(0^i).(1^j) such that i<j
c)(0^i).w.(1^j) such that w belongs to {0,1}* and i>=0
d) such that every pth input digit is 0 where p is a prime number

14)find the output

void f(char * x)
{
x++;
*x='a';
}

int main()
{
char * str="hello";
f(str);
cout<<str;
system("pause");
return 0;
}

a) hello
b)hallo
c)allo
d)empty string

15)Given an sorted array, what is the complexity of finding weather a number is present n/2 times or not.
a)O(lgn)
b)O(n)
c)O((lgn)^2)
d)O(1)
[Ans is option d]

16)The weight of a squence a0, a1,a2,... ,an is defined as a0+a1/2+a2/(2^2)+...+an/(2^(n)). A subsequence of a sequence is said to be a sequence with some of the elements deleted from the original sequence but the order of the sequence remaining the same. Now let X be the maximum weight for a subsequence of a sequence a0,a1,a2,a3..,an. And Y be the maximum weight for a subsequence of the sequence a1,a1,a2,a3.....,an. Then X in terms of Y is
a) max(Y,a0+Y)
b)max(Y,a0+Y/2)
c)max(Y,a0+2*Y)
d)a0+Y/2
[opn b]

17) What is the complexity for finding all the leaders in an array? A leader is defined as an element which is greater than all the elements to its right.

18) Subjective question
Write a program to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order.

For Ex : in the circular array ABCDEABCCDE
The answer is 6 because the circular string starting from the element A in the 6th position comes first in the dictionary formed from all the possible strings of the circular array.

The pre-placement talk was well received (especially since the brother of one of the 2010 B.Tech passouts and an IIT Roorkee alumni had come for giving the PPT). Most of the interaction was very informal with questions ranging from mundane to the technical. Google Instant and the "Did you mean?" feature of Google were the hot topics of discussion and of course, how can we omit the discussion on the Google core search algorithm. The actual interview process was slated for 29th November. A number of questions were asked by the curious audience and very candidly answered by the techies.

The interview process began dot on time at 6:00 pm on 29th November. A couple of minutes spent getting things in order and off we go!

The first indication that we were dealing with a company that was serious about the people it hired was the fact that it had arrived on campus as a team of 16 people hiring for 3 different profiles. The fact was that they were interviewing only 12 candidates shortlisted from the written test. A quick, back of the envelope calculation shows that they've spent more than Rs. 1 lakh per campus that they've visited (5,000 x 16 airfare + hotel + travel). All the interviews were soon cubbyholed in the board rooms on the first floor of the placement office and off started the mating ritual: people would go into rooms and emerge 45-50 minutes later after having an intense session. Here's how my interviews went.

Interview 1: 45 minutes

Q1. Given a graph with all vertices of even degree, how will you print the Euler's tour of the graph?

A: Fleury's Algorithm

Q2. Given a set of overlapping intervals of the form (start, end), each of which is associated with a property (say S), print a sequence of disjoint intervals with all properties current valid in that interval.

eg. (1, 3, S0) (2, 3, S1) (2, 4, S2) yields (1,2, S0), (2, 3, S0 + S1 + S2), (3,4,S2) as the disjoint intervals.

Also, code a solution to the above problem.

Q3. Design a site similar to tinyurl.com

Q4. Now scale it to higher loads.

Q5. Given that you now have 2 geographically separated datacenters and a request comes in for a url that's not present in your current datacentre, how will you handle it?

Q6. Various questions about failovers, replication, node failures, load balancing, redirects etc.

Interview 2: 45 minutes - This one went horribly.

Q1. Given a 2^n x 2^n chessboard and an infinite number of L shaped tiles (of size 2x2) which may be rotated and placed, is it possible to tile the entire chessboard leaving just a single gap?

A: Yes. You can prove this by induction. Unfortunately, the solution didn't strike during the interview.

Q2. Delete a node from a Binary search tree.

A: Standard data structures question

Interview 3: 45 minutes

Q1. Print the elements of a matrix in spiral order (outside to inside). Make your code as efficient as possible. (an icebreaker question)

Q2. Given 2 numbers in base 10 with digits given in MSB to LSB order in a singly linked list, add the two numbers and return the result as a linked list in MSB to LSB order. Do this in < 4n operations on the given linked lists (including traversals) (this constraint was stated somewhat vaguely). Code up the solution. The more efficient the better. I gave multiple solutions to this problem (the first few methods had 4n operations).

The primary challenge in the interviews was the tight time limits within which we had to figure out solutions and code them up. Finally, I guess there was some CV evaluation from Mountain View and the offer letters materialized after a sleepless night for us. Congratulations Naman, Parth, Tanmay and Gunjan for also clearing Google. You guys rock!

Tune Meri Jaana Kabhi Nahin Jaana - Lonely (Emptiness) - IIT Guwahati - Rohan Rathore

2010-11-22T16:27:00.008+05:30

Update: Rohan Rathore and his tragic story is a hoax for sure. This is confirmed.

I've talked to my friends at IIT Guwahati and there is no record of such a person ever existing on campus. Nobody at IIT-G knew him and if a person dies in tragic circumstances, nearly everyone in the IIT knows it. The story about Rohan Rathore was created in order to gain views for a video on Youtube. So let us all put the "fake" Rohan Rathore to rest permanently as a person who never existed. Therefore, we can be very sure that the original singer of the song is Gajendra Verma. I'm leaving the original post below for archival purposes.

------ Original Post follows ----

I was introduced to this song by Sanat nearly a month ago and today, after listening to it again on Youtube, I really felt that I needed to transcribe its lyrics. It's such a soulful song that you can't help feeling sentimental after hearing it - especially since the IITian (Rohan Rathod) who wrote and sang it died of cancer 15 days after finishing this beautiful piece of music. Everywhere I've looked on the net, the lyrics have been littered with mistakes. This is my cleaned up version and hopefully it makes much more sense than the others.

(English Section)

Oh love of mine, with a song and a whine,

You're harsh and divine like truths and a lie.

But the tale ends not here; I have nothing to fear

for my love is a yell of forgiving and hold on.

In the bright emptiness, in a room full of it,

is a cruel mistress - my heart!

I feel this unrest, that nests all hollowness,

for I have nowhere to go and I'm cold.

And I feel so lonely yeah...

There's a better place than this: emptiness.

And I'm so lonely yeah...

There's a better place than this: emptiness yeah...

<alaap>

(Hindi Section)

Tune mere jaana, kabhi nahin jaana,

Ishq mera, dard mera

Tune mere jaana, kabhi nahin jaana,

Ishq mera, dard mera

Aashiq tera...

Bheed mein khoya rehta hai...

Jaane jahaan....

Poocho toh itna kehta hai -

That I feel so lonely yeah...

There's a better place than this: emptiness.

And I'm so lonely yeah...

There's a better place than this: emptiness yeah...

Also, for those who don't speak or understand hindi - here's a line by line translation of the hindi section:

Tune mere jaana, kabhi nahin jaana, (You, my love, have never ever realized)

Ishq mera, dard mera (my love, my pain)

Tune mere jaana, kabhi nahin jaana, (You, my love, have never ever realized)

Ishq mera, dard mera (my love, my pain)

Aashiq tera... (Your lover)

Bheed mein khoya rehta hai... (remains lost in the crowd)

Jaane jahaan.... (My dear love, wherever ...)

Poocho toh itna kehta hai - (... asked, he just says ...)

That I feel so lonely yeah...

There's a better place than this: emptiness.

And I'm so lonely yeah...

There's a better place than this: emptiness yeah...

Hope all of you enjoy this as much as I do.

What Microsoft is Today

2010-10-20T11:06:00.001+05:30

I read this on the LinkedIn groups' Microsoft current and ex-employees forum and it really touched my heart. I've worked (more accurately, interned) at Microsoft and I can understand the pain that he has felt. Read the mail below and form your own opinions about MSFT.

LinkedIn Groups

Group: Microsoft - Current and Former Employees
Discussion: I think MS is dying because of losing capability of innovation, losing capability to keep those talent people to work for her, and the fatal reseason of MS dying is Value of Closing" and "Isolated"

Here's my personal experience of trying to innovate at Microsoft. I spent 14.5 years at there. I'm one of the co-inventors of ClearType, I have some 20-odd granted US Patents, so I think I have some credibility...

Approximately 2.5 of my Microsoft years were the best years of my (long) working life. About 12 of them were the worst years of my working life - by a very long way.

I came to Microsoft in 1995 because I believed that with Windows and Office, it was the one company in the world best-placed to lead the transition from reading on paper to reading on screen which I could see was inevitable. Most of Microsoft thought I was crazy back in 1995 - "No-one will ever read anything longer than a short email on a screen" was the general consensus. Not so crazy now, eh?

My boss, Steve Shaiman, believed and supported the vision. We produced a strategic plan called "Read It Anywhere", and began executing. In 1995. We were many years ahead of ANYONE else. Then Shaiman left - after a run-in with his VP, I understand.

The group I had come to Microsoft to run was tossed into the Windows organization (and later the NT organization). I had six different managers in three years, none of whom cared about the plan, all of whom wanted me to roll over and let the circling sharks of other teams tear the group to bits by taking its best engineers...

I fought successfully to keep the group together - right up to Divisional VP level, twice! - because I still believed the mission was important. I took most of that pain myself, while keeping the group focused on the plan - and innovating.

In 1998 I was fired, and only rescued with six hours left to run on my jobsearch by Dick Brass, who was an outsider (and thus viewed as prey by most of his fellow-VPs). He had come to Microsoft at BillG's invitation to develop an eBooks project. TabletPC also came out of that team - but was forced to try to run a sprint while dragging a millstone behind it (Windows).

Jason Atlas has it right. Microsoft has become GM - or the IBM it used to ridicule. Ironically, IBM has rediscovered how to innovate, in the services space. If you'd invested in IBM a year ago, you'd have made a profit of 17%.

Microsoft will not die, at least not for a very long time. But it has become a plumbing company.

Microsoft has had no leader able to drive innovation for a very long time. BillG checked out a number of years before he officially left. And the Windows & Office teams learned a long time ago how to frustrate his calls for more rapid innovation. I watched it happen. It took TEN YEARS before ClearType was turned on by default in Windows. Oh, it was grudgingly put in XP. But it was buried so deep few customers ever found it.

If you read my 1999 paper, The Magic of Reading ( http://www.billhillsite.com/osprey.doc ), you'll see we laid all the groundwork for Amazon's Kindle and most of the other eBook software in the market today. Microsoft was there years before, and blew it.

I was one of the 2009 casualties. Microsoft was right to get rid of me, at keast by teir rationale. I couldn't find any way to get traction any more. I was just a spinning wheel. Now, I'm obviously biased. But I believe that when a company that knows how to innovate sees a team of smart people who're really fired up to change the world, it moves obstacles out of their way.

Microsoft did exactly the opposite...
Posted by Bill Hill

Comment &#187 Stop Following Discussion &#187

Are NoSQL implementations really faster than the usual SQL thing?

2010-08-27T04:00:00.000+05:30

This was the question that I received from France via Aardvark. Here's my response:

"Faster" when applied to software implies a number of things - including the quality of implementation (which can sometimes play a very significant role).

Firstly, it is unfair to compare NoSQL and Relational databases because many NoSQL implementations do away with many of the hard guarantees of the relational world. So even though you might get a speed boost because of that, you're compromising on durability or consistency in some cases.

Secondly, space usage is definitely a concern. Not everyone can afford the humongous disks that NoSQL implementations will invariably require (denormalization eats up space because of repetition - but this does not apply in all scenarios and can be mitigated with careful thought - YMMV).

Thirdly, nothing can beat RAM - so pure memcached implementations will beat a database anyday at the cost of durability of data.

In short, treat "fast" as a term to be used with caution in this scenario as you are essentially comparing apples with oranges. If you still wish to look at some figures, check out http://www.mysqlperformanceblog.com/2009/10/19/mysql_memcached_tyrant_part3/

Hope this helps.

This Blog is Officially in Hibernation

2010-07-25T23:38:00.001+05:30

Over the past few days (months?? year?) I've become just too busy to blog about anything of interest to anyone. That has left me with a number of tricks, tips, ideas and unfinished blog posts. It is high time that I officially post on my blog my inability to service it with content. For those of you looking to find me or to take my advice, please mail me at my email id that is there somewhere on the sidebar of this page. FB and LinkedIn are good ways to connect. That's it for now. Ciao!

Zigndog 3rd Session - Django

2010-03-31T23:41:00.001+05:30

Hey guys and girls,
I have the screencast nearly ready, but it is hugely boring and very very long. Not only that, it's very impossible to download because of the large file size. So, if you're interested, what is the max file size that you can download? Ping in the comments, I'll try and make it smaller.

Divye

The super duper not-so-secret recipe for a great Pasta

2010-03-17T14:29:00.001+05:30

Pasta in White Sauce

Okay, here goes the super duper ultra not-so-secret recipe to awesome indianized pasta created by the resident geek who writes on these hallowed pages.

Part 1: Preparing the pasta
1. Take a huge kadhai and fill it with sufficient water (sufficient = enough to cover all the pasta you will put into it later completely).
2. Add enough salt to make the water quite salty. Exact quantity doesn't matter too much here..
3. Start heating the water, put in the pasta (penne version preferably as it doesn't break easily) and bring to boil. The water will start frothing.
4. Keep the pasta boiling in the water till it grows in size and changes colour from hard, deep yellow to a lighter, softer, larger size (closer to off-white)
Acid test for this step: you are able to break the pasta easily with a tablespoon's edge.
5. Remove from boil and drain away all the water with a sieve. (you can taste the pasta to judge its saltiness if you like, it won't be much)
6. Typically, you should be in a position to directly add the pasta to the white sauce that you should have prepared in the meanwhile. If you keep the pasta out for too long, it might start to stick. You can avoid that by coating it with a little oil (similar to noodles).

But I guess you know all that... here's the recipe for the sauce:

Part 2: Preparing the white sauce
0. Cut carrots and beans into 2" long, thin strips. Using about a 1-2 teaspoon of oil and about 1/2 tsp salt, cook the vegetables in an open pan at high heat till they are ready to eat but slightly crunchy. These vegetables will be used in step 6 (can be done in parallel with the remaining steps).
1. Take a kadhai and put in 1.5 - 2 tablespoons of butter and start heating till the butter melts
2. If you want an indianized version of the pasta, now is a good time to put in all the spices - Ajwain for the flavour, some jeera as per taste (any other spices of your choosing). Fry them till they change colour slightly. Add about 1 tablespoon (about 3 teaspoons) of garlic paste freshly prepared from garlic cloves (critical) (erring and adding more is good, adding less is not). Fry till slightly brown and aromatic. Add salt to taste (make sure to account for the salt in the butter and the vegetables and the slight salt in the boiled pasta).
Reduce the heat and add milk as per the next step.
3. Add 1/2-1 litre of milk (do a bit of judgement here).
The quantity should be just enough to cover the pasta after accounting for the reduction.
4. Bring the mixture to near-boil at high flame and then add 1-2 teaspoons of dissolved cornflower (dissolved smoothly in 1/2-3/4 cup of water) to the sauce. This will cause the milk sauce to thicken slightly. Keep stirring the mixture to ensure no lumps form and cook for a minute or two.
5. Add 1-2 tablespoons of tinned cream (optional) and turn the heat down slightly for thickening. Simultaneously, add 3 cubes of grated cheese (where 1 cube is as per Amul's processed cheese pack), lots of oregano (to taste - about 3 to 5 heaped teaspoons), 3-5 cloves for flavour and about 1-2 teaspoons of freshly ground black pepper. Keep heating at slightly reduced flame, thicken for a short while (2-3 minutes (estimated) - the sauce will thicken further on cooling)
6. When the sauce is of the desired consistency but slightly more flu, add the vegetables prepared in step 0 and mix well.
7. Add the boiled pasta prepared separately. Mix well and cook a little so that the flavours seep into the pasta.
8. Pour into a separate container for serving, dust with oregano, grated cheese and black pepper powder (freshly prepared)
9. Garnish with a sprig of freshly plucked Tulsi leaves. Serve hot.

List of ingredients:
1. Carrots, Beans - as per quantity desired in the final dish (example values - 2 long carrots, about 10 beans) - cut into 2" long thin strips (french fries type but much thinner)
2. Penne pasta - I don't know the grammage exactly, but 1 big packet (use only 1/2 or 3/4 of it)
3. Butter - upto 2 tablespoon
4. Ajwain, Jeera - to taste (optional)
5. Garlic paste prepared fresh from garlic cloves - roughly 1 heaped tablespoon or slightly more
6. Milk (boiled preferably) - 1 litre
7. Cornflower - 2 teaspoons
8. Black Pepper (freshly ground) - min 2 teaspoons + more for garnishing
9. Tinned Cream - about 2 tablespoons (optional, but highly recommended)
10. Oregano - lots of it. 3 to 5 heaped teaspoons + more for garnishing.
11. Cloves - 3 to 5 (optional)
12. Cheese cubes (grated) - 2-3 cubes for sauce + more for garnishing
13. Tulsi leaves - for garnishing

Serves: 4

The standard disclaimers apply:
1. I don't take any responsibility should you try this recipe and it blows up in your face, leaving you much the poorer on an empty stomach.
2. All the measurements are approximate as I'm an experimental cook and not a theoretical one.
3. Should you so decide to go ahead, feel free to tell me of the results. I would love to know.

A few closing comments
To the Dieters: What are you doing here?
To the masochist dieters: What's the calorie count of this dish?

To the Geeks: Please learn to cook. It is an important survival skill that will serve you well in life.
To the CS Geeks: No, that fancy robot you've just programmed cannot cook this for you. Get up and do it yourself.
To those in Google/Facebook: Just get your fix from your in-house cook, will ya? Cooking this could prevent you from saving the world! :P

Take care guys! Until next time, Chef DK signing off!

How to enable Compile and Run for C/C++ files in gedit

2010-03-12T20:34:00.003+05:30

I never liked using gedit for programming because it needed extensive customization before it even came close to becoming a programming editor. However, those that are just starting out with linux will feel most at home in gedit. So here is how to enable "Compile and Run" functionality in gedit.

1. Enable the External Tools plugin by going to Edit -> Preferences -> Plugins as shown in the screenshot below

2. Go to Tools -> Manage External Tools and create a new Tool by clicking on the "new" icon near the Help button.

3. Name the new tool "Compile and Run" and press enter
4. In the coding area, paste the following script:

#!/bin/sh
cd $GEDIT_CURRENT_DOCUMENT_DIR
g++ -Wall -g $GEDIT_CURRENT_DOCUMENT_NAME && xterm -e "sh -c './a.out; echo Press enter to quit... && read KEY'"

5. Put in a shortcut key (eg. Ctrl + F5) in the shortcut key area
6. Set the save setting to Current Document
7. In the applicability setting, select C and C++

That's it. You're done! Press Ctrl + F5 to start off with compile and run. Happy coding!

PS: All the tools to make gedit programming worthy can be found in the blog posts here:
http://www.makeuseof.com/tag/top-plugins-to-extend-and-make-gedit-a-more-useful-text-editor-linux/
http://www.micahcarrick.com/09-29-2007/gedit-html-editor.html

Compile and Run For C/C++ programmers on vim

2010-03-12T20:15:00.001+05:30

If the file is named file.cpp or file.c, in the vim command mode just type in:

:!make abc
:!./abc

The first command compiles file abc.cpp to the executable file abc in the current directory. You can then execute it using the second command.

Alternatively, you could use something like :!g++ -g -Wall file.cpp -o file if you want to specify your own compilation options. (Anything more complex and you should be using a Makefile anyway).

Reprint of Zigndog Certificate

2010-03-10T00:59:00.000+05:30

This post should probably belong to the Zigndog site, but seeing that I have no time to update it, let me just post it here. I trust that most of you who are interested will be mailing me soon (common self-interest reasons) :)

To get your rewritten certificates, you need to perform the following tasks:

1. Get in touch with me on my Zigndog id (divye kapoor (at the rate of) zigndog (dot) com
2. Send in a scanned copy of your old certificate along with your correct spelling and the address to which you want the certificates dispatched.

3. I'll acknowledge the receipt of your email and dispatch the revised certificate soon.

4. On receipt of the revised certificate, please mail back the original certificate via speed post.

That's all folks!

Looking forward to your mails...

Chinese Intervention?

2009-10-22T11:28:00.000+05:30

Just on a light note, have a look at this screenshot of Firefox in an "embarrassing" situation. I wonder if it was because of the ever present Chinese... :)

Automatic Django Template Directory adjustment

2009-08-27T23:17:00.002+05:30

Django is that hot new MVC framework on the block that's kept me sleeping at night, quite unlike PHP. Yup, its that good! :) It's got wonderful features that make me feel - Yeah! Development for the web is still worth the grind! By the way, if you're not into Web Development and don't care two hoots about the difference between a framework and a library, this post is not for you - Mosey along now! Nothing to see here. ;)

Anyway, one of my few n00b questions to which I've never actually got a satisfactory answer is - How do you specify the template directory so that you can send your code to others and have it execute by manage.py runserver without any changes? The primary problem is the hardcoding of directories that is done in the settings.py file at the root of the project. After a bit of searching, I've come to a satisfactory solution and lest I forget it, I've decided to post it to my blog. Here's the code snippet.

TEMPLATE_DIRS = (
# Put strings here, like "/home/html/django_templates" or "C:/www/django/templates".
# Always use forward slashes, even on Windows.
# Don't forget to use absolute paths, not relative paths.
# os.path.realpath(os.path.curdir).replace("\\", "/") + "/templates",
os.path.abspath(os.path.dirname(__file__)).replace("\\", "/") + "/templates"
)

This seems to work most of the time, just let me know how it works out for you!

Geeky Stuff - The Linux Kernel Implementation of Pipes, FIFOs and other Filesystems

2009-08-27T23:02:00.002+05:30

I had to create a presentation on the implementation of Pipes and FIFOs on GNU/Linux for my Network Programming class (we're doing some background on IPC). Since I couldn't find any decent documentation online, I decided to dive deep into the Linux kernel code and see what devils were lurking beneath the pipe() and the mkfifo() system calls. The end result? A rather organized documentation of how pipes and FIFOs are implemented on linux (including some stuff about the pipefs filesystem). You can use this documentation in a variety of ways (including creating your own, new filesystem, for linux), but beware, I've made this complete documentation by reading the code. It elides a lot of informative stuff and might be incorrect in places. I would love to hear about anything wrong or misleading in this documentation. I undertake no responsibility if something happens to you, your computer or someone else's computer if you use/misuse the information provided. Please feel free to use the information as you see fit, but keep your eyes open and your mind working. I release this presentation into the public domain. However, I would love to hear if you liked it and used it somewhere.

The presentation is located here.

Life Updates after the internship

2009-08-27T22:47:00.004+05:30

Hello Web Surfer,

Firstly - Apologies! Its been a really long time since my last (reasonable) post and I've been neglecting my blog a lot. Mostly, this can be attributed to my internship at Microsoft which sapped me for over 2 months and then the brilliant work I've been doing at Zigndog. Forgive me for all the neglect and thank you for your brilliant patience. Given the long absence of updates, it is only fair that I give you a peek into the inner workings of my life (If you're not really interested, just skip on to the next post, you just might like spicy letters to the Dean :D ).

I've been tweeting a lot about DesignChef and Zigndog. If you don't already know of it, Zigndog is Puneet Jaggi's brainchild startup that working in the Web Development and Print Design space. Its working out well - Zigndog got 2 special mentions at the first DesignChef Logo Challenge and Second Place at the DesignChef UX Challenge. That's bagged us a cool Rs. 10,000 as a cash prize, not to mention a lot of positive publicity. (Hey! DirectI got so impressed by our work, we got contacted by them to do some work on rush basis). Of course, needless to mention that I was involved in the creation of the UX. But, collars up comments apart, serious kudos should go the entire team - Sampath, Rishabh, Sanat, Vikesh, Puneet and Priyanka Mdm. This was the outcome of our team effort and nothing significant could have been achieved without each one playing his part. Besides this, we've been working hard at ensuring that all our clients get satisfied. Something that's rather tough to achieve. (Trust me... Specially if you're planning to go for a startup someday)

Ok, here's the deal - I need to post some meaningful stuff that will document my internship and not leave you bored to death... First, some tech stuff: http://tinyurl.com/luc2zo - That's my internship presentation on Coalescing. Don't even bother reading about it if you're not interested (I don't have a transcript of my speech, so the slides are rather empty). It suffices to say that people liked it and I met my personal goal of getting across 60% of my work. Most people failed in their early twenties... :)

On the non tech front, here are a few images that document the really fun time I had in Hyderabad while sampling restaurants and enjoying the weekends. Thanks a lot everyone! It was great fun. Oh, and as a parting note - Happy Birthday Umesh!

This photo was taken at the Ramoji Film City. Its located about 2 hours away from Hyderabad but its a "must visit" for any tourist.

Taken at Tirupati. The golden cupola at the center is the sanctum sanctorum of Lord Balaji at the Tirupati temple. Many many thanks to P. Abhyuday and his family for making our trip such a memorable experience.

[Cinema Club] Appeal

2009-08-20T20:05:00.001+05:30

Dear Sir,

I would like to inform you about a number of irregularities that have taken place in the selection and subsequent notification of the secretary of the Cinema Club. The professors in charge have refused to consider my case and hence I am resorting to this final recourse of appeal to you.

To give you a little background, I would like to state my version of events. You may wish to verify this with any you deem suitable:-

1. A notice was issued wherein applications were requested for application to the post of Secretary, Cinema club on Monday/Tuesday - 17th/18th August.

2. The notice clearly stated that applications must be deposited in the office of the undersigned Prof. R. Prasad (of Electrical Department) by 20th August 2009. I complied with the same, having slipped in my application to his room at about 4:45 PM on 20th August 2009 (today). He was not present in his room and the timetable in his office showed that he was in a Lab. I visited some Labs in the department but was unable to locate him.

3. Just before 6 PM, I am informed, in casual conversation, by one of my batchmates that interviews for the post of Secretary Cinema Club have already taken place at 5 PM in the office of Professor R. C. Mittal (of Mathematics Department) and that he has already notified the selected candidate by issuing a letter to Mr. Somya Mohan.

4. I immediately rush to the office of Prof. R. Prasad where I meet him and ask him whether he has received my application for the post. I am informed by him that he has received the application but that it is too late as he has already conducted the interviews, the result of which has already been declared.

5. I appeal to him by stating that I have complied with all directions of the notices and all the information that was available with me. He refuses to consider my case.

7. At 6:30 PM at his behest, I have a telephonic conversation with Prof. R C Mittal wherein he states that he was made aware of my application by Prof. Prasad but was not willing to consider it.

8. On further conversation with Prof. Prasad, I come to know that information about the interviews was passed on to the applicants through a single person - Mr. Somya Mohan via the phone during the afternoon.

I would like to make the following representation:

1. I was not given a chance to represent myself at the interview for the post.

2. My application, though within time and present at the requested place was not accepted by the concerned Professor.

3. The interviews were scheduled before the deadline for applications had elapsed.

4. Only oral notification of the interviews was made and that too via a single student, who was also an applicant for the post and thus had significant self interest in the matter.

5. The results were declared before the deadline for applications had elapsed.

6. I was given no valid reason for the rejection of my application and my request for revoking/modifying/holding the earlier order in abeyance were summarily dismissed.

I feel that I have been unfairly discriminated against in this process.

Due process was not followed for the notification of interviews which were conducted without considering all applicants and before the expiry of the application deadline. Further, I wish to state that the interview procedure followed was arbitrary, unfair and opaque.

I request you to hear me out and take corrective measures as necessary so that my grievances are redressed. I shall be depositing a hardcopy of this application in your office tomorrow.

Thanking you,

Yours sincerely,

Divye Kapoor

4th Year

B.Tech (IDD) CSI

IIT Roorkee

--
At bottom, every man knows perfectly well that he is a unique being, only once on this earth; and by no extraordinary chance will such a marvelously picturesque piece of diversity in unity as he is, ever be put together a second time. -Friedrich Nietzsche, philosopher (1844-1900)

The Complete Story - The NSS Valedictory Fiasco

2009-04-27T02:52:00.002+05:30

Not everything went according to plan at the NSS Valedictory Function on the 25th of April. This is a chronicle of all the events that took place. This is the mail that I sent to the NSS group to explain the effect of their individual choices on the collective whole.

Hello everyone,

For those of you who don't know what has taken place, let me give you a quick summary. For those of you who do, you might have missed some of the following points. Please go through this carefully.

1. The Chief Guest for the Val function was Dr. Harsh Sinhval, Dean (Alumini Affairs)

2. The Guest of Honour was Dr. Gaurav Raheja - Institute Architect

Both of them had agreed to be present at the Val function at the last moment. They had been invited at around 5 pm the previous day.

The fiascos that took place:

1. Almost no one was present at the venue at the allotted time of 3:15 pm

2. Dr. Sinhval arrived punctually at 3:28 as the time given to him was 3:30 pm

3. 3:28 pm onwards - we push the panic button and start calling up everyone to be present at the Val function

4. 3:43 pm - Dr. Sinhval expresses his anger at the state of events and threatens to leave the function if the event doesn't proceed by 3:45

5. 3:44 pm - We start the event. Dr. Sinhval requests that all the doors to the auditorium be closed to prevent the entry of latecomers

6. We disregard his request. We keep on calling up people. We even request the Dramatics section to fill up the auditorium. They refuse. I call upon personal friends to help me out at this point of time. The NSS activity list is being read out by Shruti.

7. Close to 4:00 pm: Dr. Sinhval is asked to say a few words to the audience. He is furious. Total audience strength: close to 40 people.

A quote from his speech: "Normally, it isn't considered good manners to criticize your hosts but I am compelled to do this today. All the activities that you have read out to me hold no value. Anyone can write anything on a piece of paper and say that we've done this and done that. From an organization of 345 students, is this what is expected? Had I been the head of NSS, I would have clearly stated - those who don't attend this function will have their grades held back."

Just then, someone enters. Dr. Sinhval responds - "Aayiye, Aayiye. Mushaiyare mein tashreef rakhiye. Aakhir yeh mushaira hi hai na, koi function nahin." The entire executive team is looking shamefaced.

At the time of inviting him, Dr. Sinhval had expressed happiness at the work we were doing to teach students. He had asked us about the problems we were facing and had even offered to get a room for Prerna students to be taught at the ABN School on Saturdays. This is what he said then:

"Naga had told me about the problems you were facing in teaching students on weekends. I had thought of helping you in this regard but after what I have seen here today, I shall most certainly not be doing that. This is all that I had to say." He proceeds to his seat.

Can you imagine the plight of all those present there? Katiyar sir on the dias, sitting right next to him. Me and Naga sir down below - looking at the dismal empty chairs of the Civil Audi, desperately hoping that something can still be done, our hearts sinking with a feeling of deep loss. What should we do next?

8. Dr Raheja states a short story on the work that NSS has done. He maintains a calm disposition, but it is clearly seen that he's disappointed with the state of events. Meanwhile, Katiyar sir is desperately trying to calm Dr. Sinhval. Water arrives for the guests. There was no bouquet for any of them as the flower shops in Roorkee were closed.

9. Dr. Sinhval realizes our plight and requests the mic to say another story, this time a humourous one to diffuse the tension, but it is obvious that he is still simmering under the surface.

10. Naga sir was asked to announce the new team - Katiyar sir interrupts him and asks him not to do so.

11. The prize distribution for all the active volunteers takes place. Dr. Sinhval's comment: "I hope atleast they are present here". First two names called out are not present. Just to save face, we start sending other people up in case those that were being awarded were not present. Katiyar sir is given a memento for being the NSS Program Coordinator. There are no mementos for the Chief Guest and the Guest of Honour.

12. Prize Distribution over. I come up on stage and try salvaging the situation. I highlight the fact that the NSS Volunteer Awardees have worked close to 100 hours over the course of 2 semesters for a 2 credit course and that the people sitting in the audience aren't the "masses" working for grades, but those that realize the importance of their work and the service they are rendering to the nation, not out of pity, charity or kindness, but out of a feeling that every person in the country deserves as much as his country can give him.

14. I escort the guests down from the stage towards the refreshments. Dr. Sinhval refuses to leave the stage before me (as is his right, being the Chief Guest of the Event). This is an indirect slap to my face.

15. Katiyar Sir and the other Guests chitchat over refreshments but Dr. Sinhval refuses to give an assurance that he will continue to help us in the future.

16. The guests leave.

Let me make a few points here:

1. Why do I make such a big fuss about punctuality?

a) I realize the value of time. So do others.

b) This is what happens when you're not punctual. I know this. That's why I care.

2. Who is responsible for this mess?

a) I am - for leaving the management of critical aspects of such an important event to my juniors.

b) Naga Sir - for doing the same.

c) The new executive team - for not taking their responsibilities seriously.

3. Who is not responsible for this mess?

a) The first yearites - You have done exactly what I had expected you to do. You will prioritize 1 hour of sleeping or lazing around in the name of studying over coming for the val function.

Don't you think that your seniors might have spent many more hours getting the permission for the Civil audi, tallying the attendance, getting the certificates printed, writing the names of the people, getting the mementos, arranging for refreshments etc? Aren't their examinations on the same days as all of you?

All you guys had to do was to get up and come over for one hour - one single hour away from your studies too finally see and understand what you have achieved as part of NSS, what other cells had done and why you should be proud of your work and give a farewell to the current team. Of course, most of you weren't interested.

4. Who should bear the brunt of the consequences?

The NSS Team. They are now entrusted with the task of jumping through administrative hoops and loads of red tape to get permission for the simplest of things. By serving your self interests, you have inadvertently denied NSS a golden opportunity to have better relationships with the administration.

In any case, there is no use crying over spilt milk. You have done what you had to and we did what we could to save face. That's all there is to it. Thanks everyone for a very "memorable" farewell. It affected me to the depths of my heart... really. Thanks a lot...

Divye Kapoor

Ex-Joint Secretary

NSS

BUGS in DK's soul

2009-04-23T22:17:00.001+05:30

Recently received via fakemail.info:

DK's soul has bugs too!!!! Thats why its in Beta...

Thanks for the obvious creativity guys, you really cracked me up. :-)

The other mails were also fun, but some were unpublishable.

Keep mailing... Love to see your quote of the day in my inbox.

Google moving towards the "Google OS"

2009-03-11T15:28:00.003+05:30

Google Code Blog: Announcing the Native Client Security Contest

Google is moving slowly but surely towards its much hyped (but never confirmed) "Google OS". Google has just announced the Google Native Client Security Contest which challenges students and professionals from around the globe to have a look at the Google Native Client (or NaCl as it is better known in the docs) to find bugs and vulnerabilities. The person who identifies the maximum number of bugs can receive (in typical Google fashion) upto $ 2^13 . Great chance for all you hackers out there to earn some real m00lah.

However, its not the money that has caught my eye in this contest. The most eye popping thing about this piece of software are the screenshots that show how a full fledged 3D game - Quake, is running right inside of a browser. Its no wonder that Google claims that it will revolutionize the degree of interactivity available inside of a browser. Have a look at the screenshot below:

Another thing that you should consider doing is reading the research paper of the people who built this sandbox. The've gone to great lengths to ensure security of their sandbox by using static code analysis, code flow control and syscall interception. Its really worth your time.

GMail has bugs too! That's why it's in Beta.

2009-02-24T01:16:00.002+05:30

Check out the image below. A rare bug in the GMail interface.

My match with Vishwanathan Anand

2008-12-21T00:42:00.002+05:30

On the sidelines of the PanIIT Alumini meet being held at IIT Madras, Vishwanathan Anand - World Champion of Chess put in an appearance and played 14 boards of chess in a rapid mode of play. This was the sequence of moves played at table 4 by Narendranath (a 2000ish rated player and captain of the IITM chess team whom I met while playing chess at the InterIIT sports meet held earlier). It was real fun. Have a look.

White: Vishwanathan Anand
Black: Narendranath (IITM)/Divye Kapoor(IITR)

1. e4 c5      ; Sicilian Defense
2. Nf3 Nc6
3. Bb5 a6     ; push the bishop
4. Bxc6 bxc6 ; have a doubled pawn
5. O-O d5     ; try opening the doubled pawn
6. d3 Bg4     ; try pinning the Knight
7. h3 Bh5     ; push back the bishop
8. Nc3 d4     ; push the Knight and block the center
9. Na4 b3     ; Knight threatens entry
10. Bg5 h6    ; Push the Bishop
11. Bxf6 Qxf6 ; Bishop v/s Knight exchange
12. g4 Bg6    ; Break the pin on the Knight
13. Kg2 h5    ; Support the white pawns
14. g5 Qf4    ;
15. Qd2 Qc7   ; Push back the Black Queen
16. Nh4 Bh7   ; Push back the Black Bishop
17. f4 Bd6    ; Develop the Black Bishop
18. Nb2 Kd7   ; Break Black's Castling
19. Nc4 Raf8 ; Bring rooks into play
20. a4 Qb8    ; Start supporting the White Knight at the hole at b6
21. a5

Match abandoned due to lack of time.

Is Heysan.com a clickjacking attack, virus dropper or something else?

2008-11-11T21:26:00.007+05:30

For those of you who have been regularly using GMail, the recent arrival of unexplained chats from your friends might have piqued your curiosity. A chat lands up in your GMail Inbox claiming to have been sent to you by one of your friends bearing some sort of cheesy one liners and that you should click on the link to view them. Something like this:

Though usually I'm highly suspicious of these sorts of clicks, I went ahead and clicked it. (After all, Firefox, my favourite web browser has quite a decent track record as far as security is concerned).The site that opened up looked like:

Now, I'm not going to be giving up my Google Account password to any site that just asks for it. No Way! Not a Chance! Not even if it boasts of the Google Talk logo. But then, there are all kinds of people in the world and some are likely to enter their Google ids and passwords due to ignorance. In my opinion, this site is a fraud that is directly and obviously obtaining access to userids and passwords of GMail accounts and using them to perpetuate a mass mailing campaign from within the comfortable confines of your GMail inbox. The fact that there exists a hidden link to admob.com (a highly SEOed advert site - see image) by means of a 1px x 1px image, bolsters my gut feeling about this site. Beware all of you who get a link to heysan.com - I think that its just the tip of a very large iceberg. Recent reports of a click based vulnerability in all browsers is a further cause for tension. Be on your toes everyone! More information on clickjacking is available here.

The hidden links on the GTalk page is:

And the heysan.com home page looks like this:

All links on this page lead to login areas of different popular e-mail and IM sites. So beware the casual web surfer: this does not augur well for the web. Currently, the best known safety solution is to install the NoScript addon for Firefox and use it to disable iframes.

Permutations of a string containing duplicates (C++ Version)

2008-10-10T00:34:00.003+05:30

Update: This is part 1 of a 2 part series of posts that discuss generating all possible permutations/anagrams of a given string. This post discusses how to use the next_permutation function provided by the standard C++ library to generate the anagrams iteratively. The next post discusses a custom recursive implementation of how to achieve the same thing. See: Recursively printing all permutations of a string containing duplicate characters.

Have you ever thought of how to generate and display/print all possible permutations of a string (containing duplicate characters) such that every legal permutation appears atmost once in the final output, without taking a humungous amount of memory to keep track of all the permutations you have generated? This particular function utilizes a cool STL algorithm and generates all possible permutations of a string only once (whether the original string contained duplicates or not).

int dup_permute(char *str, size_t length) {
    int count = 0;
    std::sort(str, str+length);
    do {
        ++count;
        cout << str << '\n';
    }
    while(std::next_permutation(str, str+length));
    return count;
}

Of course, since the major work of this function is being done in the C++ standard library, an explanation of the standard library functions is in order.
First up is the std::sort function. Located in the <algorithm> header, true to its name, it sorts the given range of elements (in this case the string, specified by pointers to its first and last elements). std::next_permutation is a tough one to deal with. The working of this function is too convoluted to explain in a couple of sentences, so, I would recommend you look up this reference and this MSDN article. In short, next_permutation generates the next lexicographically ordered permutation of the given elements using no more than a constant amount of extra space. All that work is done using comparison, swapping and reversing a subset of elements in the array itself. Also, since there is no copying involved, this function is blazing fast. So, the next time someone asks for all permutations of a string, forget about recursion and look at this iterative version. Not only is it correct for the distinct elements case, it works even when the string does contain duplicates. If you liked it, don't forget to leave a comment.

Selected!!!

2008-09-17T23:23:00.003+05:30

After 5 hours of mind wrenching tension and reams of code later, I've finally been selected for the internship programme at the Microsoft India Development Center (better known as Microsoft IDC). The internship is going to last for atleast 8 weeks and I'll be getting accomodation for 15 days and travelling expenses in addition to my internship stipend. Looking forward to going to Hyderabad, anybody going to meet me there?

The 'Said' Problem

2008-09-17T23:18:00.001+05:30

I came across this cool piece of text on a patents website.

"The computer-readable medium of claim 23 wherein said workspace is used by a database system to create a plurality of run files, each of which contains a plurality of variable length records from said set of variable length records, as sorted by said database system using said workspace, said step of selectively removing comprises writing a next of the plurality of variable length records that are stored in said workspace out to a run file in a predetermined order, said method further having computer-executable instructions for performing steps comprising:

determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace;

creating one or more run files on a data storage medium; and writing out to said run file only those variable length record selected by said step of selectively removing subsequent to determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace. "

Now we know why we need lawyers for legalese, don't we? ;-)

Easter Egg in Google Chrome

2008-09-08T23:33:00.002+05:30

Try typing about:crash in the title bar of Google Chrome and see this cute cross eyed robot! :-)
Of course, you do know by now that Chrome is hottest new entrant on the browser block, don't you? Well, now you do. :-D

Have a look at this review of Chrome on ZDNet.

in.com - India on the world stage

2008-08-02T12:03:00.002+05:30

Its rather rare that you come across a site with content really geared towards Indians with a look and feel matching any world class website. Take a quick look at the layout and source code of sites such as CNN-IBN and Aaj Tak and you will realize that we are really retards as far as decent site layouts and navigation is concerned. However, in.com was a really refreshing change. The interface is quick and snazzy and the site runs on blazing fast servers - in fact, I would go as far as to state that I had a better experience with their quick registration and speedy interface than I had with GMail on Google servers. Oh and just not to forget, they've gone onto internet overdrive and I'm constantly receiving targeted ads that lead me to their site. Well, what can I say - you have me hooked! :-)

The first thing that I tried out was their radio service - its awesome! Have a look at the screenshot below:

Despite it being an obvious ripoff from last.fm, I really don't mind. They've got more Indian songs in such an accessible format that it took me less than 10 seconds to start listening to Kabhi Kabhi Aditi. The best part of it is that its free and delivers songs on demand and their Bollywood song collection beats the living daylights out of any other service on the internet. Thats not to say that they are lagging in the english songs department - there's plenty of fare for all metal and rock addicts. A point to note is that I did not receive any lag while switching songs and there were no annoying "buffering..." issues. A quick traceroute showed me that its because they are hosting the site on dedicated servers on the VSNL backbone. That gives a really stellar experience for Indians. All that money that's gone into making the site is really being spent intelligently.

The mail was not bad at all - a complete GMail ripoff - right down to the drop down contacts list. Have a look:

The cool colour combination, the smooth fonts and especially the news and radio services makes me feel that I'll be visiting it much more often. Also, the short and sweet id I registered for - divye at in dot com is the icing on the cake. I loved their service and if you are an Indian (or even otherwise), you will too. So, what are you waiting for? Rush!!! Go (listen to) Talli on this site ;-)

Enjoy Everything You Do

2008-07-31T14:10:00.002+05:30

Live the life of a dolphin,
Travel the world without fear,
Whether to the top of a mountain,
Or where the water ain't clear.

Fear not to push the ceiling,
Try to reach for the sky,
Go with the flow if you want to,
Or be left high and dry.

Speak your words with feeling,
Enjoy everything you do.
Play from dawn to the evening,
Is that not everything you do?

Follow the world in its footsteps,
Or make the world follow you.
Do everything with feeling.
Enjoy everything you do.

Bird of Fire

2008-07-31T14:04:00.001+05:30

Fly, Fly, Fly little bird in the sky.
You own the heavens - the Earth and the Sky.
Lie, Lie, Lie, asleep in the clouds,
Free from cares, from worldly bounds.
You creature of mirth, of joy abound.

Live, Live, Live, a life full of dreams,
Unchecked by dearth of form or means.
Pray, Pray, Pray for a life full of song,
For finding a rhythm to play along.
You creature of milk, to heavens belong.

Say, Say, Say, the words in your heart,
Bring a smile with a kind remark.
Day, day, day a day in your life,
Opens a door from formless night.
You warrior of words, of shape and light.

Inspired by - To a Skylark by P. B. Shelly

Wordle and SEO

2008-07-21T16:02:00.002+05:30

An image is worth a thousand words. This image is a tag cloud
generated by Wordle from the text at
http://www.drkapoorsclinic.com . I don't need to tell you
how such a map is helpful for SEO - do I?

And yes: despite my earlier post on Mac v/s Vista - that *is* a screenshot taken from my laptop running Vista. You might call me a hypocrite, I just call myself a pragmatist - if you can't beat 'em, join 'em. ;-)

Walking through your first template metaprogram in C++

2008-07-18T15:40:00.006+05:30

From the Wikipedia article on Metaprogramming:

Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data, or that do part of the work at compile time that is otherwise done at run time. In many cases, this allows programmers to get more done in the same amount of time as they would take to write all the code manually.

Unfortunately, metaprogramming is not directly supported by C++ and resources on template metaprogramming are few and far between. I'll try to document my knowledge of metaprogramming as I learn it and hope that it proves useful for one such as myself hunting the web for information.

First, lets get the preliminaries out of the way:

Templates are used to create generic code (but you already know that, don't you?)
Code like:
template<typename T> std::string to_string(T const & object) {
return object.to_string();
}
is used to allow the to_string function to be called on all objects that have a to_string() member function.
Template specializations are created to handle certain datatypes in a special manner (or in technospeak - to provide a custom instantiation of generic code)
So, code like:
template<> std::string to_string<int>(int I) { std::ostringstream o; o << I; return o.str(); } ensures that calls to to_string that take an int for a parameter will use the second definition of to_string and not the more generic first definition. This allows us to provide a string representation of an int even though it does not have a member function named to_string. Thus, the body of a templated piece of code can be changed completely from its generic counterpart in a template specialization.
The compiler always chooses the most specialized definition of a function. This is somewhat akin to function overloading. So, given a choice between to_string<t> and to_string<int>, it will always choose to_string<int> for an integer parameter.

Well, how does all this help?
It allows us to do a compile time recursion and that's what I'm going to show you.

Look at this piece of code:

template<int N>
struct factorial {

   static const long value = N*factorial<N-1>::value;

};

Doesn't that look dandy! Its that same old factorial function again! So, what's new? Firstly, notice that instead of templating the structure via a typename, we have chosen to template it over a compile time constant. So, creating an object of this structure will require code such as:

factorial<5> five_factorial;

But why would you want an empty object? Remember: static structure and class variables do not occupy any space in objects and factorial<N> has only static members. So, what's the use of the static member?
The static member allows us to directly access values that are calculated at compile time. In essence, you can think of it as the return value of the computation. Before we move further into the analysis, let me answer a couple of questions that can arise:

Where's the computation taking place?

It is taking place at compile time when the template is initialized/instantiated and its being done by the compiler while the templated code is being compiled. Effectively, the compiling process is the runtime for template metaprogramming.

Where's the recursion in the code?

The instantiation of factorial<N> requires the value of factorial<n-1>::value which is of-course a static member in factorial<N-1>. So, this template is also instatiated and the recursion takes place.

Sharp programmers might have noticed that there is no base case in this piece of code: You're right!
So, here's the base case:

template<>

struct factorial<0> {

    static const long value = 1; 

};

So, when the compiler tries to instantiate factorial<1> and comes across factorial<0>::value, it will choose this base case and terminate the recursion. Once all the constants have been determined, they are multiplied by the compiler and the result is stored in the resulting executable. So, the value of 5! can be used at runtime without any computation of any sort, all it requires of you is to substitute factorial<5>::value wherever you need it.

A side-effect of this evaluation is that all lower factorial structures are also instantiated. Thus, when you instantiate factorial<5>, you get for free the values of factorial<4>, factorial<3> etc. Also, use of factorial<4> later in the program will not cause additional template instantiations because C++ compilers follow a single template instantiation rule: viz. no template will be instantiated more than once. This allows for a very important optimization: memoization that's right memoization and not memorization (though the two are pretty similar). You can have a look at the Wikipedia entry on memoization for info, but for the impatient, it allows you to code a fibonacci number generator like this:

template<int N>

struct fibonacci_term {

    static const int value = fibonacci_term<n-1>::value + fibonacci_term<n-2>::value;

};

template<>

struct fibonacci_term<1> {

   static const int value = 1;

};

template<>

struct fibonacci_term<0> {

    static const int value = 0;

};

If you had coded an analogous recursive function for evaluation at runtime, you should have been spanked by your computer science/engineering professors because that's the worst way to evaluate the fibonacci series as it has a time complexity of O(2^n) which is exponential in the size of the problem. However, because of the one template instantiation rule, its perfectly alright to do this at compile time. While evaluating fibonacci_term::value , the compiler has already instantiated fibonacci_term and that instantiation is simply looked up from a table, thus saving computation time and making the compile time program linear in time and space complexity.

Meta-programming is not just about compile time computations and tricks like this. Its far greater application lies in the capability of manipulation of the C++ type system. Most metaprogramming techniques are applied to make libraries hide their implementations better and allow you to write simpler, cleaner code without reams of types in angle brackets.

Type manipulation tricks are best left to another blog entry. For now, you can check out:
[1] C++ Template Metaprogramming - Concepts, Tools and Techniques from Boost and beyond
This is a book by the authors of the Boost.MPL (the Boost Meta-Programming Library). The MPL has loads of tools to make metaprogramming easier as well as hacks to work around the deficiencies in various C++ compilers.
[2] The Boost TypeTraits library - This library makes type manipulation a breeze, thanks to the consistent interface and excellent documentation.

Hope you liked it. Comments always welcome.

The files for the examples are listed below. All of them have been compiled and tested using the Visual C++ 2005 compiler and should work with most other compilers. In case you have troubles, let me know.
[1] factorial.cpp
[2] fibonacci.cpp

The commplete source code including makefiles can be found here. A Jamfile is included for those who use Bjam.

I'm Back

2008-07-14T02:15:00.002+05:30

Hey all,
Its been ages since I last posted on this blog and its been rather sometime since this blog had been taken off the internet. However, I'm back on the internet after being *really* busy at college and the blog is back online.
Well, in the time my blog was offline, I was completing my second year at college and in the summer vacations was developing a website for my dad and mom's Ultrasound clinic. You can see the final result at their home page: http://www.drkapoorsclinic.com .

Mac v/s Vista

2007-08-25T20:55:00.000+05:30

With Apple now shifting to the Intel platform - the Mac has become another shark hungry for the market share being doled out by the beleaguered Microsoft Vista.
To quote from the Apple web site:

Why upgrade to Vista when you can upgrade to Mac? Especially when you can move all your stuff from an old PC to a shiny new Mac in less time than it takes to add the memory, hard disk space, and graphics card you’ll probably need to install Vista. Here are three easy ways to make your move.

That's a pretty strong statement coming from the Apple stable and yet another indication of the poor feedback offered by Vista users. Personally, I feel Vista is still just as secure as Windows XP from the user's point of view but more secure from the programmers viewpoint. The whole crux of the matter being that Microsoft forgot its end users while trying to implement new revolutionary (read: proprietary) technology for its programmers. With the .NET platform still stuck onto Windows due to the poor help offered by M$ in porting it to linux (for obvious reasons), Microsoft's credibility with the Open Source guys is going to the dogs - so much so that they have started an online campaign at http://badvista.fsf.org/blog. This is hot on the heels of Microsoft signing pacts with LG and Xandros that state that M$ will not prosecute them for any (perceived) patent violations for a period of 5 years, a deal that is similar to the one signed with Novell last year. IMHO, this is yet another tactic to prevent linux adoption by implicitly spreading false and misleading information (also called FUD) about linux. Have a look at http://www.eweek.com/article2/0,1759,2140955,00.asp for more info.

On a side note, its quite likely that Google is funding a hush-hush compilation of a linux distro to gain a foothold in the desktop space so more fireworks are likely soon. As it is, Google's new Google Desktop provides a sidebar for Win XP users, a combination with a good theming engine will give users lesser and lesser reason to upgrade to Windows Vista.

For people interested in more technologies (muck?) coming from the Microsoft stables, have a look at the Visual Studio 2008 (Orcas) beta 2 and Windows Server 2008 beta available for free download from here and here respectively and decide for yourself. However, don't forget to check the minimum system requirements, most likely, your PC is obsolete for these "revolutionary" technologies. (And I thought the most basic function of an OS was interfacing between the user and the hardware at minimum resource cost. Guess I was wrong... ;-)

ऑनलाइन video editing

2007-08-25T19:50:00.000+05:30

Planning to make those college videos into cherished masterpieces? Have a look at the great online tools for editing video. Check out this site. Give me a feedback on how you liked these tools.

AJAX और हिंदी

2007-07-13T23:13:00.000+05:30

हाँ! अब आप हिंदी में भी भी ब्लोग कर सकते हैं। गूगल में तो कुछ अलग ही बात है। इतनी आसानी से मैंने कभी हिंदी नही लिक्खी थी। चलो, इसी बहाने मेरी हिंदी कुछ और शुद्ध हो जायेगी।
इस लेख का मुख्य उद्देश्य है आपको AJAX नामक टेक्नोलॉजी (इसे हिंदी में क्या कहते हैं?) के एक अंग से परिचित करवाना। AJAX का पूर्ण नाम है Asynchronous Javascript and XML और इसी के मध्यम से मैं अभी इन्टरनेट के द्वारा ब्लॉगर के इस सुन्दर यन्त्र का फूलपूर्वक इस्तमाल कर रह हूँ।
दरसल AJAX द्वारा हम Desktop जैसी look aur feel web applications को दे सकते हैं। पर आज के लिए बस इतना ही। अगले लेख में मैं इस टेक्नोलॉजी पर ज्यादा विस्तार से बात करूंगा। तब तक के लिए शुभ रात्री, शब्बा खैर, और अपना ख़याल जरूर रखियेगा। तब तक के लिए नमस्कार। ;-)

2007-07-12T14:00:00.001+05:30

Firefox in Firefox!
Here's something of a "Do you know?" variety.
One of the great things about Firefox is that its interface is highly modular and creating an extension or a plugin is as simple as editing xml files and writing Javascript code (things most web designers do on a daily basis). Firefox renders its interface with the appropriate theme by evaluating an xml file. So effectively, Firefox renders itself by evaluating its own interface file and placing widgets as defined in it in a blank application window. Well, I just came to know that it's possible to load Firefox within itself by asking it to evaluate its own interface using a chrome:// uri. Don't be surprised - just try typing chrome://browser/content/browser.xul in the address bar and see the results. The new interface is a fully functional Firefox!
Now, for the more curious among you - the reason why this works is because the chrome:// uri is interpreted by the firefox engine as a reference to its chrome directory and the subsequent paths provided are used to navigate the inner tree structure. The xul file is interpreted as an interface and rendered as such, complete with all event handlers - giving you a complete browser within a browser. To see the innards of Firefox, open up the browser.jar in the chrome directory of your Firefox installation using any standard unzipping utility and look at content/browser/browser.js and content/browser/browser.xul to have a feel of how flexible my favourite browser actually is!
Enjoy!

2007-03-21T21:59:00.000+05:30

Looking at my blog, it just occurred to me that I have become very tardy in posting here. Its been over a month since my last post! Anyways, this is just to post the fact that my Bhawan Day concluded on 20th March and my room got trashed. Apparently, there is an age old custom of ensuring that the inmates atleast bother to clean their rooms once every year.
In a nutshell (for those of you who don't know), every hostel on campus organizes an evening of cultural events and a DJ. All inmates are allowed to invite 1 other person to the Bhawan Day (held at night, of course ;). Oh, I almost forgot - girls are also allowed to enter the Boys hostel on this day.
Coming back to the point, most people give their passes to their "Room Baaps" (seniors who have stayed at the room last year) and they end up coming with a few friends to their ex-room and trashing it. It only helps if you are a member of any student group like IMG or Watch Out. They come and finish off whatever is left of your room. Of course, the authorities have a field day after all this and they end up making a pretty penny from the fines imposed in the aftermath. I hope I escape a fine (The warden did read a quote written on the wall in fluorescent marker by one of the IMGians, so its all upto him now). I'll be putting up "beautiful" pics of my room here soon. It will make an interesting study - the Apocalypse and subsequent clean up. Suprisingly (or not, depending on how you look at it), my room looked cleaner after I ended up removing all the mess than it did before it got trashed.
Before I cleaned it up, it had quotes written on the walls with unconventional materials - red Close Up toothpaste, green Lifebuoy soap, white shaving cream, fluorescent marker (to name a few); the floor was littered with torn newspapers and water was on the matresses and quilts. Needless to say, I have to buy a lot of toiletries quite soon. After things quietened down around 10 PM, news came rushing over the airwaves - The Chief Warden is conducting a surprise check of all the rooms. All inmates are requested to be in their rooms or face automatic fines. Out came the dusters, the pail of water and off I went scrubbing... After the inspection, the day wasn't done - time and tutorials don't wait for trifles like Bhawan Days and finally, I went off to sleep, exhausted, at 2 PM...
This is my story, but let my faithful friend - the reader be a part of another one. IITJEE, the world's toughest engineering entrance examination, is going to be held once again to select another batch of students for the premier institutions of India. I give all those students giving this examination my best wishes and I wish them luck. Just spare 2 minutes and mentally send your blessings to all of these hardworking students, and don't forget to send a special small "best of luck" for students from my school - Loyola. Go Loyola!

2007-02-20T20:39:00.000+05:30

The Big Brother of the Internet: Google.
So you really like Google, use it for searching, check your mails on it, link to your friends on Orkut, blog away on Blogger, create web pages on Google Page Creator, organize images using Picasa, shop using Froogle, read news using Google Reader, publish scraps of info using Google Notebooks, edit documents using Google Spreadsheets, find maps using Google Maps, view your home using Google Earth, soon you will be operating on Google OS....

Doesn't this sound like a monopoly of sorts? Not that you are forced into opting for Google products, its just that there are no good alternatives. So, what does all this mean for an average guy? It means that everything about your online "personal" life has a record on some Google server and you and I can't do anything about it. (I mean, I doubt that sending a mail to Google, asking them to delete all your private data would even elicit a response.) It all depends on how much you value your privacy. For me, I value it a lot but because of Google's sterling track record, I'm comfortable in entrusting private information to it. But that doesn't stop people from worrying about what "computer analysis" can be done to your private data in order to "catalog" you in the pecking order of the internet. Anunay was bothered with the same thought and came to more or less the same conclusion.

Anunay has posted a very nice reflective article here and if you bother to "Google" - "Google as Big Brother" , there will be plenty of good articles that will tell you why you should be wary of Google. Check out this article on google-watch.org(there it is again, the 17th time in this article) that I liked because of its objectivity, though I don't agree completely with all its points. In the end, you have to decide about the level of trust you are willing to put into a "monopolistic" data warehousing company. For the more privacy inclined, have a look at Scroogle. Oh, and don't forget to educate yourself here.

2007-01-30T21:49:00.000+05:30

Ekta Kapoor had a reason when she named her serials with a K. K has a universal appeal. Have a look at Gopal's Blog on this topic: http://k-gopal.blogspot.com/2007/01/k.html

2007-01-30T21:31:00.001+05:30

As far as I have been able to discern, there is no law that states that momentum must be quantized. It is defined to be a continuously varying function dependant on the velocity of the particle according to the relativistic equations derived from the Lorentz Transformations. However, this article: http://www.nemitz.net/vernon/MOMEQUAT.htm on the web puts forth on first glance a convincing argument for the quantization of momentum. I haven't analyzed the mathematics in detail but can anybody spot some flaws?

2007-01-30T18:21:00.001+05:30

I recently received a forward mail from Utsav that has generated some debate. I am posting it below.

Forwarded Conversation
Subject: Fabolous Article abt India!!!Are we dreaming the correct future for ourselves!!!!!! DO read
------------------------

From: utsav kumar

Date: Mon, Jan 22, 2007 at 5:41 PM

I belong to life's batch of 1979 and as I grew up through the 1980s and early 1990s I was deeply embarrassed about India. About everything, our movies, our cricket team, our athletes, our products, our infrastructure, our poverty, our politicians and the whole damn system.

No matter what we did, we fell painfully short of potential. Time and again! It hurt because I wanted to belong to a big, strong nation that could kick some a** and not to some laggard.

But the story has changed, and how! Here I am in a brand new 2007, miles away from sweet home India, yet still closely following her story. Now they all say that it is not so much 'whether or not' as much as 'when' will India become a superpower, a world beater.

India is shining, India is poised and India is everywhere, so I hear. Now the embarrassment and the heartaches have been buried with the 1990s.

Instead now there is a swelling pride and a sweet anxiety as we roar back into being a nation in fashion. And I am very happy for India and for all of us Indians. I am 27 now and I pray that I can see India fly highest before I kick the bucket.

But here comes the twist in my tale. I no longer want India to be a superpower in the manner I wanted it to be when I was naive and without a broader perspective. I no longer want it to be another big and brawny US. I don't want it to be a superpower that is just made up of brain and brawn, that is GDP performance and military might.

Rather and more pressingly, I want India to have a heart. The heart of a superpower, a civilised country. Now what is the heart of a country? Let me try, humbly:

Having a heart, unlike GDP growth and a military beef-up, does not just relate to the macro-economic and political issues. Having a heart of a real superpower essentially has micro implications, for each of us. Each of us can soon belong to a mighty nation and all that but then what is the point of belonging to one if we indulge in or turn a blind eye to child labour?

Are we ready yet to ask for the age of our servants or avoid and report restaurants where the cleaners are boys who should be in school? I ask again, what is the big thing about belonging to a superpower if we continue to pelt stones at speechless stray dogs and cows? What is the big deal?

We can spit on the roads and throw the banana peel from a travelling car and still India can turn into what the world calls a superpower. The two are not corelated but then do we just want to be a mighty country and not care about our manners? We can buy a multitude of cars, bikes and look down on public transportation and still become a superpower. All our trees can make way for ultra modern townships. But then do we just want to belong to a superpower and pollute without caring about our environmental legacy for our children?

Are we ready yet to smile freely at random countrymen on the streets? Or if someone's car rams into ours are we ready to get out and ask, 'Are you ok?' instead of fisting the aggressor?

Are we poised to replace brutal ragging at our educational institutions with warmer welcoming gestures? Are we there yet, when we care to build local infrastructure that can also be used by handicapped people? Will we ever care enough for our country that we pick up our dog's poop when we walk it on the streets?

And will we dance on the streets again if India successfully tests another nuclear weapon? Are we ready yet to have a heart?

The time has come for us to become an economic powerhouse of the world. There is no stopping us now. But the time is certainly not here as yet for us to claim that we have a collective heart, the heart that makes a real superpower beat soundly. That's going to take a while.

Till then let us not kid ourselves at the prospect of becoming a superpower.

The task at hand is a lot bigger than the mere achievement of becoming an economic powerhouse and having destructive weapons. Let us be aware, lest we stop and rejoice as soon as we become the world's largest economy and stagnate.

Let's keep moving onto bigger things. Let's become a real superpower. A superpower that beats to a super heart.

Ravi Bhaskar is a software consultant based in Calgary, Canada.

--------
From: Indrasen Bhattacharya

Date: Thu, Jan 25, 2007 at 5:43 PM

Hi

That article has been written by a typical example of what the
BIGGEST problem with our nation is today. The guy who wrote this is
based in Canada. Why doesnt he come back to India like and do his job
for the country if he really cares instead of sending out emails like
that? He is one of those disgusting people like Arundhati Roy who said
- "If India becomes a nuclear power , I will give up my citizenship."
Would you rather have it, as this person seems to, that India
should have remained nuclearly handicapped and in a position to be
blackmailed by just about any rogue country like Pakistan or North
Korea ? AND this guy doesnt care even about the smaller problems like
poverty, illiteracy or child labour else he wouldnt be in Calgary. Its
very easy to send emails like that. Its hard to come here and do
something.
So, next time please exclude me from your prestigious list. Oh, by
the way "fabulous" is spelled in this way.
-Yours indignantly,
Indrasen

--------
From: Divye Kapoor

To: Indrasen Bhattacharya

Date: Sat, Jan 27, 2007 at 5:27 PM

Hi indi,
It looks like you feel really strongly about this subject. So do I. But my viewpoint on this message differs from yours.
To quote you:
"That article has been written by a typical example of what the
BIGGEST problem with our nation is today. The guy who wrote this is
based in Canada. Why doesn't he come back to India like and do his job
for the country if he really cares instead of sending out emails like
that?"
My opinion on this point is that you need not be in your country in order to participate in its upliftment. Take the case of the massive PIO and Indian diaspora present in the US that is flexing its muscles in order to ensure that some pressure is brought on the US Senate to ensure that Indian interests are preserved while passing the Hyde Bill. Their contribution is behind the scenes but it plays a part nonetheless.
Another case in point is the flourishing Indian culture in the UK. Not only has it helped remove the stereotype about India as a land of nakid fakirs and snake charmers, but it has also proved to be an enormous source of Repatriation of foreign currency to India, thus contributing to its booming economy.
"Would you rather have it, as this person seems to, that India
should have remained nuclearly handicapped and in a position to be
blackmailed by just about any rogue country like Pakistan or North
Korea ?"
Firstly, nowhere in this mail has he opposed India's testing of a nuclear weapon. He has used the fact that the testing of a nuke brought people out on the streets, rejoicing in our technological development. He has asked people in general whether they would rejoice with the same fervour if India tested another nuke. The real question being whether testing another nuke brings us any closer to the emancipation of the large mass of human society that lives below the poverty line in our country. The first nuke test served the purpose of a deterrent to nations that intend to use their military might to suppress us but any subsequent tests serve no purpose at all except as signals of our increasing proficiency in nuke tech.
"AND this guy doesn't care even about the smaller problems like
poverty, illiteracy or child labour else he wouldn't be in Calgary."
Note that he has mentioned child labour and our careless attitude towards our country in his mail. That would definitely not support your assessment that has does not care for the smaller diseases ailing our country. Also note that he categorically states that he has been following the "Indian story" ever since the 80's, so you can't brand him as an unfeeling expatriate.
"Its
very easy to send emails like that. Its hard to come here and do
something."
Again, I don't agree with your viewpoint. You don't need to do things on a massive scale in order to do something to help your nation. All you need to do to make a difference is to pay some conscious attention to the finer details in your day to day life and coach others to do the same. After all, you are the future of this nation. The bad guys will not be at the helm of this nation forever you know. You too can enter politics but I don't think you will. Why's that? Its because you don't want to fight the system. Sitting here in this country too, you can only crib about politics but might not even go and cast your vote (not now but when you are eligible) simply because you don't care about which bad guy heads the government. To phrase it in your words, its really easy to send such a mail expressing anger at an Indian settled abroad for not caring but it does pay a little to have a look at what you can do for your country, irrespective of your location. This mail is his way of stirring up discussion and its doing its job fairly well.
That's my humble opinion,
Please comment,
Divye

Huff!!! That is a really long post....Which side of the debate do you lie on? Do post your opinion.

2007-01-23T18:07:00.000+05:30

I recently posted a very intriguing and irritating problem with a C++ program on the GCC help group. A certain piece of (incorrect) code was returning a defined answer when compiled with DevC++ and g++ on linux. Have a look at the problem and the solution here.
If you are really interested in competing with the best at the highest level, come for Cognizance, IITR's tech fest. Plenty of programming opportunities (multiple programming events and great cash prizes). Make sure you check out the E&C department's and Maths Department's list of events.

2007-01-19T17:18:00.001+05:30

Yippee. A new template for my blog. I seriously got bored of the previous one. How do you like it?

2007-01-19T16:17:00.000+05:30

How many times have you wasted hours in finding good website templates? Google searches for "web templates", "free html templates" and the like give terrible results. I found a really good site that hosts a lot of Open Source Web Templates. Its really terrific and I'm not kidding. Kudos to Open Source and all the people who actively support it.

2007-01-09T17:22:00.001+05:30

A lot of people have been asking me about what they should make for the ISC Physics project. Well, all I can tell them and those who are here looking for more info is that I made a full wave rectifier. Its really easy and fun to make and the concepts of a diode are really cleared up. For more info, consult Wikipedia or Google: full wave rectifier.
While on this topic, I came across some good explanations about the internal working structure of a transistor. Its by an amateur electronics hobbyist but he does a good job on the whole. Check out his site.
Also, if you want to keep up with posts on this blog, you can add an RSS feed to your browser. The instructions to do this vary from browser to browser but in the case of Firefox, look for an orange icon in the title bar. In case you find any broken links, don't hesitate to send me a comment stating the problem.

2006-12-31T23:08:00.000+05:30

Firstly, with great regret, I have to say that my beloved phupharji, Sudhir Kharbanda, (my father's brother-in-law) left for his heavenly abode on the 28th of December, leaving behind fond memories with his entire family, the Kharbandas and Kapoors. His Chautha was held on the 30th at Mata Ka Mandir, Near New Friends Colony, New Delhi; the 30th also marked the completion of 2 months of life without my grandmother. It was a really sad day for me.
Moving on, it is holiday season and I wish you a Merry Christmas and a Happy New Year. I sincerely hope and wish that life in 2007 will be happier and more enjoyable than 2006 has been and may you reach (or atleast try to reach) the pinnacles of success that you have been aiming for. By the way, do have a look at those Wikipedia ariticles. Its amazing that Christmas and New Year have a different meaning for different cultures.
Pratik Dhaboo, a brilliant ex student of Loyola, is the webmaster for Medha 2007, a mechanical tech fest being held at BIT Mesra. Do visit the official web site and by all means participate if you like the contests and the prize money. ;)

2006-12-21T23:56:00.000+05:30

A discussion on the divinity of Christ, a chronicle of the rough and tumble history of computers, the continuing fight between the raw talent in open source and the hype of Microsoft and a very informative blog of an open source developer (Hacking for Christ) are some of the things that I have been reading. Have a look.

2006-11-30T15:56:00.000+05:30

What do you get when Microsoft sends you an e-mail on your gmail id?

Ans: Google's offer to invite Microsoft to Gmail!

2006-11-26T20:59:00.000+05:30

Which photo looks better, the coloured one or the black and white? I haven't found time to do proper photo editing in photoshop. Comments solicited!

2006-11-23T01:26:00.000+05:30

Yippee! I just managed to finish my Maths tutorial work. Except for some sums that were swallowed or unsolved in between, one headache is over! Now on to studying for Chemistry. Forgive this blantant self congratulation but I needed to blog my happiness. Chem on the 25th....

2006-11-20T12:19:00.000+05:30

I got so irritated by the maths tut that I didn't study all of yesterday. Instead, I watched "Sound of Music" - the hit movie of the 70s -80s (Have you heard of the song - Doe a deer, a female deer, Ray, a drop of golden sun....., its from this movie). It was a senti one and slightly old fashioned, but i enjoyed it. I'm planning to study today.

2006-11-17T17:14:00.000+05:30

Well, this is an update on the revision in syllabus. It has now been confirmed of sorts that the entire syllabus for the first year will be revamped for the incoming batch and all the rubbish courses like engineering graphics and thermal/material sciences will be made electives. The course load will be reduced and the new batch will have 2 computer programming courses - basic programming and data structures in the first year itself. There will now exist only about 6 core courses and the remaining will have to be chosen from about 19 electives. However, these changes in syllabus and content will not be propagated to our batch. Well, the juniors always have all the fun! Not fair!
End semester exams are from the 25th but the good news is that (assuming i clear the end sems), I will never have to sit in another chemistry and biotechnology lecture. :D I still have another semester of physics and 2 sems of maths to go, but this is reason enough to smile.
The bad news is that my physics practical exam went off very badly (300% error from the standard value and a maximum permissible error of 6%) and i have no clue about how my chem practs went so I really can't comment on it. I'll be back in Jamshedpur by the 10th of December and leave again on the 29th. New years day has to be celebrated in the Institute itself as we have classes from the 1st :( Those who are planning to be around in JSR in this time interval, please do comment. (Do get away from orkut, all of you!)
Another update is that the Cognizance team has been formed and has started working to make IIT Roorkee's Tech Fest a huge success. For those of you interested in engineering - you are invited to take part. Cogni should be held in Feb or March. Sponsors invited!

2006-11-13T15:55:00.000+05:30

Well, a lot has happened over the last month in my personal life. My grandmother, Shrimati Uma Kapoor, expired on 30th October and I went to Delhi for mourning. Also, we had Thomso, our cultural fest, featuring Shibani Kashyap, Zero, a Hasya Kavi Sammelan (Thahake) and a fashion show (Vogue) October and my mom's birthday was on the 29 with professional models from NIFT, Delhi, from 26th to 29th too.
I enjoyed all of these events in Thomso and participated in a salsa workshop too (with a fourth year student of a college in Kaithal - Geeta Mittal, who is now placed in IBM) but I made a mess of it as I really have 2 left feet. However, Dadima's death has left me with a feeling of loss...
Having rather mixed feelings on the happenings of this last month, and also due to shortage of time, I would rather not blog about my feelings. As for the present, I am loaded with tutorials as usual but a really nice thing that is happening at the institute is that we are being asked to fill up response forms for the course content and the effectiveness of the teacher. Needless to say, we are enjoying our chance to punch back anonymously at our teachers.
The inside news is that the content of the Physics course will change and the teachers are lobbying for reduction of the course load, specially for the first year students. I completely agree with them. Making us stay up till three in the mornings on account of finishing the course load is too much. We deserve some time on our own.
There, I'm rambling again. KV told me that I speak well but explain my points too much. Engineers should be precise. Well, that's my target for self improvement. That's all for now.
PS: All of you who visit my blog, please leave a comment so that I can know my regular readers ) (Not that there are many that is ;)

2006-10-03T18:55:00.000+05:30

Today was a day of rest and relaxation. I'll be going to UC to have its trademark Wednesday Dosas. I didn't do much today except waking up late and lazing around watching TV. I met Mishra sir in the evening and he was late for his class (a rarity I must say) so I couldn't talk to him for too long. Tank sir is out of town and he will be back on Thursday so I will meet him on Friday. I received a warm welcome from the faculty of Prerna Classes when I went over there just before classes. I met most of my ex-teachers. I'll meet my school teachers tomorrow. That's a short post detailing my activities of the day.
Ah, life is bliss at home - no tension, no fikr.

2006-10-02T21:47:00.000+05:30

Ok, I'm back in Jamshedpur. To echo the opinions of hostelers all over the world - "There is nothing like home cooked food." I went to a party tonight on the occasion of Vijaya Dashami and I had fun there. I was dead tired after my train trip and a restless night as I wasn't sure of the time of arrival of Neelanchal at TATA. I took Tipu out for a walk after 2 months (God, was he delighted at seeing me after such a long time) and got caught in the rain and came back drenched and dirty. But does anyone really care about that.
Don't know and don't care. I just have to write or type - however you see it. Coming back to the point, Soumya got impatient at being made to wait for so long for the next move in our chess series. Just for the record, the current status of the match is -
1. c4 e5
2. e4 c5
3. d3 Nc6
4. Nc3 ...
But I'm too tired to think up of any suitable reply. Any help would be welcome. Just comment on this post and constructive and destructive criticism is most welcome.
On my way back from Roorkee, I stopped by for a day in Delhi and met Anunay and Gopal (refer to last post to know more about him). Anunay is doing his B.Com(Hons) from Amity as there are a few problems with his admissions in Symbiosis in B.Com(LLB). He's free more or less and absolutely disgusted with the faculty teaching him. So note: All those considering Amity as their future, think twice. That reminds me - Abhishek Ghosh was supposed to be in Amity. Wonder what hapenned to him. I'll ask Arijit.
As for Gopal, he's founding a youth wing at the Rashtrapati Bhawan. Anybody interested in joining should keep a watch at www.presidentofindia.nic.in/youth This site is not yet up but it should be up soon according to Gopal. By going to Harvard, Gopal is depriving India of a wonderful and imaginative mind.
I met Mrinal today. He's doing well at Tank. If he keeps this up, he's well on his way to clear IIT-JEE next year. Hopefully, the new pattern should be for his benefit. That reminds me that I need to meet all my teachers while I'm here for the pujas.
Well, while on the topic of teachers, I just wanted to discuss my Mathematics sir. He is an enhanced photocopy of our most beloved NATO sir. He too insists on proper framing of solutions and showing all steps while solving the problem. He reminds me of NATO sir everytime he writes on the blackboard. Next update will include my interactions with my teachers.
Till then, Sayonara
Signing off... Divye
PS: That was a line ripped off from Lage Raho Munna Bhai.

2006-09-20T17:48:00.000+05:30

Ok. I'm already starting to behave like a bad blogger. I haven't come to the comp centre for nearly a week now and I seriously need to regularize this. Well, I met Gopal online today and he has reiterated that he is going to Harvard on a 125% scholarship to study "Economics and International Affairs" on an integrated doctoral programme with a non-degree granting programme in Energy at MIT (I might have jumbled the terminologies a little bit but you get the idea) without finishing his boards in India as a graduation is not a criterion for admission into Harvard. Oh, and he recently had a meeting with the director of IIT Delhi and his book on energy independence has just been listed on Amazon. I met Rutwik online too. Tarush, Rutwik and Karan are planning a day off from college. I hope they enjoy themselves and have some decent Indian food after the continental stuff they have been eating for the past month (They are only about an hour away from each other by train in the US). I don't know what's happenned to Ankur, I need to get in touch with him.
On another note, the match with Soumya has progressed another step. Let's see what move I get in reply. I scrapped plenty of people over a course of an hour and a half on orkut and I have a physics practical to get done before tomorrow and my stomach is rumbling with hunger. Time for a glass of milk and something to eat.
Just a random thought, a lot of people fall sick in hostel because they don't drink enough water. For all those reading this, just keep in mind to force down atleast 2-4 glasses of water with every meal, even if you don't feel like it.
That's all for now. Until next time, Ciao!
PS: Warning: Don't join orkut, it is highly addictive and a huge time sink. Trust me, I know

2006-09-16T21:19:00.000+05:30

I'm sitting in Delhi right now after having an anticlimax saturday. I started out with high hopes of having a fun day but a series of bad timings robbed the day of its flavour. I woke up at 8 today and got ready after breakfast by 11 or so. I then hitched a ride with Nonika, my cousin, to Nehru Place where I did some shopping and then came back with 4 chicken rolls. I called up Aku didi, who'll be joining Google sometime next month in HR and obviously demanded a treat from her. She said she would be home in GK by 4 and she was there by 3:15! We thought that we had a good chance of watching a movie but we got delayed in our departure to Saket and we decided to wait a little longer and watch Bas Ek Pal in PVR Spice but we delayed too much and we lost our chance to get a ticket there too and we ended up playing pool at Tayaji's place. There the lights went off and we returned home by 8:30 :( Anyways, another 1/2 day is left and I feel like sleeping so that's it for today. I'll make the most of Delhi while I'm here.

2006-09-13T15:34:00.000+05:30

Well, I got into an accident just after I posted my last blog entry. A scooterist, tearing down the main thoroughfare failed to brake and banged into me. Although nothing happened by the grace of God, I did realize that my life was precious and could be snatched away from me by a small mistake. Well, enough of senti stuff... I had another chat about E-Biz with Ashutosh. This new fangled concept of network marketing does not appeal very much to me. Also, I'm worried about the legal ramifications. As of now, I don't think I will join.
Soumya and me are currently playing a long distance chess match over e-mail. He's playing the "English Open" to confuse me as usual, but beware Soumya, I have played with plenty of good opponents here and I just might have improved a bit...
Tutorials and Practicals just keep on coming throughout the week. I just finished 2 tutorial sheets for today last night by 1 am and I am on my way to the 3rd. Test papers for the mid sem exams have been corrected and are being distributed. I am in the middle of my class in Maths with 21 on 35 and I have done ok in Physics with 20 on 25. Let's see how the other papers go.
I think tonight is going to be another long night with a huge physics practical to be completed for tomorrow.... Hmmm, maybe the load might seem less as now we don't have Saturdays as working days.
That's a long post for today. That's all the time I have on my hands now. See you as soon as possible.... (I don't know how many people have even seen my blog since it came online, I will have to publicize the link).

2006-09-11T16:42:00.000+05:30

Ok. Now onto business. Sushreet is going to Sri Lanka for the international stage of a computer competition. Congrats to Loyola! Also, Loyola has won Abacus for the sixth year in a row. Well, there is some pride to be felt for training the juniors pretty well (although I won't take full credit ;)
Today was an ok day in college with plenty of homework waiting for me. Results of mid semesters are coming out one by one. I got 17 + 4 = 21 in a maths test of 25 + 10 = 35 marks. See! I can add! Tutorials are left and Library books have to be returned (not that I read most of them anyways, but they were some source of help.) That reminds me - There are NO good fiction books in the library. What do these IIT R people think - engineers can't read fiction?
Anyways, that's all for today. I'll try and update this tomorrow. Atleast I can make it a diary of my college life....

2006-09-11T16:39:00.000+05:30

Ok people. I've finally chosen the template, twiddled with the font colours and uploaded the images and am ready to go! I welcome myself to the online publishing world! (I hope no one reading this blog will feel that I have lost my senses entirely, though I believe I might do so not too long in the future.) Hmmm, I think this is enough for the first post.