An O(1) approach to the LFU page replacement algorithm

LFU: Least Frequently Used

The LFU algorithm evicts pages that have been least frequently used. If the cache is full, and one more page needs to be added, the page that has been used the least number of times is evicted from the cache.

How can we efficiently implement this algorithm? Each operation of the LRU algorithm can be implemented in worst case O(1) complexity. We can do the same for LFU as well.

For this, we maintain a doubly linked list where each node of the linked list looks like this:

struct CountNode
{
 CountNode *prev, *next;
 PageNode *root;
 int count;
};

Each node of this linked list points to the root of another doubly linked list which holds the actual pages. All the pages in this 2^nd linked list have the same usage count. The node for this linked list looks like this:

struct PageNode
{
 PageNode *prev, *next;
 CountNode *parent;
 char pageData[4096];
};

The PageNode's parent member points to that CountNode of which it is a child. So there is a direct pointer from every PageNode to the corresponding CountNode it falls under. These extra links are not shown in the diagram to keep it simple.

The CountNode linked list's count member holds the usage count of each element under that node. So each PageNode under a CountNode having a count value of 6 will have been accessed 6 times.

How to implement the various operations?

1. Insetion: To insert, we always add the new PageNode to the CountNode list with the count value of 1. This will always be the first node in the linked list pointed to by head. If the first CountNode pointed to by head is greater than 1, we just add a new CountNode with a count value of 1 and then perform the insertion. All this can be done in time O(1).


2. Deletion: We will delete nodes, only if the cache is full, and this deletion will always happen from the CountNode list which has the least count. So, we just follow head, and delete a PageNode in such a CountNode. Additionally, if that CountNode happens to become empty because of this deletion, we also delete that CountNode. This too takes time O(1).


3. Access: Access involves incrementing the count of a PageNode, i.e. moving the accessed PageNode from it's CountNode list to a CountNode list with a count value that is 1 greater than it's current count value. We maintain pointers to the CountNode in the PageNode. This makes deleting the PageNode(and possibly the CountNode to which it belonged) a constant time operation. After that is done, we can insert a new CountNode that has a count value of 1 more than the CountNode from which the accessed PageNode was removed. If such a CountNode does not exist, we can always create it first. All this can also be done in constant time, making the whole process O(1).

   A lot of people have asked me how they can get to a PageNode in the first place. The answer to that question is that we maintain a hash table which hashes an object(page address, integer, etc...) such that accessing it (getting to the PageNode that that object corresponds to) can be accomplished in O(1) time.

This implementation takes advantage of the fact that:

1. When we add a new object to the cache, it is always going to start off with a use count of 1, and


2. Whenever we access an object, it's use count will go up by exactly 1.

I haven't found any resource that says that LFU can be implemented in time O(1). If you (reader) find any, please do let me know.

The Missionaries and Cannibals Problem

Some reading before you start: http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

Problem Statement:
[From the link above] "In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board."

Solution:
We will solve the generalized version of this problem, wherein there are C cannibals and M missionaries, and at most P people are allowed on the boat simultaneously.

This problem can be solved by noticing that at every stage, we can encode the state of the problem by using 3 variables, (nc, nm, shore). nc is the number of cannibals, nm is the number of missionaries and shore is either 0 or 1, which signifies whether nc and nm represent the count on the source or the destination shore respectively.

Thus, there are at most 2 x n² states that the problem can be at any point in time.

We can use BFS (breadth first search) to perform an exhaustive search on the search space to find a solution if one exists. The run-time complexity of doing so is O(CM P²). Below is the Python2.5 code that solves this problem using the BFS search method.

import sys
import string
from collections import deque


states = [[], []]
dq = deque()
nc = 0
nm = 0
c = 0
combinations = [ ]


def gen_combinations():
    global c, combinations

    for i in xrange(0,c+1):
        for j in xrange(0,c+1):
            if i+j>0 and i+j<=c:
                combinations.append((i,j))


def init_states():
    global nc, nm, states
    for i in xrange(0, nc+1):
        states[0].append([])
        states[1].append([])
        for j in xrange(0, nm+1):
            states[0][i].append(-1)
            states[1][i].append(-1)


def is_valid_state(nc, nm):
    return (nm>=nc) or (nm==0) or (nc==0)


def bfs():
    global dq, states, nc, mn, c, combinations

    while (len(dq) > 0) and states[1][nc][nm] == -1:
        (x,y,depth,boat) = dq.popleft()

        present = boat
        next = 1-boat

        if states[present][x][y] != -1:
            continue

        states[present][x][y] = depth

        for comb in combinations:
            (dx,dy) = comb

            if x>=dx and y>=dy:
                new_st = (nc-(x-dx),nm-(y-dy),depth+1,next)
                (lx,ly) = (nc-(x-dx),nm-(y-dy))
                (rx,ry) = (nc-lx,nm-ly)

                if is_valid_state(lx, ly) and is_valid_state(rx, ry) \
                       and states[next][lx][ly] == -1:
                    dq.append(new_st)



def main():
    global dq, nc, nm, c, combinations, states
    input = string.split(raw_input())
    nc = int(input[0])
    nm = int(input[1])
    c  = int(input[2])

    init_states()
    gen_combinations()

    dq.append((nc, nm, 0, 0))
    bfs()

    print states[1][nc][nm]

    return 0


if __name__ == "__main__":
    sys.exit(main())

The Capacity C Torch Problem

I stumbled upon the Capacity C Torch problem, and found it really interesting.
I'll start off with a few resources:

1. http://aps.cs.nott.ac.uk/2008/05/06/the-capacity-c-torch-problem-2/


