CSE 3101 - Design & Analysis of Algorithms

Summer 2008

How to present your work

This is a suggestion of how to prepare your assignment reports (and partly how to answer your tests). Any other way of presenting your work is totally acceptable given that conforms to the nature and requirements of this course. Communicating technical mathematical material is a skill required in (or should developed during) this course. Here are some suggestions that hopefully will help you to improve the presentation of your work (and reduce the risk of loosing credits - or help you to get partial marks):

In most questions you will be asked to devise an algorithm (for a given problem) and analyze its (time) performance. In this course every algorithm should also be accompanied with a proof of correctness and proper time analysis.
It helps your presentation if you begin every answer by stating (within 2-3 sentences) what is the problem you are solving and briefly state your results. Then you can elaborate by giving the (actual) answer.
Present your algorithm in English. Alternatively (or additionally) you can give the description of your algorithm in pseudo-code. Please be careful when expressing your algorithm in English. This means that you shouldn't be vague or ambiguous about its structure. You are strongly discouraged in presenting algorithms using specific programming language primitives (e.g. avoid using ++, -- or !=).
There are specific problems where the algorithm might be obvious (or more obvious) but it appears that it gets more involved to prove it correct. Apart from convincing yourself that your algorithm works correctly; the ability to provide convincing (mathematically valid) arguments on the correctness of an algorithm has to do with the ability to grasp its very structure. A goal of this course is to make you develop this ability. Unless the question explicitly specifies that you should merely give an indication of the correctness of your algorithm you are required to carry the proof of correctness in detail.
It's good to include (at least) one input example and show how your algorithm works on this input. Note that no example is sufficient, not even as an indication, to show the correctness of your algorithm.
Stating the running time should always be accompanied with a counting argument for the time analysis. Any assumptions about the data-structures you use (as a black-box) should be stated explicitly.
When arguing rigorously you should decide on how much detail you should give. It would be nice if you try to find a balance between detail and clarity. Moreover, the simpler (and shorter) the better your proof is. Note that messy, unnecessarily long and unnecessarily complicated answers involve the risk of losing marks.