Friday, March 30, 2012

The SIMPLE homepage @google.com, why is it so designed ?

White, to me,  is the favourite colour for it  projects purity, cleanliness, and neutrality. Doctors don white coats, brides traditionally wear white gowns, and a white picket fence surrounds a safe and happy home. White is clean, neat and classy and looks pleasing to the eye. But is it the reason why the google homepage is also white in background. What does it project about Google ? What message does it convey ?

Ever Wondered why the google homepage is such a simple one ? No flashy looks, nothing moving here and there, no ads, absolutely nothing more than the simple plain search! You would probably guess that its a well thought move , definitely a deliberate decision. Of course, we dont expect the big G to be casual about it for its an unmatched web giant. Is it because they didnt have people to design it more elegantly/appealing ? Sounds kind of funny ! Right ? Well, it isnt !

If Google's vice president of local, maps and location services, Mayer is to be believed, this is a result of the limited knowledge of the co-founders of Google. This is what Sergey Brin had to say to Mayor when enquired about it. His own knowledge of HTML was not that great and they did not have webmasters, plus they wanted to test their search technique quickly which they were pretty confident about.

Some argue that it could have been more user friendly and needed less clicks had they put more options , more graphics on their homepage. To some extent I do agree with them, but then i personally feel its an iconic page with a neat look. Almost all other pages on web are a little more cluttered and most importantly we are used to this plain simple look which by now looks so pleasing to the eye. To me its a classy choice to keep it this way. What do you think though?

Sunday, March 25, 2012

Internship or no internship ??

"Should I go for an internship ? " - I have been asked this question a number of times these days and I could never reply it as a yes/no. Probably it depends. But depends on what ? To some I replied - "Yes go for one if you find an opportunity ", to some I could not give a concrete answer. Probably I was not sure. The reason is - my friends and colleagues have a divided opinion on the matter. One thinks, "Why go for an intern ? Instead one should sit at home and enhance his skills." Other said, "why cant one enhance his skills while he is an intern ?" And many others are not that clear about it. So you see that is the problem !!

Interns can sometimes be very useful. There is no denying the fact if you get to intern with an excellent firm. If not, you got to think hard and decide. Interns can be rewarding or sometimes not, sometimes they are paid, sometimes not. But I personally think the money factor should not be a very big role in this decision. It should be more about the time you devote and things you learn. Here is a small story.

Have you heard of  Wes Cherry? Probably not ! Have you played Solitaire on windows ? I think I can safely assume you have. If not, find a computer near you that has windows. Go to start up ->games-> solitaire. This is it !! It has been a part of windows operating system since windows 3.0 itself. Windows 3.0 was released in 1990 and I guess it has always been a part of it since then.  Why are we talking about though ? Yes, lets get back to the point. Solitaire was wrote (developed) by Wes Cherry in 1989 while he was an intern at microsoft. At that time there were few games and this became immensely popular. To verify how popular and tempting it has been let me tell you that people have also been caught playing Solitaire in their offices and some of them fired too :P . Dont believe that ? Look here yourself. To his misfortune though Wes received no royalties for Solitaire. So internships can sometimes be not rewarding at all . But then they are pretty useful. In wes's case itself, he later got an opportunity to write some code for the "microsoft Excel"  and yes he was highly rewarded for this.

The moral of the story is - though you could not be rewarded for your work as an intern it gives you a great opportunity to get a full time job with the same firm and enhances your chances to get selected into some other firms as well.

I myself did an internship at IIT Bombay in 2010. It was a 6-week internship and to this day I cant believe I wrote such a huge volume of code. I was a part of the team (of 5 people) who developed an excellent software. It was there that I realized how much I loved this field of software development. Not only that, I realized for the first time how important testing and UI (user interface) design are !! Though I can still not decide whether I should advice you to go for an internship or not, I think you should go for it. Take a chance, work hard, put in extra hours and I bet it will definitely benefit you in the long run :)

