Recursion, randomization, sorting and computations

Comment 1:

Divide-and-conquer vs. recursion?

Follow-up:

Divide-and-conquer is a general technique in which we divide the problem into small parts and then solve the smallers independently. Recursion is closely related to divide-and-conquer in that it is usually the most concise way to express a divide-and-conquer idea. However, a divide-and-conquer idea does not always need to be realized by using recursion. Indeed, sometimes, we would like to avoid recursion because it can be very slow, as you have seen (or will see) in Tutorial 1.

Comment 2:

Randomization?

Follow-up:

Let us consider a simple problem in order to illustrate the usefulness of randomization. This problem is about several important but related concepts: worst-case analysis, average-case

analysis, and probabilistic analysis. Consider the following “hiring” algorithm:

1) Set candidate best to be unknown;

2) For each of the n candidates, do the following:

3) Interview candidate i ;

4) If candidate i is better than candidate best, then hire candidate i and set best to be i ;

Assume that interviewing each candidate has a cost of c In and hiring a candidate has a cost of c H

(where c H > c In under normal circumstances).

(a)

Can you give the worst case total cost of the above hiring algorithm?

(b)

Assume that the candidates come to the interview in a random order, i.e., each candidate is

??? equally likely to be the best. Specifically, candidate i has a probability of -- to be the best

among the first i candidates. Can you give the average case total cost of the above hiring

algorithm?

Hint: You can consider to use the “indicator random variable” X i , which is equal to 1 if

candidate i is hired and 0 otherwise. Hence, the average number of candidates that are actually

hired is equal to the “expected value” (i.e., the average) of ∑ X i .

Answers:

(a)

The worst case is that every interviewed candidate is hired. Thus, the total cost is: c In n + c H n .

(b)

In this average case, the only change to the total cost is the hiring part. So let’s focus just on this

part. Specifically, as given in the Hint, the average number of candidates that will be hired is:

??? which in turn is equal to: ∑ -- . A good bound for this sum is: log n . Thus, the average

case hiring cost is just c H log n , which is much smaller than the worst case’s hiring cost.

The lesson we learn is that average case is sometimes much better than the worst case.

As you can see, it is helpful to assume that all permutations of the input are equally likely so that a probabilistic analysis can be used. Now, here is the power of randomization—instead of assuming a distribution of inputs (i.e., the candidates), we impose a distribution. In particular, before running the algorithm, we randomly permute the candidates in order to enforce the property that every permutation is equally likely. This modification does not change our expectation of hiring a new person roughly log n times. It means, however, that for any input we expect this to be the case, rather than for inputs drawn from a particular distribution.

Comment 3:

Quantum computing? Parallel processing? Biological computing?

Follow-up:

These are really exortic computing models that we will elaborate on in the later part of the course. Please be patient. Thanks!

Comment 4:

There are a lot of different mathematical ways of documenting/calculating numbers/codings. How come only a few can be applied to computing processing algorithms?

Follow-up:

Good point. But please note that not many mathematical ways of calculations can be realized, in a mechanical manner, using a computing procedure (i.e., to be carried out by a computer). For instance, think about integration in calculus, there are many integration problems that need very good “inspection” or insight to solve. Agree?

Comment 5:

Insertion sort?

Follow-up:

Please find the sketch of a computing procedure using insertion sort below.

(1)Given a list of numbers A[1], A[2], ..., A[n]

(2)for i = 2 to n do:

(3)move A[i] forward to the position j <= i such that

(4)A[i] < A[k] for j <= k < i, and

(5)either A[i] >= A[j-1] or j = 1

Now, it is not difficult to see that the number of checkings/swappings in lines (3) to (5) above cannot be larger than i . Thus, the total number of steps, i.e., the estimated running time, would be ??? , i.e., on ??? the order of n .

Comment 6:

Quicksort? Randomization?

Follow-up:

The Quicksort algorithm looks very similar to the algorithm that you have worked (will work) on in

Problem 3 of Tutorial 1 (about “searching”). So I leave this to you to write up the computing

