Awesome day!!!!

Thanks Anshuman, Anirban, Anushray, Amit and Anup for being there and making it so much fun for me!!!!

Kerala: A short story

A short account of the excellent trip we(Sandesh, Pascal, Barbara and I) had to Kerala(God's own country).

20^th June, 2009: Left from Mumbai, Lokmanya Tilak Terminus at 11:40am by Netravati Express. The train journey was essentially uneventful with us eating stuff we had brought from home. We avoided the train food as much as possible since it is known to down your spirits.

21^st June, 2009: Anyhow, we couldn't avoid calling for breakfast when an undercooked dossa greeted our bile-infested stomachs and was probably digested. We got off at 2:50pm(the scheduled arrival time for the train.. surprise! surprise! the train was on time!!) at Ernakulam Junction. We did run into some (very little) trouble locating our driver for the trip(Pradeesh), but we eventually did find him. He took us to the first place we were supposed to go to: Kapithan Inn at Kochi. This is a nice home-stay run by a very friendly lady named Pushpa. The time spent there was really nice. We visited the beach, which has fisher-folk that use Chinese Fishing Nets to catch their prey. Kathakali dance performances take place every evening at 7pm. After a nice stroll, we decided to get something to eat. Finding a good eatery wasn't easy, but we did manage to find one called "Elite Inn". The waiter there was really over-worked but was good.... The food was good, and we ate well.

22^nd June, 2009: Breakfast was at Elite Inn, and we and headed off to Kumarakom for the House-boat stay in the back waters. This was really the bestest of times we had.... There were 3 people waiting on us, The Chef(Anish), the driver(Meneesh) and the third took over when the driver was tired. Frankly speaking there was nothing to get tired about, but what the heck!! And I guess these guys must be finding it slightly monotonous to do the same thing every time, and greet everyone with the same enthusiasm and show them around.... This however, was a truly amazing experience.... Neither words nor pictures would do justice to what we experienced on the house boat. The back waters are a very still mass of water where the house boat just slithered along beautifully. We had fresh sunari(golden) coconuts and good food all around.

23^rd June, 2009: Again, amazing breakfast and a very serene ride back to where we started off. This ended at about 10:00am. From here, we took the car and headed off to Thekkady. This was a slightly tiring and longish drive(about 4¹/₂ hrs). We had stopped at a small place to have some tea. These long drives on hills really get to me cause there are so many sharp turns and when you are turning on these roads, all the food in your stomach starts to move about, and you feel giddy and sleepy. Well, we reached our place of stay -- Cardamom Club. This is another heaven on earth. There are about 4 small cottages on a small hillock over looking a treehouse. Behind the cottages is a hill on which Cardamom Club's plantations reside. The porch(the hillock on which the cottages are) is also filled with cardamon, vanilla and pepper plants. There are also jackfruit, papaya and mango trees here. The staff(Lijo and Shibu) was really co-operative and the food was really awesome! We had mango juice and papaya from fruits that grew in their own plantations. There is a old lady that did the cooking. She had the most amazing smile.... It reminded me of happiness.... :)

24^th June, 2009: Went to a spice garden(Deepa Spices). Didn't like it so much. We would recommend other places like Abraham's Spice Garden, which is recommended by Lonely Planet. The one that we went to didn't show us much and the spices there were very highly priced. At 3:30pm we left for a boat ride in the Periyar Wildlife Reserve. We made it _just_ in time for the 4:00pm boat. However, Shibu had already bought tickets for us(you get them an hour before the boat ride) which is why we were able to go. The boat ride was nice.... It reminded Sandesh of scenes from Jurassic park. We didn't see to many wild animals though. We saw cows, bull, deer, pigs and some birds(the name of whom I do not know). The place closes at 6:00pm(which is also when the boat ride ends). We bought some spices after moving about in many shops and retired for the night after dinner.

25^th June, 2009: Left for Munnar. Stopped on the way at a Spice Garden that was a home-run place. Really liked this place. Just bought stuff from here. They have the plantation, their home and the factory in one place. They grow their own vegetables to eat as well!! Again, longish drive that I didn't like too much. However, Pascal stopped us on the way and we took a nice 2 hour break at the Kannan Devan tea gardens. We spotted some cow munching grass and not doing much ;-) On reaching Munnar(about 4:30pm) we had lunch at some restaurant. I don't remember the name, but it was alright. We reached the home stay(Aranyaka) at about 5:30pm. It was too late to move out after that because of the mist so we retired for the day. The person who owned and was managing the home stay was a lady named Poornima. The person who was entertaining us was named Suresh.

26^th June, 2009: We has good breakfast(tea, toast and omlette) and left at about 9:40am for Mattupatty dam. We thought there would be pedal boating out there, but there was only speed boating there. We were told that this time last year, the water on the dam was 120ft, but this time it was just 60ft, so there had been lesser rainfall this year as compared to last year. We were told that pedal boating would be available at the dam about 10km ahead. This dam is called Kundala Dam. We reached there to find out that we had not been lied to and in fact had pedal boats!! So, we hired them for 30min each(up to 3 ppl. in each pedal boat, but since there were 4 of us, we too 2 each). This was a really nice experience!! There were ducks in the lake too. Halfway, we decided to stay on for 30 min more. We were able to cover the whole lake :) After that, we went to echo point. There was nothing much interesting happening here[interesting incident with Barbara...]. Then we went back to have lunch. We hunted for some nice place and finally settled on Hotel Saravan Bhavan which we thought would be good. And it turned out to be an excellent place to have authentic South-Indian food. We would recommend it to everyone who visits Munnar.

