DeeKaying @ Nettle

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

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

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

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

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

Okay. This is another common interview question. The one line answer to this question is: "A mutex is a binary semaphore that can only be unlocked by the thread that locked it. It's primary purpose is to ensure single threaded access to a piece of code called the critical section. A semaphore, in contrast, is often used for cooperative signalling across threads, a feature that is explicitly disallowed by the construction of the mutex as a binary semaphore owned by the thread that locked it." 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 stag...

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, i t 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:...

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

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

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