CSE373—Data Structures and Algorithms for Nonmajors

Programming Assignment #4

Due: Friday, 12/9/05, 10:00 PM

Overview:

In this assignment, you will be implementing a graph representation, a classic graph algorithm, and a visualization of that algorithm.

Programming (60%):

The following files are packaged into the zipfile:

· vertices.txt – a list of vertices

· smallmap.jpg – map of UW campus

· Vertex.java – a simple vertex class. You are welcome to add to it.

· Edge.java – a simple edge class. You are welcome to add to it.

· BuildGraph.java – builds a vertex list and an edge list from a list of intersections.

· GraphUI.java – a collection of methods to help you visualize your graph. You are welcome to add to these and to share other low-level visualization code with each other. There’s a main here to demo some of the features.

You may create your own files/classes too.

Implement an algorithm of your choice: Dijkstra’s algorithm, Kruskal’s MST algorithm, or Prim’s MST algorithm.

If you’d like to implement a different algorithm (of equivalent or greater difficulty), you first need to get permission from the instructor. Your implementation should be efficient, as in, use good data structures (e.g. priority queues if appropriate) and avoid obvious redundancy. Likewise, if you would like to use data other than the data provided, you first need to get permission from the instructor. The flexibility is so you can challenge yourself, not so you can tailor the assignment to something you’ve done in a previous class.

Create a visualization of your algorithm in progress. You should use a combination of graphics and text in the textbox.

You may use code from the book, as long as you cite it. You may share low-level tools for visualizing, but you may not share code for the graph algorithms or get the code from any other source. Your visualization styles should be unique (i.e. you can share code that makes a vertex or an edge blink, but you cannot share code that makes a whole path blink in a certain way). If you have any questions/concerns about this, please ask. The intent is for you not to waste your time with Swing/AWT but instead to be creative and produce a cool result.

Visualization advice:

Use the sleep in GraphUI to control the speed of the visualization.

Animation is useful for continuous evolutions but can be distracting for discrete events that we normally don’t think of as transforming smoothly. A good animation does not distract from the task at hand but instead establishes temporal connectedness so that events in time can be followed one to another without getting lost along the way.

There are many dimensions in which you can encode information, for example, text, color, thickness, and texture. If you really want to go crazy, try adding sound to the mix.

Short Answer Questions (40%):

Put your answers to the following in a file called questions.txt (you can use Notepad for editing). You will be graded on content, not on spelling or grammar.

1) Describe the representation you used for the graph. Adj matrix? Adj list? What decorations did you add to the vertices/edges? In hindsight, did your choices work well? What would you do differently next time?

2) Give a description of what your visualization does and how to understand what it is doing. Give instructions (for the TAs) on how to compile, run, and use your program.

Bonus (0-10%):

We will award bonus to assignments that we feel have visualizations that are exceptionally creative, aesthetic, or pedagogical (probably between 10% and 20% of all assignments).

Compress all your code, auxiliary data, images, and questions.txt into a file called MyGraph.zip and turn in that file.

Turn in your work electronically from the “assignments” link on the class webpage.