Due date for projects: Friday Dec 6, midnight
Submission instructions: Please send the following by e-mail to the address: email@example.com:
- the source code, preferably as a link to some code repository or inside a compressed archive (zip, tar.bz2, or tar.gz)
- some of the problem data, either hosted in the repository or inside the file archive
- your report in PDF format
Graduate students must write their report in latex.
Guidelines for projects:
- choose the topic by Friday, Nov 1, 23:59. Please e-mail me your choice.
- you may work in teams of two. Both graduate and undergraduate students will be evaluated in the same way, and so an undergraduate student may pair up with a graduate student.
- Topic: choose a particular problem for which approximation algorithms are known or can be devised from other problems. If you are unsure, please see me. The project must implement at least two different approximation algorithms for the problem if you are part of a team; if you are alone, then you must implement at least one algorithm.
- tentative date for the project: end of November.
- a project report as a PDF file please. Grad students must use latex for document preparation.
- your source code with data, ideally as a link to bitbucket or github or some other public code repository. Alternatively, you can send me a bz2, zip, or tar.gz archive.
Project evaluation criteria:
- compilation: I should be able to compile and execute your code on the provided data, without problems. Target the architecure for a linux machine.
- description of the problem and the algorithm(s): describe the problem, the algorithms implemented and a proof of the approximation factor if the algorithm was not already discussed in class.
- data: describe in the report how you obtained the data. Be concise but rigorous. Include both randomly generated data and real data if you can obtain it. The data size should be as large as possible. Talk to me for ideas and advice.
- correctness: describe how you assessed the correctness of your code. Ideas: small separate code to verify the constraints, code that generates specific instances on which you know the results expected from the algorithms, etc. Provide appropriate details in the report.
- quality of the solutions: provide graphs in the report that show the quality of the solutions obtained. Give an a posteriori guarantee: either use the optimal solution which is published for some real problem instances that you download, or calculate the bound for the optimal solution. For plots, I recommend gnuplot. Provide details as appropriate.
- efficiency of the algorithm(s): explain your data structures and provide both a running time analysis like for Problem 5 in Assignment 1 and a plot with measurements from your experiments. Try to get an implementation that is as efficient as you can. Use library data structures as much as you can in your implementation.
Notes on code & data:
- do not submit executables, just the source code.
- submit just enough data so that the total size of your submission does not exceed 2Mb.
- briefly explain any specific steps required to get your code to compile and run.
Guidelines for presentations:
- choose a topic by Friday, Oct 25, 23:59. Please send an e-mail with your choice and provide references to where the result is described.
- Topic: choose a particular approximation algorithm for a particular problem. If you are unsure, please see me. The algorithm for the problem you chose must not have been already discussed in class. The topic can be from the text or from another paper, for example, consult part II of the text. Make sure you provide the reference to where the result is described.
- tentative date for presentations: mid november
- target your presentation for 35 minutes; we will have two presentations per class.
- organize your presentation as if you are teaching that topic in the class. You are encouraged to propose homework.
- try to present the algorithm gradually, starting with simple ideas and slowly building more complex ideas incrementally.
- you are free to choose the presentation style, slides, blackboard, or a mixture.
Presentation evaluation criteria:
- clarity: is the algorithm and the analysis clear to the audience?
- correctness: does the presentations seem free of errors?
The students attending the class will be asked to write comments, anonymously.