CSE 373 -- Data Structures and Algorithms

Winter 2002

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 3

Version 1.0

Visible Algorithms

Due date and time: Friday, February 1, 2002, at 5:00 PM)

Turn in this assignment by filling in the A3 online submission form.

Title: Visible Algorithms .

Purposes: Gain experience implementing simple algorithms in Java and rendering their behavior graphically on the screen. Further practice and demonstrate your ability to create Java applets. .

Instructions: Be sure you have read Chapter 2 of Sahni. Choose one of the following algorithms from that chapter: Horner's rule; Computing ranks; Rank sort; Selection sort; Bubble sort;

Create a Java applet that contains a text area for entering data and commands, a canvas (preferably an instance of a subclass of Canvas that you define) for displaying the data, and a "Process" button to tell the applet to perform the operations that have been typed in the text area. It should have a place to store a list of integers. (You may wish to use a Java Vector for this, or perhaps an array of int's.)

Implement the following operations:

CLEAR, which should empty out the list of values.

INSERT n, where n is an integer. Puts the new number at the end of the list.

one of the following, depending on the algorithm you have chosen: EVALUATE (for Horner's rule), RANKS (for Computing ranks), or SORT for any of the sorting methods.

After each operation, the current version of the data should be displayed on the canvas using a style something like that in Figures 2.3 and 2.4 in Sahni.

Optional enhancement 1: include two additional "operations", SLOW and FAST. After the SLOW command has been processed, the program should perform subsequent EVALUATE, RANKS, or SORT operations in "slow motion", updating the display after each change to the state of the data, and waiting a few milliseconds (say 500) using Java's sleep method in the Thread class. If the user inputs a FAST command, then the applet should go back into its regular mode of completing the EVALUATE, RANKS, or SORT operation before updating the display.

Optional enhancement 2: (This one is a little trickier to get working, but adds a lot to the interactivity of your applet.) add another button to your program with the label "Step", and add another operation called STEP. These should work as follows. If the user enters the STEP command, then during any subsequent EVALUATE, RANKS, or SORT operation, instead of processing it quickly or with timed delays, the operation will wait for the user to click on the Step button, and then it will perform one step of the algorithm and repaint the canvas to show the change. Then it will wait again, etc. Whenever it waits, it should display a message somewhere on the screen to indicate that it is waiting for the user to click the Step button. If the user gives the SLOW or FAST command, then the stepping mode is cancelled for subsequent operations.

Partnership Work: This assignment requires partnership work. Work in teams of 2.