Last, but not the least, if you dont get an opportunity dont be disheartened. Trust me, I have seen a number of people bagging an excellent offer inspite of no internship/good projects. But yes, in that case you will have to work just a little harder.

Monday, March 19, 2012

The encyclopedia or wiki, the text or the e-book ?

Its been just a few days since I appeared for a job at amazon, and as usual I went about reading a lot about the company. One interesting product of theirs which specially captured my interest was kindle, the e-book reader which enable users to shop for, download, browse, and read e-books, newspapers, magazines, blogs, and other digital content. Look at the contents in bold once again. A few years ago, we were so used to the hard copies of these. An amazing sale of the amazon kindle made me think twice about the digitization of all the information around us today. It has occurred so rapidly that we could never sit back and admire it. So what ? Whats new then ? Here it is..


The encyclopedia called Britannica has decided to stop the release of its printed versions. Its going completely digital now.


And this makes me think of the future of libraries. What will be the most important  sources of information in future? I can already see a trend in my friends. People seeking knowledge no longer visit libraries, they no longer refer the Encyclopedia placed at a shelf in the library. Wikipedia and co I think has brought about this change. The online tool and e-content is so comfortably accessible, maintained and updated which probably beats the feeling of having a book in your hand !!

To many, it would be a shocking news, and I can understand that for I too love the feeling of  having a printed book in my hand as opposed reading an e-book. But, in life the only thing thats constant is "the change". And I think we are moving towards an age where most (if not all) of the information will only be available in the digital form !!  The printed pages of  Britannica have been a great companion to many for over 244 years and so this change will surely bring sadness to some. But with the tremendous rate at which digitization  is taking place it’s an inevitable move in this golden age of Internet and technology. If you are a Britannica fan and not the print form itself, nothing is going to change. Its only going to get better, at least in terms of regular updation. Jorge Cauz, the president of Encyclopaedia Britannica, Inc. put it like this -
 it [the digital form] is now a better tool since the website is updated on a regular basis and is integrated with multimedia. Their online offerings are more expansive which will make it even more convenient when doing researches.

Lets now look at the other side of the story. With this move, is it justified enough say that wikipedia is going to rule the world of information soon ? Thats probably debatable !!


The wikipedia contents can be very easily changed into a nonsense. Though generally not the case, its still possible. Add to that the censhorships, Is wikipedia really as reliable as an encyclopedia ?? Not exactly, but studies have shown that its not far behind. For more on this comparison, you may look at a report on the comparison between wikipedia and Britannica. To me it appears that Wikipedia is a definitely a good starting point for an introduction into any topic, to say the least. If you still doubt the credibility of the contents at wikipedia, it does provide you with links to outside sources. It also saves a lot of time compared to going through a gazillion Google hits for something useful. All these references on wikipedia are mostly excellent ones.


Five years ago, I lived with my uncle. When he got up in the morning in winter, my aunt used to place a cup of coffee and the "Times of India" newspaper near him. As soon as he got up he would pick up the two and then start with his normal routine. For some reason though, I started dreaming of it for myself :P but in my case I guess  it will be a little  different to say the least, for I have already stopped the subscription of Times of India (the newspaper) and moved to the e-version. Whats your take though ? Do you think the feeling of having a text in hand will be obsolete soon ?



Wednesday, March 14, 2012

Wikipedia NOT with Go daddy now !

How often do you visit wikipedia ? Have you heard of SOPA/PIPA ? Did you notice the wikipedia blackout on January 18 ? Do you know what the reason was ? Here it is - the full story on why wikipedia took this bold step, what followed and what has changed !!

What is SOPA/PIPA ?

