CS5234 - Combinatorial and Graph Algorithms
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


Mathematical Proficiency for CS5234

Question: What level of mathematical proficiency is required for this course?

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.)


Are there Proofs in CS5234?

Question: Will the course place a lot of emphasis on the mathematical proofs and analysis of algorithms?

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.


Level of Detail in Proofs

Question: What level of detail should be used for proofs that you write for assignments in this class?

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.

Some Examples

Let's say the focus was on asymptotics, and you were asked to prove that f(n) + o(f(n)) = O(f(n)). Because this was the focus of the problem, we expected an extremely detailed proof of this fact using the immediate definition of the asymptotic functions. Of course, if you are analyzing an algorithm for any other problem and see that one part takes O(n log n) time and another part takes O(n) time, you may certainly conclude that the overall running time is O(n lg n) without another word.

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

Error Message From pagecount

A FATAL ERROR OCCURRED

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