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.