SOPA stands for "Stop online Piracy act" and PIPA represents " The PROTECT IP Act ",  with PROTECT meaning Preventing Real Online Threats to Economic Creativity and Theft of Intellectual Property Act. SOPA is a bill introduced in US to expand the ability of their laws to fight online trafficking in copyrighted content on web. Under this act if a person/organisation finds that a website on internet is using its content without a legal permission from them, they can approach a court and get orders to stop the advertising networks and payment facilities from conducting business with this websites. They can get the site blocked and search engines will thereby stop linking to that site. Not that there were no such laws earlier but SOPA strengthens them by a fair magnitude. PIPA is a similar bill. Like SOPA, PIPA too gives the the copyright holders a strong tool to stand against a dishonest website.

Piracy indeed is a big concern but whether or not this is the right way to curb it,  is debatable. Some have lauded it, others have deemed it too harsh on the websites involving user generated data. Some have welcomed it with both the hands open. But it is not short on the criticism too. You can find a list of Congresspersons from US on each side and their views on these bills hereEric Schmidt , the Google chairman,  put it as an "overly simple solutions to a complex problem". 

The case of websites with user-generated data:

Though piracy, no doubt, deserves a strong fightback and copyright holders have been crying for long asking for a strict rule to help them curb this dreadful virus, people have found the above laws a little ambiguous to say the least. The case of websites such as Facebook, Youtube, Vimeo, twitter etc is interesting. Users leave a lot of content on these websites and users, I am not sure ought to be restricted . Let us take the most familiar example of Youtube. People post a lot of videos on Youtube. It may be the video of an artist who performed at their college and they would love to share that with their friends through youtube or probably Facebook. "Jal- the band" , performed at my college recently (by the way, thanks to those who organised it :D) and would you not love to share such a thing on your Facebook profile ? But wait a minute, should I get a legal permission from the officials at "JAL"  before I post a video of it on my Facebook wall ? Now suppose, I always go that way. Will I post as many videos as I normally do ? Will I not sometimes think - "what drama man !! Who will do all that ? I am feeling quite lazy about it" (Well, I am a lazy person by the way !!). Will that not be a setback for Facebook ??

Now suppose one posts such a thing on his Facebook wall or may be writes something on Wikipedia which should really require a copyright. What do you think the result should be ? Should he be banned from using the respective site ? Or do you think thats a little too harsh ? If you do, this is going to be a surprise for you. Now look at the underlined text above. Yes, the organisation with the copyright can get facebook (Youtube or wikipedia) blocked. Its not mendatory that this will happen but there is a chance (even though slim) that this can happen.

What happened between Wikipedia and GO Daddy:

Wikipedia blackout on January 18,2012 was a firm stand by wikipedia against SOPA. Now, look at the image below. This is a snapshot showing a tweet by Jimmy wales (the wikipedia co-founder) himself:



As the above text suggests Go daddy seems to have supported SOPA and Wikimedia could not digest this. Wikimedia legal counsel Michelle Paulson put the transfer of its domain registry like this:-
After months of deliberation and a complicated transfer, the Wikimedia Foundation domain portfolio has been successfully transferred from GoDaddy to MarkMonitor [a U.S.-based domain registry and trademark ]. The portfolio transfer was formally completed on Friday, March 9th, 2012. The transfers were done seamlessly and our sites did not experience any interruption of service or other issues during the procedure.

Here is the official blog post covering the transfer. Wikipedia is not alone on this. If VentureBeat is to be believed, Go daddy has lost more than 37,000 domains as a result of its support for SOPA . Though, Go daddy realised this and softened its stand on SOPA, it was just a little late. I am not completely against SOPA. I completely agree that piracy need to be fought and fought very strongly but i think the bill just passed needs to be edited a little.

Related Articles:

Wednesday, March 7, 2012

Watson computer - the INTELLIGENT one !!!

The human-like intelligence- ARTIFICIAL INTELLIGENCE !!

