Notes about the Final Project

The project is intentionally left to be open ended and you can try to make it more exciting for yourself. You are supposed to choose a theory paper (appeared in any of the theory conferences, FOCS, STOC, SODA, ICALP, ESA, APPROX, PODC, etc). The paper is supposed to be relatively recent, say it is to be published not earlier than 2000. You can make groups of at most 2 people working on the same project. Please send me your group and the paper that you would like to work on by Sunday Feb 19th.

For the final project you can choose from one of the following 3 options:

Option 1: Write a summary of the paper. Your summary should contain the following items:

Option 2: For this option you should do an empirical study of the paper. In most theory papers typically there is no empirical evaluation. In this case you are supposed to implement the algorithm proposed in the paper and run it against some test cases. You may generate your test cases or ideally you may use actual data from real world applications. It would be ideal if you compare the performance of the algorithm with a ``greedy'' algorithm or any reasonable algorithm that come to your mind. Please write a report describing the algorithm proposed in the paper, a description of your suggested ``greedy'' algorithm and the details of your findings. Please also send in your code and your test data.

Option 3: This is my ideal final project. In this case you are supposed to relate the paper to your own field of interest. For example, you may modify the algorithm suggested in the paper and add a heuristic on top of it and run it against a real world problem in your field of study. In your report please describe the algorithm in the paper and say your modifications. Then, go over the problem in your area that you are trying to solve. Then, describe the test data and the performance of your suggested solution for those test cases. Theoretical justifications for your suggested solution would make this a great project.

You should send me your project by the last day of the classes, March 10th. Back to the main page