procedure. You can also prove that the estimated running time is n log n .

On the other hand, I would like to supplement a bit more about the “randomization” part used in

Quicksort. Similar to the “hiring problem” in Comment 2 above, we need a certain “distribution” in the input list so as to realize the potential of Quicksort (or, divide-and-conquer, for that matter).

Specifically, in Quicksort, we would like to choose a pivot so that the resulting two partitions are of more or less equal size. It is reasonable to assume that if the list is somehow “totally random” (we will talk more about generating randomness later on), then it is likely that a randomly selected number from the list has a value right in the middle, i.e., it will divide the list into two equal halves. So just like the hiring problem, we will randomly shuffle the list before sorting and then, statistically, we would expect the list to be divided into equal halves when we partition it.

Comment 7:

P2P should be discussed/elaborated.

Follow-up:

We will spend some time discussing about P2P systems in later part of the course. Please be patient.

Thanks!

Comment 8:

We talked about our actions being monitored, even in P2P because we are accessing the Trackers. But what about the ISPs? They track everything we do. What about VPN (virtual private network)? Can it prevent ISPs from tracking us?

Follow-up:

Yes it is true that the ISPs are keeping track of our moves all the time. So when the law enforcement people need the information (with warrant), they will supply it. Even VPN (i.e., setting up the so-called private links, in the form of encrypted channels) cannot help because ultimately your IP address has to be revealed. Only the data can be encrypted. We will discuss more about Internet security and privacy in later part of the course.

Comment 9:

Feasibility of parallel processing? For example, in the Tower of Hanoi problem we are limited by the number of pegs and the rules of the game.

Follow-up:

Yes you are right. How to do things in parallel in a computer has been baffling researchers for decades.

We will discuss more about these difficulties later in the course.

Comment 10:

Isn’t it true that “recursion” is something just like mathematical induction?

Follow-up:

Yes you are absolutely right! Very good observation. Indeed, recursion, or even divide-and-conquer, is closely related to the “induction” concept. We try to “extrapolate” solutions of smaller problems to larger ones. That is the idea.

Comment 11:

The CPUs are evolving nowadays. Their computational speeds increase exponentially and this lowers the significance of the effectiveness of one algorithm to solving the problem as the CPUs can carry out the tasks equally fast and well. But still thinking of an effective algorithm is still challenging and worth continuing.

Follow-up:

Oh this one I cannot agree with you. Indeed, as you will find out in this course and we will also discuss in more detail soon, there are some problems that cannot be solved practically without a smart algorithm, even if you have thousands of processors at your service.

Applications of the recursive computing paradigm

Recursion is a computing technique that helps solve complex problems in a simple way, by using the result of the previous value of that function and finding a relation between the previous result, current result and the current value. The result we use would have been obtained using the answer for previous value, and the cycle would go on till we would reach a value for which we know the answer. This value, also referred to as the ‘base case’ would give us the answer to all the other cases, known as the ‘recursive cases’.

 For example, let us calculate the result of n! (Factorial of a number n) using recursion. In recursion, we  will use the value of n-1!, and multiply number n to it. To obtain the value of n-1!, it would use the value of factorial of n-2, and so forth. This continues till it reaches a value for which we know the answer. In this example, we know that the value of 1! is 1. Thus we would keep reducing the problem from n to n-1 to n-2…to 1, for which we know the answer. We would use this answer to find values of all unknown successive values. So we multiply 2 to 1! to get the factorial of 2 and we keep multiplying successive numbers to get the value of their factorials. The basic idea of recursion is to reduce a problem, and take it to the step for which we know the value.

Recursion is very useful in solving complicated problems, such as the traditional problem ‘towers of hanoi’.In this problem, we are given n number of disks, and our job is to transport the disks from tower A to tower C (as shown in the figure). However, we can only move one disk at a time, and also we cannot place a bigger disk on a smaller disk.

Picture Source: http://www.alper.net/wp-content/uploads/2008/03/hanoi.jpg

The problem is very complicated to solve with iteration. However, it is a small and comparatively easy to understand problem with the recursive approach. Here is the approach-

