DeeKaying @ Nettle

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

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

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

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?

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