Masala Matrix

Just a ready reckoner for me to look up to figure out how vegetables and lentils are made at my home.

Recipe	Fat	Rai (mustard seeds)	Jeera	Methi seeds	Hing (asafoetida)	Green chilli (whole)	Kadi patta	Haldi	Salt	Ginger paste	Dhania and jeera powder to season
Dudhi (bottle gourd)	Ghee	No	Yes	No	Yes	No	Yes	No	Yes	Yes	No
Tendli	Ghee/Oil	Yes	No	No	Yes	Yes	No	Yes	Yes	No	Yes
Karela (bitter gourd)[1]	Ghee	Yes	No	No	Yes	Yes	No	Yes	Yes	Yes	Yes
Dudhi + Dal (chana or tur daal)[2]	Ghee	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No
Cauliflower (fool gobi)	Oil	Yes	No	No	Yes	Yes	No	Yes	Yes	No	Yes
Cabbage (patta gobi)[3]	Oil	Yes	No	No	Yes	Yes	No	Yes	Yes	No	Yes
Tur Daal[4]	Ghee	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No
Aaloo mutter and tomato sabzi[5]	Ghee	No	Yes	No	Yes	Yes	Yes	Yes	Yes	No	Yes
Pumpkin (bhopda) sabzi	Ghee/Oil	No	No	Yes	Yes	Maybe	No	No	Yes	No	Yes
Fanshi (french beans) sabzi	Ghee/Oil	Yes	No	No	Yes	Yes	No	Yes[6]	Yes	Yes	Yes
Moong daal (yellow)	Ghee/Oil	Yes	Yes	No	Yes	Yes	Yes	Yes	Yes	Yes	No

[1]: Also put jaggery(gud), kaju(cashew) and kishmish(sultanas).
[2]: Also put jaggery(gud), kokam and corriander leaves to season.
[3]: You may optionally add tomatoes halfway through cooking the cabbage, and also add jaggery(gud) if you add tomatoes.
[4]: You can also add jaggery(gud) and kokam. It gives a very good taste to the daal. If you don't want to add gud and kokam, you can add lasun(garlic) to give it a nice taste and aroma. A 3^rd option is to add tomatoes. If adding tomatoes, leave out the kokam, but you should add jaggery and may optionally add garlic.
[5]: You can also put a bit of jaggery(gud) into this preparation.
[6]: Add Haldi only if you are adding potatoes to the sabzi.
* Dhania powder is generally added only to vegetable preparations and not to daal preparations.

Online hindi dictionary