Can a machine be intelligent ? Can it talk to people in their natural language ? Can it read our lips ? Is it possible to build a machine as smart as a person ? Can the human intelligence be replicated ? Can we build a person ? or does it only confine to fiction ?  The question has been floating for decades but without a concrete answer !!  The computer has always been the king when it comes to processing huge amount of data/information.The immense rate at which it has grown inspires the confidence. The confidence is high enough to at least inspire a lot of characters in fiction.  The concept looks mesmerizing but no computer/robot has been able to interact with human as seamlessly as hollywood imagines. The problem is - the human brain, a very complex entity that defies any attempt at replication. Our brain is immensely sophisticated. The simple skills that humans master early in life like understanding language or recognizing objects continues to baffle the researchers.

The quest for artificial intelligence has gone on for decades. There is a huge difference between data and information. Computers process data but can they extract information out of it ? Can a machine possess knowledge ? Can it learn from experiences ? These are questions that decide if a system is intelligent. Lately there has been a lot of research in the field of artificial intelligence and machine learning. But no machine can understand natural language and converse with a human for it includes puns, irony, riddles and double meaning sentences. There has been a lot of work to achieve it and this article looks at one such attempt. An attempt by IBM.

The Chess Playing Computer:

You might have heard of Deep Blue- the chess playing computer !! It was an initiative by IBM. If wikipedia is to be believed, On May 11, 1997, the machine won a six-game match by two wins to one with three draws against a world champion in chess- Garry Kasparov. The system derived its playing strength mainly out of ts brute force computing power. It was capable of evaluating 200 million positions per second. Computing at an extremely high speed it could evaluate multiple steps and search the step that would result in maximum chances of winning or minimum chances of loosing. There were adverseries who argued that the rules of chess are very well defined. So it can easily be coded in a computer system and this in no way means that the system was intelligent. Thanks to these people IBM came with a better system- The Watson Computer!!

The motivation Behind the Watson computer:-

Its an interesting story that led to the thought of designing this system. Watson computer was designed to play Jeopardy!. Jeopardy is a unique quiz-show in which there are three contestants. They are given clues leading to an answer and the contestants are required to guess what the question would be !! Sounds kind of interesting. Right ?? The show features trivia in history, literature, the arts, pop culture, science, sports, geography, wordplay, and all other topics. To know more about Jeoprady! you may visit the wiki article or watch a television show of it on youtube.Getting back to Watson,since Deep Blue's victory over Garry Kasparov in 1997, IBM had been on the hunt for a new challenge. Once Charles Lickel went out for a dinner with his coworkers. There he noticed that the restaurant they were in had fallen silent. The cause of this was the airing of a show on television featuring: Ken Jennings, who was then in the middle of his successful 74-game run on Jeopardy!. He thought of quiz show as a possible challenge for IBM, and passed the idea on. In 2005, IBM Research executive Paul Horn backed Lickel up and David Ferrucci took the challenge.

What is Watson ? What is it capable of ???

According to IBM, Watson is an efficient analytical engine that pulls many sources of data together in real-time, discovers an insight, and deciphers a degree of confidence. Lets analyse this definition. You can pose questions/hints and watson will search the most relevant things for you. Is that not what the search engines do ? The point is, watson takes you a step further. Watson can understand the actual meaning behind words, distinguish between relevant and irrelevant content, and ultimately demonstrate confidence to deliver precise final answers. As a result of its deeper understanding of natural language, it can process and answer more complex questions that include puns, irony and riddles common in natural language. Look at the words in bold. Yes, thats exactly how it differs from your favourite search engine. Ask watson- "What is the capital of Russia?” and it will speak out - “Moscow,” . As simple as that !! Now think of your search engines. Ask them the same- What is the capital of Russia?” It’ll award you with links to websites where you might find your answer.You then revise your search terms until you find a satisfactory answer. Woludnt it be nice if you could just ask the question, and get an actual answer rather than a list of documents or websites? Thats watson !!!

Watson- the Jeopardy Player:

