School of Computing, National University of Singapore

(Leong Hon Wai, July 2000; Revised: July 2002)

About Mathematics, Proofs, and Level of Detail for Writing Proofs

**Answer:**
Analysis of algorithms generally require discrete mathematics.
But, for a better idea, you should
be familiar with the mathematical foundations covered in
Chapters 2-5 of the text [CLRS01].

(Yes, these are covered in CS3230. I expect
the students to know them.)

**Answer:** **YES! Of course!**

This is an advanced course. You **expect** there to be
proofs to justify your results and to justify the running
times of your algorithms.
So, expect there be quite a bit of proofs in the lectures *and
in the homeworks*.

Actually, it should be common sense that
this is **unavoidable** if we want to tackle
any advanced analysis of algorithms and push for performance.

**Answer:**
Let's discuss some of the
issues regarding the level of detail you should be using for proofs
that you write for assignments in this class.
The underlying problem is that there are some statements which you should
be able to make which are clearly ``obvious'' and which we will not question.
For example, there is certainly no reason why you need to reprove the laws
of algebra any time you want to add two numbers. Unfortunately, there is
no clear cutoff point for what is obvious and what is not. So there is
a bit of judgment involved for us, as the staff, in determining what we
agree is a fair level and what is not.

The ``acceptable'' level of detail depends very much on what we are
asking you to do in a given problem. Anything that is directly related
to the ``focus'' of the particular problem should be proven clearly. In
doing so, you may omit proofs of facts which have been seen earlier in
this course, or which have clearly been assumed to be part of the prerequisite
courses. Beware, however, that the statement which you are saying is ``obvious''
is in the *exact* form which has been seen before.

Regarding material covered in prerequisite courses,
only assume as ``obvious,'' things which we may safely assume
that everyone knows and which are *not* the focus of the problem
you are solving.
For example, if you are designing an advanced algorithm and you need
to sort *n* items, then of course you may simply say that this
can be done in O(n lg n) worst case time, without explanation.
If you have a sorted array, and you want to locate an item,
you can simply state that you will use binary search,
and this required O(lg n) time.
However, if the focus of a problem is to prove the correctness
of Prim's MST algorithm, you may not simply say ``We saw this
in CS3230, and it was proven correct then.''

What you should *never* do is attempt to prove the correctness
or the running time of an algorithm you give
for a new problem by saying that it ``looks like'' an algorithm
which solves some other problem we have seen.
This is too loose. If your intuition tells you that what you
have done is similar to mergesort,
maybe that will help you design a proof,
but a reference to mergesort is not formal unless
you explain what the similarity is and why our knowledge of
mergesort automatically should apply.
For example, if you can directly prove that your new algorithm
has a recurrence T(n) = 2T(n/2) + O(n),
then at that point, you can certainly claim that
this recurrence is ``obviously'' solved by T(n) = O(n lg n),
since we solved this recurrence for mergesort.

However, if we asked you to design a new algorithm for finding the median of two pre-sorted lists. As it happens, the natural algorithm for solving this problem was similar, in spirit, to binary search. However noting this similarity proves nothing as they are not the same algorithm, and they do not solve the same problem. If you wanted to prove why the running time of your new algorithm was O(lg n), you could instead use your intuition to notice that in a constant amount of work, your algorithm decreases the problem size by some fixed fraction. Therefore your algorithm has a running time such as T(n) <= T(2n/3) + O(1), and at that point we have seen using the Master Theorem, that this recurrence solves to O(lg n). Furthermore, the correctness of your algorithm has nothing to do with the correctness of binary search. Your proof of correctness must have depended on the definition of the median element(s) having equal number of elements less than and greater than it. Therefore, you needed to prove that none of the elements which you eliminated could have been the median, and further that you were certain to throw away exactly the same number of elements above and below the median, and so the median of your new subproblem would certainly be the median of the original problem.

The general point in this last example is that each problem we give you has some technical difference between other problems, and you should be giving the full details for any claims that you make about this new problem, since no known results about other problems automatically apply.

About Proofs in CS5234

pagecount: /home/course/cs4234/public_html/def-msg.html: No such file or directory