Projects for CSE 373 (Winter 2010)

Projects in CSE 373

Project proposals are due Monday, Feb. 22 at 7:00 PM via Catalyst CollectIt. Preliminary code files, with graph construction and display working, are due Friday, Feb. 26 (corrected from Thursday), at 11:45 PM. Working code with basic functionality for demonstrations is due Sunday, Mar. 7 at 11:45 PM. Project reports are due at 11:45 PM on Sunday, March 14. Optional code updates are also due at that time.

CSE 373: Data Structures and Algorithms
The University of Washington, Seattle, Winter 2010

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 (with possible application to natural gas distribution, etc.).
2. PERT/CPM (with possible application to project management, party planning, etc).
3. Subgraph Isomorphism (with possible application to puzzle solving, chemical molecule analysis, pattern recognition, etc.).
4. Minimum Clique Covering (with possible application to breaking a large social network into smaller, compatible groups).
5. Optimal Routing (with application to airline flight routing -- itinerary planning-- according to schedules and connections).
6. Maximal Matching in a Bipartite Graph (with possible application to matchmaking at an online dating site).
7. Maximal Matching in a non-bipartite graph (with possible application to buddying-up at a swimming class).
8. All Minimum Spanning Trees for a graph (with an evaluation of each one in terms of graph statistics such as diameter, average branching factor, overall cost).
9. Graph Coloring with k Colors (with possible application to map coloring).
10. Graph Rewriting using a Graph Grammar (with possible applications to finding the resistance of series-parallel resistance networks, etc.).
11. Road network simulation, with a back-end algorithm such as maximum flow.
12. Network routing simulation, in which each vertex maintains a queue of incoming packets.
13. Graph Analysis via Parsing According to a Graph Grammar.
14. Social networking application with "friend suggestion" according to the number of independent paths between vertices.
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: Answer the WebQ project proposal questionnaire by Monday, Feb. 22 at 11:45 PM. The following questions are asked in the questionnaire.
What is your name?
Do you plan to work alone or in a partnership?
If a partnership, who is your partner?
Which of the 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 10 or 15. Figure out the names of these nodes. What edges are in your graph?
What special commands do you plan to support (analogous to PLAY-DEQUEUE in Assignment 1) and what should they cause your program to do?
How will you divide the responsibility for the different aspects of the project between the partners?

Project demonstrations are scheduled for Monday, March 8 and Wednesday, March 10. The demonstrations will be conducted in class. Each team should bring a personal laptop or arrange with a classmate who has one to share on each demo day. 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 Sunday, March 14.

Last updated February 17, 2010 at 10:15 PM.