Is Watson an improved search engine ??  No, it was never meant to be one. In 2011 Watson did what it was supposed to, it played the game of Jeopardy! with Ken Jennings and Brad Rutter, two of the most successful contestants on the show and emerged the winner too. Watson learns through machine learning, it learns from its mistakes, for example, initially it used to come up with very silly answers- some of which one can never expect out of a human. As part of the preparation, IBM constructed a mock set in a conference room at one of its technology sites to model the one used on Jeopardy! Human players, including former Jeopardy! contestants, also participated in mock games against Watson. This helped it learn a lot about the game. Due to its limitations with audio/video understanding, Watson received the clues as electronic texts at the same moment they were made visible to the human players. It would then parse the clues into different keywords and sentence fragments in order to find statistically related phrases.Watson's main innovation was not in the creation of a new algorithm for this operation but rather its ability to quickly execute thousands of proven language analysis algorithms simultaneously to find the correct answer.The more algorithms that find the same answer independently the more likely Watson is to be correct. Once Watson has a small number of potential solutions it is able to check against its database to ascertain whether the solution makes sense. Part of the system used to win the Jeopardy! contest was the electronic circuitry that receives the "ready" signal and then examined whether Watson's confidence level was great enough to activate the buzzer. Given the speed of this circuitry compared to the speed of human reaction times, Watson's reaction time was faster than the human contestants except when the human anticipated (instead of reacted to) the ready signal. After signaling, Watson speaks with an electronic voice and gives the responses in Jeopardy!'s question format. Watson's voice was synthesized from recordings that actor Jeff Woodman made for an IBM text-to-speech program in 2004. You would think is it only for a game that IBM spent all its time and money ? No, Jeopardy! was only a showcase of IBM's work in the field of AI.

The Science Behind an Answer:

The science behind formulation of answers by Watson can be thought of as a 4-step process:

  1. Question Analysis: Watson parses the question into parts of speech and identify the different roles words and phrases are playing. At this stage Watson has no idea of what the question can be. So it increases its chances of reaching the right one by considering many different options about what the question may be.

  2. Hypothesis Generation: For each interpretation of the question, Watson goes through millions of documents. At this point quantity is important as it does not want to miss out on reaching the correct reference. If it does, it can never chose the correct answer!!

  3. Evidence Scoring: It is not enough for watson to just come up with an answers but it has to support them with evidences and logic. Thousands of algorithms run in parallel to evaluate the score for each possible answer.

  4. Final Merging and Ranking: The scores are then used to rank the possible answers and evaluate the confidence watson possesses in its highest ranked answers. Note that the threshold confidence level based on which Watson decides whether it should give an answer or not is not fixed but depends on the scores of its opponents and the situation in the game.


What future has in store for Watson: 

Watson cant understand the love of a mother, the feel of music, the emotions but his enormous knowledge base, his skill to understand and interpret the natural language and his ability to learn are definite signals to a marked achievement in the field of technology. Watson is impressively intelligent. Beyond Jeopardy!, the IBM team is working to deploy this technology across industries such as healthcare, finance and customer service. In the words of Dr. David Gondek form IBM:
U think of internet. No one knew that internet would become such an important part of our life. Watson has a similar promise. It is transformative and you dont even know what it can become.

The whole project was not about Jeopardy! , it was about doing research, its about doing deep analytics and natural language understandings. Its about applying the technology to solve problems people really care about. According to IBM, "The goal is to have computers start to interact in natural human terms across a range of applications and processes, understanding the questions that humans ask and providing answers that humans can understand and justify." Nuance Communications Inc has partnered IBM in the research project to develop a commercial product that will exploit Watson’s capabilities as a clinical decision support system to aid the diagnosis and treatment of patients. Physicians at Columbia University are helping identify critical issues in the practice of medicine where the Watson technology may be able to contribute and physicians at the University of Maryland are working to identify the best way that a technology like Watson could interact with medical practitioners to provide the maximum assistance. It has also been suggested by Robert C. Weber, IBM's general counsel, that Watson may be used for legal research. Just the same way Watson analyzed massive data in Jeopardy! to reach a set of hypotheses and list down couple of most likely outcomes, it could help Doctors in diagnosing patients. Watson could analyze the patient's specific symptoms, medical history, hereditary history and synthesize that data along with the mass of all unstructured and structured medical information in the world including (but not limited to) medical records of similar situations available to it. Watson uses this information in addition to the wealth of fundamental medical knowledge available in the form of all published medical books and articles fed into Watson. IBM had made it clear that Watson did not intend to replace doctors, but assist them to avoid medical errors and sharpen medical diagnosis with the help of its advanced analytics technology. IBM intends to use Watson in other information intensive fields as well, like telecom, financial services, government etc. To end with, I would say this is not the end of the list, but the beginning of an era and


