CS3364 - Design and analysis of Algorithms, Summer I / 2004

Final Project

Please send me which problem you picked by Friday, June 25, 2004, 10 am, or tell me in class.

This is due Wednesday, June 30, 2004, 10 am

Background

You should now be proficent enough to solve any problem with the help of extra documentation.

Problem

Pick any problem from the ACM Problemset Archive. Please note that the problems have a percent number, which gives a good indication of the difficulty level of this problem. The Problem you pick should be between 10% and 50% and should be online-judgable. Please pick a problem that is appropriate for you personal skill level (=current grade). If you want an A+ in this class, pick a problem that has at most 20%. To avoid possible cheating no two students should pick the same problem.

Programming

Solve the problem. If possible, use C/C++/Java/Pascal, so that you can test your solution online. This time you may use all features of your language, etc., as long as they come with the base install of your compiler (NO extra libraries). If you uses C++ please see the notes on C++

Please send me your solution, along with any test-data you have used.

Presentation

The presentations are going to be on wednesday and thursday in class. The order will be based on volunteers or randomized, so you should be ready on wednesday! You presentation should be about 10, but no more than 15 minutes long. You should:

  • Shortly describe the problem (unix ls: given a list of names, output them alphabectically and top-down left-right)
  • Describe which part caused the most trouble (Not the sorting, but the output on unix ls)
  • Describe which algorithm you used to solve this problem. If time permits, give a short overview over the algorithm, if not, just something like "I used merge sort, which is a O(n log n) sort, I used Dijkstra, which searches for shortest path, etc."

For the presentation you may use transparencies, slides on the computer or the board.

Grading

Both parts (programming + presentation) are going to count about the same (8/10 or 9/9). Since the grades will be fixed by thursday, there will be no late arrangements.

Submission

Submit the programming part eletronically, either by putting them on the unix accounts in the cs department in a folder that I can read, or by sending them via email to max@berger.name