27^th June, 2009: We had to start off early(about 8:30am) for Ernakulam Junction since we had a train to catch at 2:15pm. The trip to the station was said to take about 4hrs 30min. We bought halwa, chips and bananas on the way and reached the station just in time(about 15mins to spare).

28^th June, 2009: I didn't have any breakfast in the train, but had lunch. They had nice big kerala rice along with sambhar. I was really hungry at that time. When I reached home, I had khari puris, shrikhand, karela ki sabzi(bitter gourd vegetable) and daal(pulses). A truly relished meal!!!! I then topped it off with vanilla flavoured milk that I made with the vanilla that I had brought back from Kerala :) Ah! End of a really nice trip.... :) :)

Longest Common Increasing Subsequence

I recently came across the problem of computing the Longest Common Increasing Subsequence(LCIS) of 2 given sequences. What does LCIS mean? Given 2 sequences of integers, we need to find a longest sub-sequence which is common to both the sequences, and the numbers of such a sub-sequence are in strictly increasing order.

So for example, given the 2 sequences:

• 4,3,5,6,7,1,2 and


• 1,2,3,50,6,4,7

Possible common increasing sub-sequence of the 2 sequences above are:

(4), (3), (7), (6), (1), (2), (1,2), (3,6), (3,7), (6,7), (4,7) and (3,6,7).

The LCIS of the 2 sequences would be (3,6,7). It so happens that the 2 sequences above have a unique LCIS, though that may not always be the case.

Now, how do we go about computing the LCIS of 2 sequences in a reasonable amount of time? If we think a bit, we can come up with the recurrence:

LCIS_length(seq1, seq2, prev_elem) is equal to:

1. MAX(LCIS_length(seq1 less it's first element, seq2 less it's first element, first element of seq1)+1,
   LCIS_length(seq1 less it's first element, seq2, prev_elem),
   LCIS_length(seq1, seq2 less it's first element, prev_elem)).
   If the first elements of seq1 and seq2 are the same AND the first element of seq1 is > prev_elem.


2. MAX(LCIS_length(seq1 less it's first element, seq2, prev_elem),
   LCIS_length(seq1, seq2 less it's first element, prev_elem)).
   If the first elements of seq1 and seq2 are different.

Now, if we implement it just the way it is, it is going to be quite expensive to compute the LCIS_length for any sequence having a length of more than say 20 elements. So, we want to use an approach which would work for larger input. On further thinking, we think that a faster(polynomial time) approach is possible.

Let's lay out both the sequences along the first row and column of an nXm matrix, where n and m are the lengths of the 2 sequences given.

	4	3	5	6	7	1	2
1
2
3
50
6
4
7

Let's define each cell to hold the length of the LCIS ending at the row(or column) that that cell is defining. For example, cell [6,1] will hold the length of the LCIS that ends with the number 4. The cell [5,2] will not hold any meaningful value since there can be no sub-sequence that ends with both 6 and 3. Similarly, the cell [7,5] will hold the length of an LCIS that ends with the number 7.

What we will do is we run 2 for loops, one for the row and one for the column, and each time we find a match between an element in the top row and the left column(i.e. The input elements), we will try and find some sub-sequence computed till now that can be extended by the number that that cell represents.

It should be clear by now that the number that the cell [x,y] represents is the number in the first column in the row 'x' OR the number in the first row in column 'y' ONLY IF both these numbers are the same. For example, the cell [2,3] can NOT represent any number, whereas the cell [3,2] represents the number 3.

A sub-sequence that can be extended by a number in cell [x,y] will always lie in the matrix of which the cell [x-1,y-1] is the right-bottom most cell. Let is refer to such a matrix as the candidate matrix for cell [x,y]. For example, we have highlighted all the cells which can have potential candidate sub-sequences that can be extended by the cell [5,4](which represents the number 6).

	4	3	5	6	7	1	2
1
2
3
50
6
4
7

Let's start working out a solution row-by-row.

We need to remember that while processing the 1^st row, there is NO sub-sequence that can be extended by any sub-sequence that ends with a number in the first row! This would be the situation after we finished processing the first row.

	4	3	5	6	7	1	2
1	0	0	0	0	0	1	0
2
3
50
6
4
7

When processing further rows, we check the candidate matrix of each cell being processed, and always extend the LCIS in the candidate matrix that ends with a number less than the representative number of the cell being processed.

When processing the 2^nd row, we notice that a sub-sequence ending at 2 can extend a subsequence ending at 1 because that sub-sequence is the LCIS that ends with a number less than 2 and lies in the candidate matrix for the cell [2,7].

	4	3	5	6	7	1	2
1	0	0	0	0	0	1	0
2	0	0	0	0	0	0	2
3
50
6
4
7

Similarly, after processing all the rows, our matrix looks like this.

	4	3	5	6	7	1	2
1	0	0	0	0	0	1	0
2	0	0	0	0	0	0	2
3	0	1	0	0	0	0	0
50	0	0	0	0	0	0	0
6	0	0	0	2	0	0	0
4	1	0	0	0	0	0	0
7	0	0	0	0	3	0	0

To find the LCIS, we search for the largest number in the matrix, and that gives you the length of the LCIS and also the number at which such an LCIS ends. To trace the LCIS, we need to find the largest number that lies in the candidate matrix of the cell to which this largest number belongs. In the figure below, the cell and candidate matrix have been highlighted in green and yellow colours respectively.

	4	3	5	6	7	1	2
1	0	0	0	0	0	1	0
2	0	0	0	0	0	0	2
3	0	1	0	0	0	0	0
50	0	0	0	0	0	0	0
6	0	0	0	2	0	0	0
4	1	0	0	0	0	0	0
7	0	0	0	0	3	0	0

Tracing thus, we land up with 3 cells(marked in green).

	4	3	5	6	7	1	2
1	0	0	0	0	0	1	0
2	0	0	0	0	0	0	2
3	0	1	0	0	0	0	0
50	0	0	0	0	0	0	0
6	0	0	0	2	0	0	0
4	1	0	0	0	0	0	0
7	0	0	0	0	3	0	0

The LCIS is just the numbers represented by the cells marked in green, when taken in increasing order of their value. i.e. (3,6,7).

The complexity of the approach presented above is O(n⁴). Can we bring it down?

If you notice, you will see that for each index representing numbers in the top most row, there is a unique integer associated with it. For example, indexes 1,2,3,4 are associated with numbers 4,3,5,6. There is always one integer associated with every such index. If we think a bit, it should be clear that whenever a CIS ends at some such index, and another longer CIS also ends at that index, then it is sufficient to just keep the larger of the 2. This is because the way in which we are processing the input(row-wise) allows us to track just the LCIS ending at any index.

If we adopt such an approach and use an auxiliary array to hold the LCIS ending at every such index, we land up with an O(n³) solution since we now need to scan just a single array for every element instead of an entire matrix.

However, if we think a little bit more, we can see that we don't even need that scan, since we can always maintain(for every row scanned), a single variable holding the length of the LCIS that the number(N) in the first column of that row can extend. Whenever we encounter a cell which has the same representative number(N), we store a number one more than an LCIS that can be extended by this representative number of such a cell. This brings down the complexity further to O(n²).

Re-constructing the LCIS can be trivially accomplished in time O(n) if we use extra space to the order of O(n²) and this is left as an exercise for the reader.

A cool definition of money....

Money is what it's function is....

Effective Delegation

I realise that one thing I need to learn, and learn fast is how to effectively delegate responsibilities to others. It is truly an art. How to pick someone for a task such that the probability of it's successful completion are upped significantly. Firstly, I think I need to be confident that I can trust someone with a certain task, and once that is done, how to choose that someone such that there is enough internal motivation for that person to run that task to completion.

Delegation solves a lot of problems if done well.

Some questions:
[1] What to delegate.
[2] When to delegate.
[3] Whom to delegate to.
[4] How much to delegate.
[5] How to create/detect internal motivation for effective delegation.

The Ticking

Often have I seen this line
That people are a slave to time
and when hey miss their train divine
they seldom cry but often whine
But they will when they think it fine
wait outside a royal dine.

And in the morn, when they do tick
get up they will very slick
for when they hit the ticking clock
like the feathers they will flock.

If at the time their path you block
won't they spare a living stock
and ruthlessly they will knock
for they fear the dreaded dock.

Nature hath it's living foes
and friends they o become galore
When they adorn their pretty robes
That do negate it's wily woes.

GIGO

Sometimes, the the title of a post doesn't quite describe what the post is all about. I think this post is a classic case of the above.

I'll try to keep it as simple as possible.

Suppose you are writing a program to compute the factorial of a number, you would also add a function to find if a string is a substring of another string, or check if a string is a palindrome? If you answer "yes" to any of the above questions, I would surely like to see you actively use the above in your program. For the rest of you un-interesting lot(Rule:0 of blogging; never lower the self-esteem of your readers), I would like to ask you if you would eat a packet of biscuits just because it was available for free. I'm guessing you wouldn't eat anything unless you were hungry, and if you consider biscuits as not belonging to the class of "healthy foods", you probably wouldn't eat those as well.

Maximum Atiguous Sum of a Sequence(Array)

Let me first explain what the question is.

Given an array(a sequence of non-negative integers), we need to find that subsequence of this sequence such that:
1. No element in the subsequence is adjacent to any other element in that subsequence in the original array(atiguous).
2. The sum of the elements of this subsequence is the maximum for any subsequence of the array which satisfies (1).

I was asked this question in an interview but was able to come up only with a very inefficient solution for it. That solution consisted of enumerting all possible subsequences which satisfied (1) and find the one that gave the maximum sum. Only after a week did I come up with a solution that is Linear in complexity, and examines each element of the array just once.

I present it below and leave it up to the reader to modify the solution so that it works for negative integers as well. Hint: In case all the numbers are negative, the solution will contain no elements and the value of the maximum atiguous sum will be zero(0).

But before I present the solution, let me discuss how I got to it.
For the longest time, i was under the impression that the only solution that could exists would be the one that consisted of enumerating all sets with atiguous elements. However, on thinking more on it, it seemed that the solution could be improved because if you see, you must choose 2 out of every 4 contiguous elements, whatever way you look at it. Also, you may choose 1 or 2 out of 3 contiguous elements. Similarly, you could choose 0 or 1 out of 2 continuous elements. This means that in the worst case we will have a solution consisting of abs(N/2) elements for a sequence of N elements, and in the best case we have a solution consisting of abs((N+1)/2) elements.

If you solve this problem using the enumeration method, but continuously adding elements to a smaller sub-sequence, you will notice that the best solution involves choosing either the sum 2 elements later or the sum 3 elements later; adding it to the current element, and saving the maximum of these 2 values as the maximum sum up to the current element with the current element as a constituent. At the end of this exercise, the final solution is the maximum of the 1st or 2nd element(considering that we are working backwards).

import java.util.*;

public class MaxAtigSum {

    static private Vector
    getIntegers()
    {
        Vector ret = new Vector();
        Scanner sin = new Scanner(System.in);
        while (sin.hasNextInt())
        {
            Integer val = sin.nextInt(); 
            ret.add(val);    
        }
        
        return ret;
    }
    
    public static void main(String[ ] args)
    {
        Vector ints = getIntegers();
        Vector soln = new Vector();
        
        // Pad the array with 3 integers more than the ints array.
        System.out.println("Size of input: " + ints.size());
        for (int i = 0; i < ints.size() + 3; ++i)
        {
            soln.add(0);
        }

        for (int i = soln.size() - 4; i >= 0; --i)
        {
            soln.set(i, ints.get(i) + Math.max(soln.get(i+2), soln.get(i+3)));
        }

        System.out.println("The maximum atiguous sum is: " + Math.max(soln.get(0), soln.get(1)));     
        
    }
}