Recurrence Relationships

आपका स्वागत हैं| मैं हूँ प्रोफेस्सर रिद्द्ले...

Professor : In the last class, I told you about Asymptotic notations. In this class, we shall study how to solve recurrence relationships. You have already come across a recursive algorithm like Merge Sort, that has a recurrence relationship given by,



We found that, the solution to this recurrence is theta ( n lg n). In this session, I am gonna teach you a few methods to solve in general any given recurrence relationship.

Tim : Professor, I would like to know what are the methods to solve a recurrence relationship ?

Professor : Of course ! They are

• Substitution Method
  
• Recursion Tree Method
• Master Method

Friends, there's no general method to solve a recurrence relationship. There are a few techniques that work some of the times. If you are lucky, yours will work for you.

So, class let's begin with the Substitution Method.

Substitution Method -
Substitution method has the following steps
1. Guess the solution - So, you say, "Oh! the running timer must be roughly bounded by n^2.
2. Verify if the recurrence satisifes the bounds using induction. Yeah, Substitution method uses Mathematical Induction.
3. From here we usually get the constant c and n0 for free.

Ed : Professor, could you illustrate to us, how to apply this method. I read this recurrence the other day ....



Professor : Okay, so let's solve your example Ed.
Let's guess the solution. You might wonder, what a stupid method! Asks you to guess the solution right at the beginning... But, lemme tell the solution you guess, this method can correctly tell how good your guess is.. whether your solution is right, wrong, or you are nearing the solution...

Well, what function multiplies the number by 4, if the argument is doubled ? If you think it must be . So, prima facie our guess is, it is bounded by O().



But, let's be a little liberal and check out if T(n) is bounded by . So, we'll first see how its done the easy way, and then we'll try to get the right answer by a considering a tighter bound.



So, we've proved the bounds. We shall now prove the tighter bound .

Lee : Professor, shall we proceed in the same way, we did as above ?

Professor : Yes, that's right! Let us solve it together.



Well, this may happen sometimes. You see, you may guess the asymptotic bound correctly, but, somehow your math doesn't verify it in induction. And this happens, because inductive assumption is not strong enough. So, when you encounter such a problem, give it a shot by subtracting certain lower order terms.

Aymptotic Notation

So, let's learn about some mathematical tools which you can use to study, analyse and compare algorithms. Unfortunately, this is highly mathematical..

Big - Oh Notation






Big Omega Notation

Just as O-Notation provides an asymptotic upper bound on a function, the omega notation provides an asymptotic lower bound.





Asymptotic Notations in Equations in Inequalities (Macro convention)
The asymptotic notation can also be used in mathematical formulas. We have already defined the Big-Oh notation as a set. What happens when a set appears in a mathematical formula? What happens when we use O-Notation in a formula e.g.

Till now, we only defined O-notation, as something equals O(some other thing).
But it is useful to have big-Oh in a general mathematical expression.

A set in a formula represents an anonymous function in that set.






Theta Notation





So, the theta notation provides not just the asymptotic bounds but tight asymptotic bounds. In practice, we always want tight upper and lower bounds.

Strict's Notation - Little Oh and Little Omega
Like Big Oh and Bog-Omega notations, we have little Oh and little Omega notations.The bounds they provide are not asymptotically tight.

More about the design and analysis of Algorithms

Is Insertion Sort fast enough ?





















Divide - and - Conquer Algorithm
Now, running an organisation is no easy task. Planning, forecasting, monitoring, controlling, handling the finances, allocation of man-power and resources. There are a lot of things to be done. But no single individual does all the stuff by himself. An organisation has a strucutre. There is division of labour amongst the employees of the organisation. Thus, we break down a complex task into a number of sub-tasks.

So, when you can't do the whole, chop it off into small parts, and tackle those individually. If a particular part is still big enough, we further decompose it into smaller sub-parts. This is the core idea behind divide and conquer approach.

• Divide - Divide the given problem into sub-problems.
• Conquer - Solve the sub-problems if they are small enough, or divide them recursively.
• Combine - Combine the solutions of the sub-problems to construct the original solution.

Merge Sort Algorithm

• Divide the unsorted array into two sub-arrays of size n/2.
• Recursively sort the two sub-sequences using Merge Sort.
• Merge the two sorted sub-sequences to produce the final array.

The key sub-routine here is the Merge Sub-routine...

void merge(int A[], int low, int high, int mid)
{
int n1,n2,i,j,k;
int L[20],R[20];

n1 = mid - low + 1;
n2 = high - mid;

for(i=0 to n1;i++)
L[i] = A[low+i];

for(j=0 to n2;j++)
R[j] = A[mid+1+j];

for(i=0,j=0,k=low to high,i less than n1,j less than n2;k++){
if(L[i] less than R[j]){
A[k] = L[i++];
}
else{
A[k] = R[j++];
}
}

while(i less than n1)
A[k++] = L[i++];
while(j less than n2)
A[k++] = R[j++];

}

In each individual step, we look at the two elements in the list L[] and R[] and find the smaller of the two, and advancing the pointers into the array, so that I know what the current head of that list is.

The while loop that runs from p to r, defines the loop invariant. At any point k in the algorithm, A[p...k-1] is always sorted. We can use this loop invariant to prove the correctness of the algorithm. As you can see, the merge sub-routine takes theta(n) time.

Merge Sort will now be performed as follows :