I've been trying to find an online hindi dictionary where I can enter the text in english, and the system transcribes it and searches for the meaning. However, the best results I have got are by using google's transliteration tool(http://www.google.com/transliterate/indic) followed by a google search for the resulting word.
That apart, this site: http://www.websters-dictionary-online.org/ seems to have a lot of words. Make sure you choose the "non-english" option when you search.

Lip-smacking Rasgulla recipe

I have tried for long to make rasgullas that taste like the ones I had a Ganguram's in Kolkata. I tried buying rasgullas from many shops, and tried making on my own in the hope of being able to reproduce that taste and texture that had lulled me into have a lot many Rasgullas that rainy day in Kolkata, but to no avail. None came even a close second.... Then, I read somewhere the milk that is curdled should be curdled slowly, taking care not to shock it, so I decided to try it out.... The rest is history....

The secret of making good, no GREAT tasting rasgullas is in what milk you use and how you go about curdling it and then processing it. Every step is very important, but I wasn't able to get the 2^nd one right for quite a while. I finally tasted success (and moth-watering rasgullas) after a long time yesterday. I'll mention how you can go about reproducing them at home....

1. Buy cow's milk for making rasgullas. 3.5% to 6.0% fat content is alright. Do not get low fat milk


2. Boil it till about 10% of it boils off, taking care to not let it stick to the vessel. To ensure that, keep stirring as you boil it


3. For 1 litre of milk, you will need about 2-3 tsp of vinegar or about ³/₄^th of a lime's juice. IMPORTANT: Dilute this juice in about 1 cup(240ml) of water


4. Now, slowly keep adding this juice to the boiling milk, making sure to stir all the time. You can add about ¹/₄^th every time, and stir for a minute. Do this about 4 times, and keep stirring and heating the milk on a low-medium flame. The milk should continuously keep curdling


5. The milk is completely curdled when it separates into while solid and a greenish liquid


6. Make sure that you do this curdling VERY VERY slowly, otherwise the paneer will result in rubbery rasgullas


7. Now, separate the solid part(paneer) using a muslin cloth and squeeze out as much water as your possibly can. You can wash the paneer to remove the acidic part and squeeze out again, as much water content as you can


8. Let this paneer dry up for about 30-45mins


9. Now, you can follow any standard rasgulla recipe that tells you to knead the dough, form balls and cook them in boiling sugar syrup. However, I would like to clarify a few things


10. The ratio of sugar:water in the boiling syrup should be 1:6 or lesser. I have heard some people boil the paneer balls in just water


11. Make sure you roll the paneer balls tight and their surface is smooth. You can smear a bit of ghee(clarified butter) on your hands while rolling to ensure that they don't stick to your palm, and result in smooth balls

Use these rasgullas as rasgullas by dipping them in 1:2(sugar:water) syrup or by squeezing out the water(on cooling) and dipping them in rabri(to make yummy rasmalai!!!!)

Some lessons learnt

I have been working closely with this person called "Ramki", and have learnt a lot of interesting things from him that I wish to share. I don't know if I'll keep appending them to this post or create a new one each time. I guess it depends on my mood and the context and other such stuff....

1. Never use filenames or variable names in an application that have the name of the product in it. If you ever decide to change the name of the application, you'll have to change all those file and variable names too. This can be a nightmare.


2. When creating database tables which hold the email address of the user, also use a unique user ID. This allows users to change their email IDs when they please. If you use the email ID as the primary key(like how I was going to), it would not allow a change of email address in a cheap fashion. You would probably have to do an ON UPDATE CASCADE, etc.... and it would be quite an expensive operation.

Sita Sings The Blues

I have to start off by saying that "Sita Sings The Blues" has to be one of the most influential movie I have ever seen. In the sense that it has prompted me to notice and think about a lot of things, and I think especially since I am from India.

There are many aspects of the movie I really like and I'll try talking about each one in as much detail as I feel necessary.

• Lots of things have been left to the imagination of the audience even though a lot many have been explained by way of the random conversations that happen between the 3 narrators in the movie. I think it was very natural to make them say the things that they did, and the way that they casually argue with each other. Also, the conversations weren't casual enough to call them loose.


• The music given is quite apt and makes you want to listen to it more often. The title track "Sita in Space" is trance-like in nature and makes use of instruments that sound Indian as well. I felt that the way Lord Rama is first shown being waited upon by Sita and the last scene which has the same scene with the roles reversed is quite an outstanding and representative of a lot of things.


• The way that all the characters and their relationships to each other are shown upfront is something really neat. There have been times when I've seen movies and only towards the end have I fully understood how each of the characters are related to each other(when the story depended upon the viewer knowing these relationships up front).


• I found the scene is which Kaikayee is shown to be a nurse taking care of Raja Dashrath quite hilarious.


• There is another scene in which Nina is shown almost completely undressed, sleeping by her husband's side and her husband wants nothing to do with her when we hear a dog barking in the background. This was a scene that I was most impressed by because it felt so real, since that is exactly what I hear at many places(a dog barking in the night time). The level of attention to detail at places in the movie is really commendable!

---

This is a post in progress, and I shall keep updating it regularly.... Till then, you can watch the movie for free here. The song "Sita In Space" is really nice....

Garlic and Herb Chapati

As always, I'm a bit lazy and don't want to spend time baking bread(it is a very long and drawn out process). However I felt like having focaccia(yes the yummy bread with herbs, garlic and loooots of olive oil), so I decided to make a similarly flavoured chapati and see how it turns out.

Ingredients:

Whole Wheat Flour:	2 cups + more for dusting
Water:	Enough to make a really hard dough(we'll soften it up using lots of Olive Oil!!)
Softened Salted Butter:	5 Tbsp
The Best Extra Virgin Olive Oil that you can get your hands on and afford:	5 Tbsp
Mixed Dried Herbs(Parsley, Basil, Oregano, Rosemary, Thyme):	1-2 Tbsp
Salt:	1/4 tsp or to taste
Fresh Garlic Paste(it needs to be FRESH!!):	of about 10 cloves
An appetite:	as much as you can squeeze in!!

Procedure:

1. Make a very hard dough from the whole wheat flour, water, herbs and garlic paste(take a really deep sniff, close your eyes, and savour the smell for a while).



2. Use all the Olive Oil and mix it with the dough to make it hard(very hard to hard).



3. Use this dough to make about 8-10 portions for rolling out.



4. Keep tava(pan) for heating up on a slow flame. This will ensure that your tava is heated up evenly and your chapati won't get burnt or cooked unevenly.



5. Roll out the chapati apply dusting flour regularly to prevent it from sticking. Roll out slightly thicker than standard chapatis because we have garlic and herbs in the dough. They may cause the chapati to puncture if we roll it out too thin. If the chapati gets punctured, then it won't balloon like we want it to.



6. Cook the first size on a slow flame on the tava just until small boils begin to appear on the top surface.



7. Turn the chapati over and cook on medium flame, turning the chapati so that the sides are cooked well. Always keep the sides in the center of the flame. The center of the chapati will get cooked well automatically. Now, larger boils will appear on the surface, and the under-surface will have brown spots on it.



8. Make the flame high, remove the chapati from the tava quickly, remove the tava from the stove and turn the chapati up-side-down on the direct flame. Watch it balloon!!!! (if you've done everything well till now. It took me a month and lots of flat chapatis to get to this stage).



9. Turn it around for just 1 second(or for symmetry as Appu would put it).



10. Take it off the flame and apply a little of the melted butter while it is still steaming hot.... Smell it again and again till you think you've attained nirvana....



11. Eat it!!!!

YAVFS

Yet Another Versioning File System....

I've been reading about Versioning and Snapshoting File Systems and here is a mini-dump of what I think so far. Please correct me if I'm mistaken....

I saw a few file systems with slightly more than a cursory glance, and here are my comments:

1. ext3cow: This is very close to what I have in mind for a versioning and continuous snapshoting file system. However, it does not agree with some of my "requirements of a versioning and continuous snapshoting file system"(below).


2. Elephant File System: This is probably one of the earlier snapshoting/versioning file systems and has been implemented on BSD. It is modeled on BSD's FFS. It does a great job of doing what it says it does. I like everything about it except that I can't use it on Linux.


3. NetApp's WAFL: This again is mainly solving a different problem, that of providing very fast and safe storage on a storage appliance. To the best of my knowledge, you need to trigger a snapshot(though the process itself does not take more than a few seconds), and the number of snapshots are restricted to a fixed number(32 or 256). This may be done using hourly cron jobs, etc.... The interface of getting previous versions of files is a little clumsy though.

Requirements of a Versioning and Continuous Snapshoting file system:

1. It should be able to store a large number of versions of files and directories alike


2. It should be able to do so very fast and without any user intervention. ie. Snapshoting should not be user-triggered, but should be done automatically on every close()


3. You should not need to re-compile the kernel to get this functionality


4. You should be able to apply this to a specific directory root. This means that you should be able to snapshot parts of your directory tree. You should not incur a performance penalty for accessing file out of this region of interest


5. You should have policies for controlling which file to snapshot and version files based on file attributes such as size, name, MIME type, etc....


6. The interface for accessing continuous-in-time file versions should be very clean and fairly intuitive, and it should be fairly easy to write tools around it so that GUI/web-based access can be enabled


7. You should be able to enable this functionality on any file system(and not require to re-format the partition on which you wish to enable it)


8. You should be able to disable this operation at any point in time and get back to accessing the most recent versions of the versioned files using the earlier access methods without any performance penalty. ie. Users should be able to turn on and off this functionality at will and it should allow users to proof this on real workloads without them having to make any drastic changes in their environments


9. The operations performed should be safe, and should not result in data corruption


10. The system should be easy to install and set up

I have in mind something that satisfies the requirements mentioned above....

NextGen Storage??

I've been thinking about what storage systems have in store for us in the future. I mean I've been trying to follow the progress of these beasts, and the next big thing I think should be storage devices that have in-built support for some form of transactional memory. Lots of file-system drivers are building consistency mechanisms into their implementation by using logging in some form or the other. This logging is happening on the same medium as the one where data is being stored. A consistent view of the data is formed by looking at (data+log) as a unit of storage.

I think that logging implementations would benefit a great deal if they had some sort of hardware support. For example, NetApp's WAFL is utilizing Flash memory to store it's writes. This I think is a nice way to look at the problem at hand, and if device manufacturers could integrate some of this on to their device using some nice interface, I think that file-systems of the future could be much faster than they presently are.

The only problem that I do however see with this approach is that the flash memory may wear out and cease to function much faster than the magnetic stable storage. A log-based file-system(or storage structure) would be needed to store the writes on the flash storage(something like JFFS maybe).

Crispy Butter Chapati.... yummm....

I have stopped making bread these days because I prefer eating chapatis. They not only take lesser time, but also involve eating a lot lesser flour. Besides, they are thin, can be made crispy easily, and I've been used to eating them for a while. So, I've decided to experiment with different types of chapatis(whole wheat Indian flat-bread). I don't have any pics. of chapatis I've made, but I'm sure google's image search will show up a faithful representation. Or you can visit this wikipedia page about chapatis.

My latest favourite is a layered chapati with layers of butter in between. Yesterday, it was raining quire heavily so our maid decided to spend the night at our place. I was observing her make her chapatis and she made this chapati with oil and flour in the middle, folded it and started rolling again. She was basically layering her chapatis. That's when I remembered that my mother used to feed me something similar as a kid. However, these tasted like run of the mill chapatis, so I decided to innovate and use butter as the separating medium. Believe you me, this adds amazing flavour and taste to the chapati, and it tastes so good that you can eat it as-is!!

Ingredients:

Whole Wheat Flour:	2 cups + more for dusting
Water:	Enough to make a hard dough
Softened Salted Butter:	15 Tbsp

Procedure:

1. Make a hard dough from the whole wheat flour and water.



2. Use about 1 Tbsp of Butter and mix it with the dough.



3. Use this dough to make about 8 portions for rolling out.



4. Keep tava(pan) for heating up on a slow flame. This will ensure that your tava is heated up evenly and your chapati won't get burnt or cooked unevenly.



5. Roll out cup size and apply butter generously. Apply dusting flour on the buttered side and fold in half.



6. Repeat the above step one more time to get 2 folds.



7. Now roll out completely(using dusting whenever necessary) into a chapati.



8. Cook the first size on a slow flame on the tava just until small boils begin to appear on the top surface.



9. Turn the chapati over and apply butter on the complete surface generously. Cook well.



10. Turn it around again, and apply butter on this side now. Cook well.



11. The more you change sides of the chapati, the more crispy it's surface will get.



12. Cook till done, and you have achieved the level of crispness that you want.



13. Eat it!!!!

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)));     
        
    }
}