a)    Consider it is solved for n-1 disks, and we can move n-1 disks at our disposal.
b)    So, we move n-1 disks to tower B.
c)    Then we move disk n to tower C.
d)    Now, we can move the n-1 disks to tower C, over disk n, and the problem is solved.
e)    The problem for n-1 disks would have been solved by using the same procedure replacing n by n-1 and n-1 by n-2. We would keep reducing the problem, till we reach a value for which we know the answer. In this case, we know that for n=1, we move the disk 1 directly to Tower C.

Thus in recursion, we just need to find a relation that gives us the answer for ‘n’ and we believe that we know the answer for n-1. Though, in reality we do not know the answer to n-1. But we find that out by finding out the answer for n-2, n-3 and so forth till we reach a given value for which we know the answer. Hence, recursion makes problem solving easy compared to other approaches.

However, the disadvantage of recursion shows when it comes to computing. Recursion is a slower and more space taking process than iteration, thus making its efficiency lesser than iteration for the same algorithm. Recursion requires more space as it stores the values to be calculated in ‘stacks’. It is slower as function calls take time compared to calculations within the same function. To understand this, we can compare the computer to our brain. For example, if we were given a problem to add all numbers from 1 to 5. The iterative way would require us to add 1, and then add 2 to it, and result in us just adding just all numbers from 1 to 5 without thinking anything. However, a recursive approach would require us to start from 5, and add to it the sum of numbers from 1 to 4. This would require us to keep 5 in our brain and find the sum of numbers 1 to 4. This in turn would require us to keep 4 in our brain and solve for all numbers from 1 to 3, and repeat the cycle till we reach the base case, which is adding all numbers from 1 to 1, which we know is 1. So, recursion would require us to keep numbers from 2 to 5 in our brain which requires additional space. Also, it makes calculation slower than the iterative procedure, as we can see that it is more complicated for us to try and call the ‘function’ again and again, rather than simply adding the consecutive numbers as a part of the same function.
But we cannot forget the importance of recursion in daily life in solving complicated problems. Problems such as the towers of Hanoi are made so much simpler by using recursion! Also, recursion at times has solutions to problems which are faster than their iterative equivalents. For example, quick sort, an application of recursion is one of the fastest sorting techniques used in modern world!

Programming using stack

Problem:

A stack is a useful structure for storing data because it has many useful applications. For example, it can be applied in implementing recursive computing method. A stack is a “last-in-first-out” structure — data items are stored linearly as one item is placed on top of the other. The only two operations are: pop and push. The pop operation retrieves the top data item on the stack, while the push operation puts a new data item on the top of the stack. The figure below shows how a stack works:

(a) Can you write up a computing procedure for DFS using a stack instead of using recursion?

(b) Can you suggest a practical situation where we must use a stack instead of using recursion?

Follow-Up:

(a) The first possible version is as follows.

Stack_DFS1(x):

1. Mark x; Push(x);
2. if stack is empty, then end of algorithm; otherwise, do the following:
3.    y = top of stack (without popping it);
4.    if there is a neighbor z of y that is not marked, then do:
5.       Mark z; Push(z);
6.    else
7.       Pop;
8. go to Step 2.

Another possible version is as follows.

Stack_DFS2(x):

1. Push(x);
2. if stack is empty, then end of algorithm; otherwise, do the following:
3.    y <- Pop;
4.    if y is not marked, then Mark y;
5. for every neighbor z of y that is not marked, do the following:
6.    Push(z);
7.    go to Step 2.

(b) In the Web crawling application, we need to use a stack. In fact, crawling is done by many computers running the “search” (or explore) simultaneously. Each computer takes the next node to be explored from the top of the stack, downloads the HTML file, and then scans it for further hyperlinks. But when a new HTML document is found (i.e., a “neighbor”), no recursive call is made; instead, the new node is pushed onto the stack.

Yet one interesting question remains: when we see a HTML document, how do we know it is indeed “new” (i.e., not marked) so that we want to push it on stack?