void mergesort(int a[], int low, int high) {
int mid;
if(low less than high)
{
mid=(int)(low+high)/2;
mergesort(a,low,mid); mergesort(a,mid+1,high); merge(a,low,high,mid);
}
}

Analysing Merge Sort

























Recursion Tree for 2T(n/2)+cn
Well, let us build a recursion tree for the recurrence T(n)=2T(n/2)+cn which is a more explicit representation of the recurrence we want to solve...






Thus, the Merge Sort algorithm is asymptotically faster than Insertion Sort...!

Role of Algorithms in Computing

Knuth in his book says that the word algorithms may have been borrowed from the name of 9th century Persian Mathematician, Muhammad Ibn Musa Al-Khwarizmi.

Algorithms have been used to great extent in the human genome project to find the 1,00,000 pairs that make up the human DNA. This includes algorithms like String Matching to detect patterns etc. Algorithms are used on the Internet to find a good path for the data to travel on. Everyday on the Internet, we send a lot of information such as Bank Account data, Credit card numbers, passwords. Well, you need to protect this data from theft, otherwise someone might steal this data and misuse it, impersonate you. Thus, the science of Cryptography and digital signatures uses many algorithms. Genetic algorithms often imitate the biological processes such as mutation, reproduction etc.

To save network bandwidth and storage space, data is compressed. The science of Data Compression uses Compression algorithms. In the field of Digital Image Processing, algorithms are used to enhance images, to extract characteristic features of images etc.

So, what's this subject about ?
Here we study, different ways to solve a problem. It is the theoretical study of computer programs, their performance and resource usage.

What things are more important than Performance of a program?

• User friendliness
• Reliability
• Maintainability
• Security
• Functionalities and features
• Cost
  

Why study the performance of Algorithms ?
From what I have understood is the following -

• If computers were infinitely fast and memory was free any correct algorithm would do.
• But, computer speeds are fast, but not infinite. Similarly, computer memory is a bounded resource. Hence, we need to the performance algorithms.
• Basically, we are concerned with how fast things run!
• As rightly pointed out in the video lectures, performance is the demarcating line between the feasible and the infeasible. Well, no matter how good your program is, if it doesn't run, it just doesn't work out for you.

• In the world of computer programs, the Barter system is still being used. You can use performance to pay for all the other things like User-friendliness, Security etc. So, performance is like currency or money. If a user wants good, user friendly interface you write a program in Java. Although Java is much slower than C, Java has this rich set of Object Oriented features, so that the user-interface is easy to use. Thus, you spend by a factor of 2 or 3 on performance, to get an increase in user-friendliness.

Insertion Sort Algorithm

The insertion sort algorithm is given as follows :
void main(){
int A[] = {5,2,4,6,1,3};
int length = 6;
int i,j,key;

/*Insertion Sort*/
for(j=1;j=0 && A[i]>key){
A[i+1] = A[i];
i = i - 1;
}
A[i+1] = key;
}

for(i=0;i

Sorting problem is one of the oldest problems in Mathematics. The above algorithm works as follows. At any point j in the algorithm, all the elements A[1...j-1] are always sorted. This is the loop invariant. Well, so each time, in every loop, we add one element A[j] to the stuff that's already sorted A[1...j-1]. And how do we do that ? Find an appropriate place for A[j]. We simply keep copying the elements, till we find the position for A[j].

Running time of an Algorithm
Running time of an algorithm depends upon the following two things :

• Depends upon the Input - (Sorted vs. reverse-sorted)
• Depends upon the Input Size n - Sorting 6 elements vs. a Billion elements. The more stuff you have, the more time it takes.

Running time in general depends upon the input size. So, we express the running time T(n) as a function of the input size n...

As far as Running time is concerned, we generally want Upper Bounds on the running time. We would like to know, what's the maximum running time of an algorithm, the maximum it could possibly take... The reason is simple, it presents a guarantee to the user. So, we are usually interested in an upper bound on the Running Time, because everybody likes a Guarantee.

Well, we do different kinds of Analysis on computer programs :

• Worst Case (What we do usually) -
  T(n) = Maximum time to run the algorithm on any input of size n.
• Average Case(We do it sometimes...)-
  Average running time T(n) =
  Average (Running time of an input)x(Probability of that Input)
  
  So, it is the expected running time over all inputs of size n. But, how do we know the probability of an input. We don't !! So, we make an assumption... And that assumption is called a statistical distribution!
• Worst Case(Bogus) - You can cheat. Take some input for which the algorithm runs fast...

What's Insertion Sort's worst case time ?

• Obviously, it depends upon the computer. Are you running insertion sort on a big supercomputer or on your mobile phone or PDA? They have different computational capabilities...

How do we compare two algorithms ?? Two options..

• Relative Speed - We can run two algorithms on the same machine, and talk about their relative speed.
• Absolute Speed - It doesn't matter what computer the algorithms are run, we must be able to compare them in terms of absolute speed!

So, we pull out a BIG IDEA from our Math background, and that BIG IDEA is called Asymptotic Notation.

Asymptotic Notation - Simple and easy to use!
Let's see the theta Notation...












































Worst case of Insertion Sort

Cormen Leiserson Rivest Solutions

Well , theses are some of the solutions that I have made for the exercises given in the bible of algorithms, "Introduction to Algorithms" by Cormen Leiserrson and Rivest. I will be updating the solutions as and when I solve the exercises... Here's the link...
Cormen Leiserson Rivest Solutions