2. http://www.tutor.ms.unimelb.edu.au/bridge/


3. http://en.wikipedia.org/wiki/Bridge_and_torch_problem


4. http://www.springerlink.com/content/935641175550x527/

Problem Definition:
There is a group (G) of people that wishes to cross a bridge in the dark. Each person takes a certain amount of time to cross the bridge. There is only 1 torch available. The bridge can hold at most C people at any one time. Every time a group of people cross the bridge, they need to carry the torch with them. One torch is sufficient to light the path for at most C people at a time. When multiple people cross at the same time, the entire group moves at the speed of the slowest person in the group. Given the values for G, C and the time that each person takes to cross, find the least amount of time that would be required to get the whole group across to the other side.

Expected Complexity of the solution: This solution can be solved using a computer program having a run-time complexity of O(n²), where n is the number of people in the group G [ |G| = n ].

Solution:
Step-1: Let us first concentrate only on how we will divide up the people into sets and in what order we will take them across(from size A to side B). We shall re-visit the problem of which person to get back to bring the torch back from side B to side A.

Let us take some values for the variables G and C.

Example-1: Let |G|=15 and C=5

In this case, we can easily divide people into 3 sets of size 5 each.

We'll sort all the people according to the time they take and group them starting from the slowest person. It can be seen that it is beneficial to club all the slow people together. So, we group the 15^th, 14^th, 13^th, 12^th and 11^th person in one group, and so on..

We'll take the 1^st group(the one with the 5 fastest people) and move them across first. Since someone needs to come back with the torch, it had rather be the quickest person, so we make sure he is across so that he can return.

We then take the 2nd group followed by the 3rd.

Example-2: Let |G|=16 and C=5

In this case, we are left with 1 person after dividing into sets of 5 each. No matter what we do, we will have 4 sets to deal with. We also note that it makes no sense to move just 1 person across. So, the way we make sets is {2,4,5,5}.
Why not divide as {3,3,4,4}? Well, if we do it like the latter case, then the 1^st group will have the time of the 3^rd person, and not the 2^nd like in the former case. In both case, everything else remains the same, except if the 3^rd person is slower than the 2^nd one, we will have increased the total time required to cross. This is why we optimally divide in the former way.

Example-3: Let |G|=17 and C=5

Again, in this case, we optimally divide as {2,5,5,5}. We note that no other division is possible.

Example-4: Let |G|=18 and C=5

Again, in this case, we optimally divide as {3,5,5,5}. We note that no other division is possible.

Example-5: Let |G|=19 and C=5

Again, in this case, we optimally divide as {4,5,5,5}. We note that no other division is possible.


Step-2: Now, we shall concentrate on the problem of which people should bring the torch back from side B to side A, so that the next group on side A can cross the bridge to side B. Let us call these people torch bearers. The same problem also asks and how many at a time to bring back (i.e. How many torch bearers should move from side B to side A without returning) when sets of people are being transferred from side A to side B.

[This is where you should try figuring out for yourself whether you will send 1, 2, 3, 4, 5 (or more) groups at a time (without the torch bearers returning to side B)]

For example, suppose we have a group of people, [1,1,1,1,1,1,4,5,6,7] and C=3.
It is easy to see that once we have 2 people across, we can always get more across without having the torch bearers coming back to side B.

If we decide to work such that every time 2 torch bearers cross over to side A, they return to side B, we get the following scenario: The mean cost of transferring a set from side A to side B, and back would be 1(1^st torch bearer from B to A) + 1(2^nd torch bearer from B to A) + 1(1 and 2 back from side A to side B) = 3/1 (since we were able to get only 1 set across).

If we decide to work such that every time 3 torch bearers cross over to side A, they return to side B, we get the following scenario: The mean cost of transferring a set from side A to side B, and back would be 1 + 1 + 1 + 1(1, 2 and 3 back from side A to side B) = 4/2 (since we were able to get 2 sets across).

Similarly, if we decide to work such that every time 5 torch bearers cross over to side A, they return to side B, we get the following scenario. The mean cost of transferring a set from side A to side B would be 5+1(1, 2 and 3 back from side A to side B)+1(1 from side B to side A)+1(1, 4 and 5 back from side A to side B) = 8/4 (since we were able to get 4 sets across).

We observe that the mean cost went down if we took more torch bearers at a time. However, it is also easy to see that this is not always true. It depends entirely on the time that each torch bearer takes to cross the bridge.

We could also have a case where we have more than 3 torch bearers crossing from B to A, without coming back (like we sent 5 torch bearers at once in the example above).

We can NOT make a greedy choice as to how many sets to take across. i.e. How many torch bearers to send from B to A without them returning. This is where dynamic programming comes to the rescue.

Suppose |G|=47 and C=5
We will optimally divide into sets {2,5,5,5,5,5,5,5,5,5}.

The best way to take all 10 sets across is the best of:

1. The best way to take all across without any torch bearer coming back unless all initial groups are across


2. The best way to take the first 9 groups plus the best way to take the last group


3. The best way to take the first 8 groups plus the best way to take the last 2 groups


4. ...


5. The best way to take the first group plus the best way to take the last 9 groups

The cost for computing these values using dynamic programming or memoization is O(n²). We can use these techniques because there are many overlapping sub-problems, and the other requirements for dynamic programming match.

We can pre-compute the cost required to take 1, 2, 3, 4, etc... groups at a time and store it in a lookup table. The time required to do this is O(n²).

Thus, we can solve the whole problem in time O(n²).

Wordlist for GRE

Hello people, I have made a simplistic wordlist tool for GRE preparation. I've been asked by a well-wisher to post it here, so here it is: http://wordlist.dhruvbird.com/.

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.