Projects for CSE 417 (Winter 2013)
CSE 417: Algorithms and Computational Complexity
The University of Washington, Seattle, Winter 2013
Purpose: In this project, each student has an opportunity to work independently or in a partnership of two on a topic of interest within a range of alternatives. There is not only a choice of algorithms, but also a choice of project types: theory or implementation.
Project plans are due Wednesday, February 20 at 5:00 PM, including choice of option, choice of topic, intention to work individually or in partnership, and if in partnerhips, your partner. You'll submit your plans via a Catalyst WebQ questionnaire.
 
Progress reports are due Wednesday, February 27 (corrected from Mon. Feb. 25) at 2:00 PM, also via Catalyst.
 
Final project reports and materials are due Friday, March 8. (Turn in your project materials via Catalyst by 2:00 PM.)
 
Suggested Topics:
 
The following topics are suggestions for projects to be performed by individual students. For partnerships of two, the project should either combine theory and implementation for the same topic, or involve an empirical comparison of two or more algorithms for the same problem. 
Divide and Conquer:
 Comparing Fast Fourier Transforms with alternative radices (radix 2, 3, and 4).
    (research this online)

Dynamic Programming:
 Stereo correspondences with real images.
    (research this online)

Network Flow:
 Directed Edge-Disjoint Paths Problem (K&T sec. 7.6)

 Undirected Edge-Disjoint Paths Problem (K&T sec. 7.6)

 Marketing Survey Design (K&T sec. 7.8)

 Airline Flight Scheduling (K&T sec. 7.9)

 Image Segmentation (K&T sec. 7.10)

 Business Project Selection (K&T sec. 7.11)

 Baseball Team Elimination (K&T sec. 7.12)

 Real-Estate Sales Management (K&T sec. 7.13)
I. Theory Option
 
Overview: Choose a topic and get the instructor's OK for your choice. The topic will be a non-trivial algorithm that has been presented in the literature or that is covered in Chapter 7 of our textbook. Write a report about it that includes a tutorial. Prepare and deliver a 12-minute talk on your algorithm.
 
Contents of the Report:
  1. The problem that your algorithm solves
  2. History of approaches to that problem
  3. Brief mention of related previous work by the inventor(s) of the algorithm
  4. Description of the algorithm ( in English and in pseudocode)
  5. Running time of the algorithm
  6. A simple example that illustrates effectively how the algorithm works
  7. A proof of the algorithm's correctness
  8. A proof that the algorithm's running time is efficient
  9. A list of your sources of information, with full references to each one

 
Contents of the Oral Presentation:
  1. Your (and possibly your partner's) name(s), major(s) and why you chose this topic. (about 1 minute)
  2. The problem that your algorithm solves (about 1 minute)
  3. Brief background on the problem and algorithm (about 1 minute)
  4. Explanation of the algorithm with walkthrough of a simple example (5 minutes)
  5. Your choice of proof of correctness or proof of running time (4 minutes)
You are encouraged, but not required, to use Powerpoint for your presentation. A draft version of your Powerpoint slides (or other presentation materials) should be turned in with the rest of the project on March 8. Talks will be scheduled to take place during the week after that.
 
II. Implementation Option
 
Overview: Choose a topic and get the instructor's OK for your choice. The topic will be a non-trivial algorithm that has been presented in the literature or covered in Chapter 7 of our textbook. Implement the algorithm in Python. Write a short report about it describing the algorithm, your program, and several test cases.
 
Contents of the Report:
  1. The problem that your algorithm solves
  2. Description of the algorithm ( in English and in pseudocode)
  3. Running time of the algorithm (using Big Theta, Big Omega, and/or Big O).
  4. Presentation of a basic example, showing input, output, and any key intermediate results.
  5. Presentation of one or more advanced examples, showing input, output, and (optionally) any key intermediate results.
  6. Complete commented code.
  7. A list of your sources of information, with full references to each one

 
Updates and Corrections: This page was last updated on February 24 (with a correction of the due date for progress reports).