CS 840

Project

General expectations of a project (It is quite reasonable to deviate from these, but check with me first):

• Read 2 or 3 papers in an area related to this course. You may start with a fairly recent paper and realize that in order to fully understand that paper you have to read a couple of others on which it builds.
• Understand the results and approaches
• Apply, extend or implement these results:
• Application could be to some appropriate problem, perhaps one in your own research area.
• An attempt to extend the results may or may not be successful, in either case you should explain the avenues taken and why they were successful or unsuccessful
• In some cases, implementations may be appropriate
• Tell me what you intend to do preferably by October 30. email and/or personal on line discussion is best, I can/will give feedback.
• Present your preliminary findings in class via slides and audio in the last 3 weeks of term.
• The final written report should summarize the papers read and your findings in a 5 to 10 pages (due December 20)

Projects are expected to be the work of one or two students. (I usually encourage two but this year connections are tougher to make. Feel free to email your classmates to find a partner … either before or after you decide on a topic.) Expectations for two person projects will be appropriately higher than for a single person. If you would like to do something for academic credit beyond this course, this is possible provided all parties involved are appropriately informed and agree. This could be projects in two courses taken concurrently could be closely related or a portion of a thesis.

Starting points:

A particularly good starting place is Space-Efficient Data Structures, Streams and Algorithms LNCS 8066 (otherwise known as "Ianfest"). Many/most of the articles are fairly easy to read surveys with lots of great references.

A more direct approach is to try fairly recent conferences and journals, say from the last 3 years or so. Most papers are accessible when logged on from the university: (Only a modest fraction of the papers in any conference or journal are relevant to this course. Conferences have a 2 to 3 year lead on journals, so try the following conferences)

• ACM-SIAM Symposium on Discrete Algorithms (SODA)
• European Symposium on Algorithms (ESA), Proc. in Springer LNCS series
• Workshop on Algorithms and Data Structures (WADS), Proc. in Springer LNCS series
• Scandinavian Workshop on Algorithms and Complexity (SWAT), Proc. in Springer LNCS series
• International Symposium on Algorithms and Computation (ISAAC), Proc. in Springer LNCS series
• ACM Symposium on Theory of Computing (STOC)
• IEEE Symposium on Foundations of Computer Science (FOCS)

Conferences and journals also vary in average quality. SODA is very strong by both metrics. STOC and FOCS are very high quality but also rather broad in scope.