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]. (This will be quickly reviewed in CS5206, but you should already be familiar with them.)
(Yes, these are covered in CS3230. I expect
the students to know them.)
Answer: YES! Of course!
This is a graduate course on algorithms. 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 relating to the level of detail you should be using for your proofs in your solutions for this class. On the one hand, there are some statements that are clearly very ``obvious'' and these you can just state. 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.
pagecount: cannot get configuration data from database