CS 5114 Project Assignment, Version 1 January 31, 2000

As part of the course work for CS 5114 this semester, every student will carry out and report on a research project during the semester. Each student will select a different research topic on his or her own, with help from the instructor as needed. Each topic selected should be suited in subject for publication in a good journal or conference that publishes research in discrete algorithms; suitability of the topic is at the discretion of the instructor.

In the research, the student should aim for results that are sufficiently original to merit publication. A semester is usually too little time to reach such original results, but at least a plan of research that demonstrates a plausible path to original results is required in the final project report.

Both the quality of writing and the mastery of algorithms demonstrated in the reports will be evaluated. The point value of each component of the assignment can be found in the syllabus. In evaluating a report, the research results achieved will be weighed against the difficulty of the topic.

Your bibliography should include the sources that you derived information from, including journal papers, conference papers, books, web pages, and personal communications. For web pages, you should include the URL and verify that the URL remains reachable on the day you submit an assignment. In other words, you should not include a URL that is likely to disappear before the end of the semester. Personal communications might be something you discussed with the instructor, one of the GTAs, or anyone else. It is fine to seek advice from other students in the class as long as they are given credit for the advice and the work you submit is your own apart from that advice.

Electronic preparation of your project reports in L^{A}TEX is mandatory. Electronic submission is optional, except for the final project report, for which electronic submission is mandatory. The procedure for electronic submission is explained for each report.

Initial Project Proposal — Due February 18, 2000

A topic will typically be an algorithmic problem (e.g., traveling salesman problem or sorting) together with some questions about the problem that have not been asked and answered before in the literature. Here are some possibilities to help your thinking.

• Select a problem that has not been studied algorithmically before. All algorithmic questions are then open. It will be easier to look in a less established field, such as computational biology/bioinformatics.

• Select a problem for which there are several competing published algorithms. Find a way to differentiate among these algorithms through a combination of analysis and experimentation. The experimentation must include experimental design and “fair” implementation of each algorithm.

• Select a problem with known algorithms. Restrict the domain of the problem to determine how that affects the performance of the algorithms or how it provides opportunities for new, more efficient, algorithms. Alternately, look at the effect of variations in the problem on the efficiency of algorithms.

If you are having difficulty selecting a topic after a reasonable amount of searching using the resources provided on the CS 5114 web site, please seek the instructor’s help in identifying a topic. You can see him during office hours or (usually) immediately after class. Once you have a topic, you should write a paragraph about it and discuss the paragraph with the instructor for a few minutes before you work on the full proposal.

Electronic Preparation. The proposal for your project should be 1 to 2 pages long, prepared in 12 point type using L^{A}TEX (find skeleton.tex on the web site to get started). The proposal should have a title, the phrase “CS 5114 Initial Project Proposal”, and your name. There is no need for an abstract. In the body of the proposal, you should motivate the problem with a potential application, define the problem precisely, and indicate what kind of research results you are aiming for. You will want to have approximately three relevant references. You should also identify the source(s) of your topic, such as a technical paper or some source online. A sample proposal will be put up on the web site to give you an idea of the expectations for your proposal.

Electronic submission is optional. If you do submit electronically, send an email message to cs5114@courses.cs.vt.edu with the L^{A}TEX file, BibTEXfile, and any other files needed to make a postscript version as attachments. If you attach a postscript file, make sure it was created with the letter option of dvips. Optionally, you may submit all the files within a tar file. Use the subject line “CS 5114 project proposal” for this email.

Literature Review — Due March 24, 2000

Once you have received feedback and a grade on your proposal, you should look for more extensive resources in the literature. You should survey these in your literature review to firmly establish the current status of your chosen problem. In particular, you should justify your claims of originality for the approaches you proposed to attack the chosen problem. Notice that your literature review may demonstrate that something you proposed has already been done. This is fine. This is in the nature of research. Just modify your proposals a bit and explain in your literature review how your proposals have changed. Your literature review should contain approximately 15 references.

Electronic Preparation. The literature review for your project should be 5 to 7 pages long, prepared in 12 point type using L^{A}TEX (you should be able to build on your proposal source files). The literature review should have a title, the phrase “CS 5114 Project Literature Review”, and your name. An abstract is optional.

Electronic submission is optional. If you do submit electronically, send an email message to cs5114@courses.cs.vt.edu with the L^{A}TEX file, BibTEXfile, and any other files needed to make a postscript version as attachments. If you attach a postscript file, make sure it was created with the letter option of dvips. Optionally, you may submit all the files within a tar file. Use the subject line “CS 5114 literature review” for this email.

First Draft of Project Report — Due April 7, 2000

The first draft of your project report should start to look like a journal paper with introduction, literature review, precise project statement, precise terminology and notation, research results so far, planned results in the near future, conclusions, and bibliography. You should apply feedback from your literature review to this first draft.

Electronic Preparation. The first draft of your project report should be 8 to 12 pages long, prepared in 12 point type using L^{A}TEX. The first page should have the title you have been using, the phrase “CS 5114 First Draft of Project Report”, and your name. An abstract is optional.

Electronic submission is optional. If you do submit electronically, send an email message to cs5114@courses.cs.vt.edu with the L^{A}TEX file, BibTEXfile, and any other files needed to make a postscript version as attachments. If you attach a postscript file, make sure it was created with the letter option of dvips. Optionally, you may submit all the files within a tar file. Use the subject line “CS 5114 first draft” for this email.

Second Draft of Project Report — Due April 21, 2000

By this time, much of your research should be done, and the remainder should be well under way. The second draft of your project report should look like a well-written journal paper. Any research results yet to come should be identified.

Electronic Preparation. The second draft of your project report should be at least 10 pages long, prepared in 12 point type using L^{A}TEX. The first page should have the title you have been using, the phrase “CS 5114 Second Draft of Project Report”, and your name. An abstract is mandatory.

Electronic submission is optional. If you do submit electronically, send an email message to cs5114@courses.cs.vt.edu with the L^{A}TEX file, BibTEXfile, and any other files needed to make a postscript version as attachments. If you attach a postscript file, make sure it was created with the letter option of dvips. Optionally, you may submit all the files within a tar file. Use the subject line “CS 5114 second draft” for this email.

Final Project Report — Due May 4, 2000

The final project report should be a polished paper with no holes in the discussion. The conclusions should include a plausible plan for attaining any research results not accomplished during the semester.

Electronic Preparation and Submission. Your final project report should be at least 10 pages long, prepared in 12 point type using L^{A}TEX. The first page should have the title you have been using, the phrase “CS 5114 Final Project Report”, and your name. An abstract is mandatory.

Electronic submission is mandatory. If you do submit electronically, send an email message to cs5114@courses.cs.vt.edu with the L^{A}TEX file, BibTEXfile, and any other files needed to make a postscript version as attachments. If you attach a postscript file, make sure it was created with the letter option of dvips. Optionally, you may submit all the files within a tar file. Use the subject line “CS 5114 final project report” for this email.