CSC 382, Analysis of Algorithms
Group Project
For this project you need to make groups of 3-6 people and choose one of the following topics. Most of these topics require you to write a short paper and present it in class (20 points). For those you have the option to just submit a paper and not present for only 10 points. A list of topics: 1. Linear Programming 2. Approximation Algorithms 3. Max-Flow Min-Cut 4. Cryptography: Asymmetric Encryption 5. Complexity Theory 6. Programming Project: Implementing Algorithms, Comparing Running times (10 points, no presentation) For some topics you can find information in the course textbooks (and other textbooks). For the rest, you must research on your own - but I am willing to give suggestions if I have any. You may suggest another topic as well, but I need to approve it.

Requirements
Each paper is expected to be 3-5 pages long (single-spaced and at 11pt) and it should include references to your sources (which should be more than just Wikipedia). As long as the paper is complete and well-written, the length requirements should not be too important. However, more than 5 pages would be an overkill and less than 3 might not let you give the necessary information and explanations. As for the actual contents of the paper, you should address your classmates, who will receive a copy of the paper in class and before your presentation. You should explain the topic you have selected and give an appropriate

1

2

example. The specifics may differ depending on the actual topic. For example, for 1 you should explain the Linear Programming technique, why it works and when it is used and explain for a specific problem how we can use the technique to solve it. For 2, you would explain what an approximation algorithm is, how it is evaluated (Between two approx. algorithms, how do you tell which one is better? In the case of regular algorithms, you would just compare their running times.), and how a specific problem can be solved using an approximation algorithm. I have more specific instructions to give for each topic, but this will be done after you have formed groups and selected topics. Your presentation should analyze the same contents and it should last about 15-20’. If you use slides, this roughly translates to about 15 slides. Each group should have up to 6 people. Everyone in the group will get the same grade. For both the presentation and the paper, you should be clear and you need to show an understanding of your topic.

Timeline
The following timeline is strict. You should really try to complete everything as much ahead of time as possible, so that you can ask me for advice if you have any issues and so that I can let you know in advance if something has gone wrong. Monday 11/17 By then you should decide the groups and the topics for each group. Send me an email for each group declaring the people it is made of and the topic you chose. After you have done so I will give you more specific instructions. Monday 11/24 By then you should send me a short summary/outline of your paper and talk. It should outline all your main points. For example: We examine G¨del’s first Incompleteness Theorem. It was o proven by G¨del in 1931 and claims that for every axiomatic o system for arithmetic there are true sentences that cannot be proven to be so. Then we examine its implications for Hilbert’s program and mathematics in general and how it eventually inspired the birth of Computer Science. Sources: Wikipedia and two random people from the street.

3

Wednesday 12/3 Your full paper is due (only if you are giving a presentation). Monday 12/8 and Wednesday 12/10 Presentations. If you are not giving a presentation, then your full paper is due on Wednesday 12/10.

Not so Important Information
My email address, in case you forgot it/don’t have it/don’t want to bother looking it up: AAchilleos@gc.cuny.edu Google is your friend. Often there are classes and notes online dedicated to some of these topics, while Wikipedia is not always the best or easiest choice. Do not try to analyze something too difficult, only what is important for your topic. For example, there may be several problems that can be solved by linear programming; pick an easy, but not trivial, one. These topics are already new to you and can be confusing when encountered for a first time, while most important task is for you to analyze your topic’s central idea clearly. If something is unclear, ask. Good luck.