Blogs mature over time

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:

Tweet

Recurrences in Computational Complexity

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:

1. T(n) is atleast linear. This is because it already contains a cn term in the recurrence.
2. 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.
3. 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:

1. a T(nr) > b T(n(1-r)) for n > K1
2. a T(nr) = b T(n(1-r)) for all n > K2
3. 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!

Tweet

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

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:

1. A law unto itself, www.outlookindia.com, March 8, 2010
   http://www.outlookindia.com/article.aspx?264454
2. 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
3. No GM trials in State: Katti, Deccan Herald, July 20, 2011
   http://www.deccanherald.com/content/177877/no-gm-trials-state-katti.html
4. 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.

Tweet

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

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

Tweet

The FBI Chargesheet for ISI Lobbying via Americans

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

Tweet

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

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

Tweet

What is the difference between a mutex and a semaphore?

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!

Tweet