CSE 373 -- Data Structures and Algorithms

Winter 2001

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 5

Version 1.0 of February 25.

Applications and In-Depth Studies 

Due dates and times: See the section below on "Timing", because some portions of the assignment must be completed prior to the applet deadline. The final applets are due Thursday, March 8, 2001, at 6:00 PM.

Turn in your documentation web page for this assignment by filling in the A5 online documentation submission form.

Title: Applications and In-Depth Studies.

Purposes: To explore a data structure or algorithm in depth.

Instructions: Do option 1, 2, or 3.

Option 1 (for individual students, not groups). Develop a novel application of a qualifying data structure or algorithm.

A qualifying data structure for Option 1 is one of the data structures presented in the text. Your application (which should be in the form of a Java applet) should include the same kind of TextArea interface to the application that we have been using for applets.

Application ideas should be proposed by Tuesday, February 27, at 6:00 PM using the online form.

Your application should contain the following elements:

  • A piece of descriptive text that poses either a fictional or a real scenario at the level of detail and in the approximate style of the thought questions given for Assignments 3 and 4.
  • An applet with a TextArea that accepts inputs that correspond to the natural events for the application.
  • Clear visualization of the data structure in the applet, so that the state of the structure is clear from the display.
  • The text for a full demonstration, so that a user can copy the text from the web page, paste it into the TextArea, and see all the important features of your application.
  • An explanation of what questions your program answers and what challenges you overcame to implement it. If you use a very simple data structure, such as a linear array or a linked linear list, then you should provide some extra applet features such as performance measurement instruments or optimization methods so that you have an equal chance at a good grade as someone who works with a more complicated data structure.

    Any code written by others that you use in this program must be credited to its original author and its functionality carefully outlined. Any code of your own should be heavily commented with information about how each feature of the data structure and applet is being implemented.

    No oral presentation is required in Option 1.

    Option 2 (for groups).  Graph algorithm applet, performance analysis.

    This option is similar to Assignments 3 and 4; however, there is no requirement for online communication using INFACT-FORUM. The topics available for this option include the following. However, no more than one group should do any particular topic.
  • Critical Path Method (PERT = Project Evaluation and Review Technique).
  • Image segmentation into regions of similar color using the UNION-FIND techniques.
  • Subgraph isomorphism with vertex-labeled graphs. Assume the graphs are directed and that each vertex has a 1-character label on it. Demonstrate the search for an instance of G2 as a subgraph of G1.
  • Finding a maximum-cardinality matching in a bipartite graph.
  • Finding the strongly-connected components of a directed graph.
  • Finding a k-coloring of the vertices of an undirected graph, where the integer k is one of the inputs to the algorithm. If two vertices are connected by an edge, then they may not be assigned the same color. At most k distinct colors are permitted in a k-coloring. Every vertex must be assigned one of the colors.
  • Generating the Hamiltonian cycles of an undirected graph.
  • Finding the biconnected components and articulation vertices of an undirected graph.
  • Maximizing the flow through a directed network with capacity constraints, sources and sinks. (Construct a maximum flow using the augmenting path technique.)

    The group will also put documentation on the web (on the page with the applet) explaining (a) the technique and the details of how it works, and (b) the special behavior studied.

    Groups doing this option will give an 8-minute oral presentation.

    Option 3 (for groups).  Study of a data structure or algorithm, either by itself or as part of an application.

    The group will have maximum flexibility to propose a topic using this option. The topic must relate to the course in terms of data structures or algorithms. The topic must be suitable in terms of work and fairness in comparison with others. There must be an applet and presentation along the lines of those we have done in Assignments 3 and 4. Propose your topic by the topic deadline and get feedback before committing to this topic.

    Groups doing this option will give an 8-minute oral presentation.

    Timing

     Wednesday, February 21: Assignment is posted
  Consider the possible options.
  Discuss with your group whether to continue to work as a group 
or to split up.
  Make suggestions to each other for possible topics.

 Friday, February 23.
  Come to a rough agreement with your group about your plans.
  Settle on three or four of the possible topics and one or two options.

 Tuesday, February 27 at 6:00 PM:
  Deadline for submitting topic proposals/choices.

 Monday, March 5:
  Deadline for web pages describing your application or technique.
This page should cover the basic idea and each of the operations you are
handling.  Explain the division of labor on this page if you are doing
a group project.

 Monday, March 5 in class.
  Presentations for those doing Option 2 or Option 3.

 Wednesday, March 7 in class.
  Remainder of presentations for those doing Option 2 or Option 3.

 Thursday, March 8 at 6:00 PM:
  Deadline for turning in your or
your group's applet(s) and other files 

    Presentation Guidelines:

    (1) prepare a web page with your applet, plus about one page of bullet points to guide your presentation; (2) tell what technique(s) you are using; (3) tell us about the test data you are using to investigate the performance of your technique,  (4) demonstrate your applet but watch the time; (5) explain your findings so far regarding the performance of your technique on your test data and any insights you have gained about your technique.