Now, do you think its the Golden Age of Technology we are living in?

References:

Monday, March 5, 2012

Edit distance - implementation

The Problem Statement:

Edit Distance (also called Levenshtein distance)is a classic Dynamic Programming Problem. You are given a source string (say, of length m)and a target string (say of length n) plus a series of allowed transformations and their corresponding costs. You are required to find the minimum cost required to convert the source string into the target string using only the given transformations. Let us take a temporary string "temp" to illustrate things clearly. Initially we will keep our "temp" string empty and at the end of the algorithm we will have "temp" containing the same contents as the target string. Lets use i and j as the indices into the source string and the "temp" string. Set i=j=0 initially. The allowed transformations are generally:

  1. insert - add a character(say 'c') to the "temp" string ie.. put temp[j]=c and increment j.

  2. replace - replacing a character of source string by any another character (say 'c') ie.. we will insert c into "temp" string and increment both i and j. Note that we only incremented j in (1).

  3. delete - deleting a character from source string ie.. increment i only.

  4. copy - copy a character from source to "temp"(generally involves no cost).


Cormen's text (no 1 here) also mentions this problem in its exercises but he has given two more transformations called

  • twiddle - exchange next two characters ie.. copy both but they appear in opposite order in the target string.

  • kill - kill the remainder of source string ie set i=m-1.


Lets assume that the costs for copy, insert, replace and delete are C,I,R and D respectively.  Also, for simplicity we will leave out the "twiddle" and "kill" operations. If you want to consider these two operations, you may refer the Instructor’s Manual by Thomas H. Cormen, Clara Lee and Erica Lin to accompany the cormen's text which gives the pseudocode involving "twiddle" and "kill" functions as well. Lets now look at a few examples to understand the problem statement more clearly.

Examples:

  1. Let source string="at" and target string="mat". Here we can simply insert "m" at the beginning of "temp"and then copy 'a' and 't' from source to "temp". So the minimum cost required= I+(2*C)

  2. let source="cat" , target = "mat" then cost= R+(2*C),

  3. let source="cat" , target = "at" then cost= D+(2*C),

  4. let source="cat" , target = "cat" then cost= 0(zero),

  5. let source="cat" , target = empty string, then cost= 3*I ie.. insert all 3 characters.


As is generally the case , lets assume that copy operation requires no cost.Lets now take a slightly tougher example(from wikipedia article):

Suppose, source= "kitten" and target="sitting",there is no way to do it with fewer than three edits:

  • kitten → sitten (replace 'k' by 's')

  • sitten → sittin (replace 'e' by 'i')

  • sittin → sitting (insert of 'g' at the end).


Recursive Code:

Below is a recursive code to find the edit distance of two given strings. You may try different inputs on the ideone link for my recursive solution.

[sourcecode language="cpp"]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define IC 1 /*cost to insert*/
#define RC 1 /*cost to replace*/
#define DC 1 /*cost to delete*/

int minimum(int a, int b, int c)
{
int min = c;

if( a < b )
{
if( a < c )
{
min = a;
}
}
else
{
if( b < c )
{
min = b;
}
}

return min;
}

