Archive

Archive for May, 2006

PDC 2006, in Lahore, Pakistan !

Well, the Professional Developer's Conference (PDC) – Pakistan is going to be held from 28th-30th June, 2006 in Karachi and on 28th June in Lahore. It's organized by Microsoft Corporation. It's a great gathering of some really cool programmer's, engineers, architects, managers around the Pakistan. I have missed last 2 when I really got to know about PDC. This year University of Central Punjab has taken nice steps to remain in the scene and provide it's services as a host place for regestration fee which is Rs. 1000 for professionals. The Lahore session will be held in The Avari Lahore. I am planning to spend my day there to meet Microsoft People once again in my life. Further information can be viewed at here. Hoping to see you all at PDC !

Categories: Computer Science, General

FAST-NU Sports Gala and Techlogix !

FAST-NU which is a premier Computer Science University in Pakistan has this privelege of organizing mega IT and Sports events. This year also they have organized a sports gala for all Software Houses and Telecomm Sector places of Lahore. It was actually good time and fun to be there. Though I reached there quite late from office, but Techlogix has already sarted the winning streak by having won their table tennis matches. Usman Qadri from Techlogix is a superb player of Tabble tennis and Badminton. He has won his matches of tabble tennis, badminton quite easily. Cricket team of Techlogix has also won it's first match with Mentor Graphics very easily. So it has been a happening night at FAST-NU Lahore cmapus, met quite old friends from university and college. Enjoyed to some extent. On our way back suddenly it started raining in torrents, yeah it was too much of rain, we were in car of Osman Sarood and decided to have some refreshment, but when we left for our homes, and Osman was reversing his car, suddenly it hit a Truck , a bang and immediately the hind screen of car broke with a loud sound. Osman hit his car with truck , he missed it because it was too much of water on back screen due to heavy rain. Very bad, I felt so sorry for him, it was his new Santro, it costed him the wind screen and a lot of denting and painting work.

So in this way this very happening night ended and we safely reached home. Today even we have our matches. Let's see what happen, but one thing is for sure, we will have some real fun.

Haroon 

Categories: General

Finding Longest Common Subsequence !

Well I will be getting some what techie. in this post , i recently tried and solved the Longest Common Subsequence problem once again , which is a really hard problem to solve(if you have not heard it before or never tried it).

Well, consider the text string S = 'i am a computer programmer' and another text string T = "a crammer" now this is contained in the string S , read the letters in capital in S, 'i Am a Computer pRogrAMMER', now this is the problem of finding any substring of T in S at any place in any form and the one which is the longest.

I solved this problem in a programming competition by generating all the subsets of strings S and T and finding the longest in subset strings of S. But the code was too complex and the complexity was 2^N for subsets and log(n) for search even the code was iterative. However thanks to Dynamic Programming that this problem can be solved in O( M * N ) worst case time complexity, where M = length of string S and N = Length of string T

the dynamic programming algorithm or pseduocode is;

int FindMaxLengthSubstring( S, T )
{
 // make a 2 D array say MaxLen of size M * N for logical thinking
 for ( int i = 0; i < Len(S); i++)
 {
  for (int j = 0; j < Len(T); j++)
  {
   if (S[i] == L[j] )
   {
    if( i==0 || j ==0)
    {
     MaxLen [i][j] = maximum( in 0th row or 0th column of MaxLen) + 1;
     continue;
     }    
     MaxLen [i][j] = 1 + MaxLen[ i – 1 ][ j – 1 ];
   }
   else
    MaxLen[i][j] = maximum( MaxLen[ i – 1][ j], MaxLen [ i ][  j – 1 ]);   
  }  
 }
 return MaxLen[Len(S) – 1][Len(T) – 1]; 
}

maximum is the simple function that find maximum of 2 numbers. Remember this function only returns the length of longest common subsequence only. Not the original such substring. We can find such substring in MaxLen array by back tracking and moving upwards. I will explain the logic for this solution some time soon.

I, Haroon

Quotes !

So the next quote in series is.

1. Our greatest glory consists not in never falling, but in rising every time we fall. By Confucius

2. The Greatest quote that fascinated me ever is,
Cogito, Ergo Sum (I think, Therfore I am) – By Rene Descartes

Categories: General