Finally Bombay gets to see some lovely rain. This isn't a good news for most, as the rain is causing floods all over the place. But one cannot stop feeling awesome (with a feeling of guilt) looking at the sea while it rains so heavily here. Marine drive looks just perfect when it rains and the skies are grey and the leaves lush green.
For people who love Bombay here is a simple quiz question:
If you were to take a friend of yours to the best place in Bombay, which would it be?
My answer is the most typical one, Marine drive. (Also watch Wake up Sid to know why I use the word "typical" to describe my choice. More about Wake up Sid later.)
Also here is a simple and cute problem I came across.
Let s be a sequence of numbers from {1,2,...,n}. Let the Longest Increasing Subsequence (LIS) be a set of numbers from the given sequence s, such that when its elements are arranged in the order in which they appear in s, they are increasing and there is no other subset of numbers (strictly) larger than this with the same properties.
For example: s = 1 3 7 2 5 4 6.
The following subset {1, 2, 4, 6} when arranged as they appear in s, give 1246 and is the LIS.
Problem: Given a sequence over {1,2,...,n} find LIS.
(I could have written this in fewer lines if I could use math symbols. !! argh!).
Patience Sorting:
You are given a deck of n cards which are numbered by numbers in {1,2,...,n}. You get one card at a time from the deck of cards. The first card is put in the first pile. Any card is put in one of the existing pile, if the topmost (the most recently added) card in that pile is larger than this card. If no such pile exists, then another pile is started.
The goal is to minimize the number of piles.
The greedy algorithm places a card in the first pile where the most recently added element exceeds the current drawn card.
Here is why we suddenly started playing cards, instead of finding the LIS.
Claim: The number of piles created by the greedy algorithm (#p) = the length of LIS, l .
Proof: #p > = l: the elements of the LIS will be in distinct piles (due to the greedy algorithm).
#p< = l: Suppose not. There exists a pile P that does not contain any element of the LIS. Let t1,t2,...,tk be the top elements of piles which were created before P. They are all smaller than the elements added in P. Also all the elements added to piles which were created after creation of P are larger than the last element added to P. Hence, one can create a longer increasing subsequence using P than the LIS. Thus a contradiction. It is easy to construct the LIS from these piles, right?
For people who love Bombay here is a simple quiz question:
If you were to take a friend of yours to the best place in Bombay, which would it be?
My answer is the most typical one, Marine drive. (Also watch Wake up Sid to know why I use the word "typical" to describe my choice. More about Wake up Sid later.)
Also here is a simple and cute problem I came across.
Let s be a sequence of numbers from {1,2,...,n}. Let the Longest Increasing Subsequence (LIS) be a set of numbers from the given sequence s, such that when its elements are arranged in the order in which they appear in s, they are increasing and there is no other subset of numbers (strictly) larger than this with the same properties.
For example: s = 1 3 7 2 5 4 6.
The following subset {1, 2, 4, 6} when arranged as they appear in s, give 1246 and is the LIS.
Problem: Given a sequence over {1,2,...,n} find LIS.
(I could have written this in fewer lines if I could use math symbols. !! argh!).
**********
On a completely unrelated note let us also look at a card game:
Patience Sorting:
You are given a deck of n cards which are numbered by numbers in {1,2,...,n}. You get one card at a time from the deck of cards. The first card is put in the first pile. Any card is put in one of the existing pile, if the topmost (the most recently added) card in that pile is larger than this card. If no such pile exists, then another pile is started.
The goal is to minimize the number of piles.
The greedy algorithm places a card in the first pile where the most recently added element exceeds the current drawn card.
*********
Here is why we suddenly started playing cards, instead of finding the LIS.
Claim: The number of piles created by the greedy algorithm (#p) = the length of LIS, l .
Proof: #p > = l: the elements of the LIS will be in distinct piles (due to the greedy algorithm).
#p