/*
red- recursive edit distance

*/
int red(char *x, char *y)
{
int d,e,f;

/* Base cases */

if(*x==0)return strlen(y);
if(*y== 0)return strlen(x);

/* Recurse */

if(*x==*y)
d=red(x+1,y+1);
else
d=RC+red(x+1,y+1); /*replace*/
e=IC+red(x,y+1); /*insert*/
f=DC+red(x+1,y); /*delete*/

return minimum(d,e,f);
}

int main()
{
char source[]="kitten";
char target[]="sitting";

printf("Minimum cost to convert %s into %s is %d\n",source,target,red(source,target));

return 0;
}
[/sourcecode]

The DP solution:

Here is the idoene link for the DP code. Play with it if you find the DP code difficult to understand !!

[sourcecode language="cpp"]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define IC 1 /*cost to insert*/
#define RC 1 /*cost to replace*/
#define DC 1 /*cost to delete*/

int minimum(int a, int b, int c)
{
int min = c;

if( a < b )
{
if( a < c )
{
min = a;
}
}
else
{
if( b < c )
{
min = b;
}
}

return min;
}

int edit_distance(char* s1, char* s2)
{
int d;
int m = strlen(s1);
int n = strlen(s2);
int dp[m+1][n+1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1])
d = 0;
else
d = RC;
dp[i][j] = minimum(dp[i-1][j-1] + d, /*replace*/
dp[i-1][j]+IC, /*insert*/
dp[i][j-1]+DC); /*delete*/
}
}

return dp[m][n];
}

int main()
{
char source[]="kitten";
char target[]="sitting";

printf("Minimum cost to convert %s into %s is %d\n",source,target,edit_distance(source,target));

return 0;
}

[/sourcecode]

Try understanding how the DP matrix will look like. For the above wiki example, here is the DP matrix:




























































































kitten
0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

You can also try different inputs to see what the result could be here. Both time and space complexity of DP solution is O(nm). The sequence of operations performed can also be printed but for that we need to use an additional O(mn) space which will save the operation performed along the way and the sequence can be found recursively moving backwards. See the Instructor’s Manual by Thomas H. Cormen, Clara Lee and Erica Lin to accompany the cormen's text if you find any difficulty. Note that the space requirement can be improved to O(n), as in each iteration only requires element from the current and previous row but in this case retracing the path to find the operations used and their order is not possible. Also note that there may be more than one of these paths and the above solution chooses one of them.

Modifications:

  1. Substring Matching

  2. LCS - make the cost of replacement greater than that of an insertion plus a deletion.

  3. Maximum Monotone Subsequence


For an explaination on what modifications are needeed in each section refer Programming Challenges by Steven Skiena( no 3 here).



References: 

Here are a few materials that discuss the algo/implementation:



Saturday, March 3, 2012

Internship at IIT Bombay

NOTICE

You can still apply for an internship program at IIT Bombay this summer. I have an experience of it and I can assure you that its a really good environment. You will get to learn a lot. Plus, Bombay is such an excellent place to visit :) I received an e-mail from them today. Here is what it contained:
Dear Students,

We are pleased to present an opportunity for direct placement into SummerInternship 2012, Under the guidance of Prof. D.B Phatak, IIT Bombay
As you know, last year only 60+ students were selected from nearly 700 applicants. After seeing the quality work and enthusiams, this time we are extending our intake.We are requesting all of you to use your software skills to contribute to an ambitious initiative http://ekalavya.it.iitb.ac.in/ekalavyaHome.do to provide quality education to underprivileged students. This is the great chance for you, to get good exposure to programming challenges and enhance your skills.
Even if you are not interested or eligible in joining the summer internship,
Please forward this mail to your friends, so they can make the most of thisopportunity..
Visit http://ekalavya.it.iitb.ac.in/summerintern2012 Summer Internship 2012 - Registration Open and register.

Thanks and Regards,
Summer Internship Team

If you are in BE/B-tech third year and want to get into an internship program, I think you should go for it.It will also be open for second year students but third year people are generally preferred. Leave a comment if you have any clarifications !!!