Projects in CSE 373
Project proposals are due Monday, Nov. 17 at 11:45 PM via Catalyst CollectIt. Preliminary code files, with graph construction and display working, are due Tuesday, Nov. 25 at 11:45 PM. Complete working code is due Tuesday, Dec. 2 at 11:45 PM. Project reports are due at 11:45 PM on Monday, December 8. Optional code updates are also due at that time.
CSE 373: Data Structures and Algorithms
The University of Washington, Seattle, Autumn 2008
Requirements: All projects must implement graph construction and display within the Visual Data Structure Applet Framework. Each project will also implement specific functionality for the selected topic.
Project Topics
1. Maximum network flow using Max Flow Min Cut
2. PERT/CPM
3. Subgraph Isomorphism
4. Travelling Salesman Problem
5. A* Graph Search
6. Maximal Matching in a Bipartite Graph
7. Maximal Matching in a non-bipartite graph
8. All Minimum Spanning Trees for a graph.
9. Graph Coloring with k Colors
10. Graph Rewriting
Other graph algorithms might be good bases for projects. If you have a particular graph problem or algorithm you are anxious to work on, check with the instructor.
Graph Construction and Display Commands: For all projects, support the construction and display of a graph with commands such as the following. 
NODE N1 150 200 Chicago
NODE N2 300 250 New York
EDGE E1 N1 N2 711
HIGHLIGHT N1
HIGHLIGHT E1
UNHIGHLIGHT N1
Here the first argument to each command is an identifier for the node or edge. In the NODE command, 150 and 200 are the X and Y coordinates, respectively, for the location of the node in the display at the default scale. The names "Chicago" and "New York" are string labels for the nodes. Each edge is specified with its own unique identifier, the IDs of the nodes that represent its endpoings, and possibly a cost or distance value (in the above example, 711 is the number of miles from Chicago to New York.) A HIGHLIGHT command causes the specified node or edge to be graphically highlighted. This can be useful in showing the important parts of a graph in a demonstration of an algorithm.
Project Proposals: Turn in a text or .doc file via Catalyst CollectIt before 11:45 PM on Nov. 17. The file should contain the answers to the following questions.
What is your name?
Do you plan to work alone or in a partnership?
If a partnership, who is your partner?
Which of the graph algorith topics are you selecting?
What is a possible application scenario for your technique? (e.g. Road network in Washington State, shipping lanes in the Pacific).
Make up an example graph for your project, with a list of the nodes and a list of the edges. You should have at least 5 nodes and maybe more like 15.
Project demonstrations are scheduled for Wednesday, December 3 and Friday, December 5. They will take place in MGH 030 (basement of Mary Gates Hall), on Wednesday form 12:30 to 1:30, and on Friday, from 12:30 to 2:30. On each day, demonstrate your project to at least two classmates and perform at least two peer evaluations of others. Use the official forms for your evaluations. You will receive participation credit for the first two forms you complete as a reviewer and for the first two complete reviews of your project by others (on each of the two days).
Project reports are due at 11:45 PM on Monday, December 8.
Last updated November 30, 2008 at 6:38 PM.