Showing posts from June, 2011

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

What is the difference between a mutex and a semaphore?

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

An approach better than Pancake Sorting for a restricted sort

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:  swap(

A combinatorial game problem

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

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

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

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

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