Due date: December 7

Here a list of possible topics for your project. Please select one and send me a message indicating your choice. You can also propose a different topic, however, you should get my approval on your topic before you start working on it.

Every student is required to write a report. Your report must reflect your understanding of the problems and algorithms that you have studied. Here are some of the things that I might look for when reading your report:

Below there is some information that might help you write your report.


  1. Survey Papers

    For each one of the following projects you are required to read, understand, and critique several papers (at least 3) on the proposed topic, and write a report on them. For some of the topics I list some papers that might help you get started. Part of your job is to find papers relevant to the topic of your choice.

    You must use a unified notation and style when describing the different problems, solutions, and ideas discussed in the selected papers. Your study must focus on the algorithmic aspects of your topic.

    The report should contain a clear description of relevant algorithms and a sketch of their complexity analyses and proofs of correctness. Several of the papers that you will read requires some effort on your part to understand them. Your report should contain clear explanations of the algorithms along with intuition explaining why the algorithms work, or why they perform as claimed.

    As mentioned above, a very important part of the report is your critical analysis of the problems and algorithms that you study. Try to propose ways in which the algorithms can be improved. It is not essential that you give a formal proof that your ideas will improve the algorithms, but you should explain the intuition behind your ideas and why you think that they might work. Discuss open problems related to the ones that you study, or other problems that could be solved by using the algorithms that you study.

    The mark that you will get will depend on how clearly your report reflects your understanding of the topic that you have selected. If your report is a mere transcription/copy of portions of the papers that you read, then your mark will no be good.

  2. Experimental Evaluation of Algorithms

    Experimental evaluation of algorithm requires implementing algorithms and fine tuning them so that they perform well on "typical" instances. For each one of these projects you must implement several algorithms (at least 2) and compare their performance (either their running time or approximation ratios) over a carefully selected set of test inputs.

    You must explain how the test cases were selected and generated. Argue that the results of theses tests are representative of the true performance of the algorithms that you have implemented. From the tests, try to discover ways of making the implementations faster/better. Report your findings. Also, show the instances for which your algorithm has the worst running time/approximation ratio, and explain why this is the case.

    Some of the algorithms that you can evaluate are for the following problems. Look at the references given above for details on the algorithms.

  3. Implementations