Update (22/06/2010): This is probably the first and last time I hope to write Java code. Such a verbose and ungainly language have I never seen.

Marketing; the 8th sin?

Did you ever notice how people when the see advertisements tend to either:
1. Believe everything that's shown or
2. Believe only part of what is shown.

Well, I think this has to do with the fact that advertisers tend to (un)intentionally blur the facts to promote their products. I say that because it is not always don't intentionally, but sometimes, it is because of difference of opinion between individuals. Besides the utility of a certain product/feature, is entirely subjective and depends on the individual under question.

I think we sometimes wrongly blame marketing people for their (mis)doings, but I do believe that they need to get their act together and try and stay as close to reality as possible.

The thing with ads is that you can't have an enticing ad that is just factual. It needs to have some sort of feeling or direction to it and that isn't achievable by just spitting out the facts. People sometimes need to be told what use a toothbrush would be to them. You can't just highlight the features of a toothbrush without moping around the teeth, gums and bacteria aspect.

I think advertising will really come of age when advertisers learn to maintain the right balance.

Tnirwahtg gogole's ad "feraute"

I was tihnnikg auobt goolge and all the ad ruenvee it geaenerts and
all the ixndees it mannitias and all our dtaa taht it ixndees and
mekas alabalive for popele to secrah and fnid. Waht if "what if" I had
this piece of data taht I didn't wnat any srcaeh eignne to be able to
unrntesdad and yet allow poelpe to be albe to read. No ads geeaetrnd
besad on the cnentot, but yet ppeole can raed it. Iesrriceptve of the
robots.txt file, the data souhld NOT be ietpntrered in a viald faoihsn
by mniehcas. Mybae tihs isn't a lnog trem sooutiln, but it sure wroks
for now! Now only if I can find a vliad use for it :-p

If you wnat the spcrit, send me an eiaml at "dhruv \bbird@" + "google"[0] + "mail.com"

Mummy's "Jeeradu" masala

"Jeeradu" is a masala that we use to flavour our buttermilk and lemon juice. You can add it as-is to buttermilk and optionally sweeten it with sugar. You can also add this masala to a glass of lime juice along with sugar and optionally some salt to get a refreshingly fresh drink!

Jeera(Cumin seed) powder:	1 unit
Dry Ginger powder(Soonth):	1 unit
Black(Rock) salt powder:	3/4th unit
Table salt powder:	1/2 unit

Mix up all the above ingredients well, and use about 1/2tsp per cup of the drink required!