CS230 Data Structures, Wellesley College, Fall 2008

Assignment 4

Due Thursday, October 16, in class

CS230 Home Page | Syllabus | Assignments | Documentation | CS Dept

Problem 1: How Theseus found the Minotaur [55 points]

In class, we talked about how the Stack data type can be used to help an airline agent search and find whether there are flights connecting two cities on the map. This is just one among a class of problems in which there is an initial state, a goal to be reached, and a set of possible actions that can be performed at each point in the problem solution. The aim is to find a sequence of actions that successfully reaches the goal from the initial state. The Stack data type provides a natural means for implementing the strategy of depth-first search for finding a solution.

Believe it or not, this is not a new idea. In the myth of the Labyrinth, a group of young Athenians were sent to be consummed by a monster, the Minotaur, residing in a maze-like structure, the Labyrinth. A smart Athenian, Theseus, outsmarted the monster by finding him first and killing him. In his effort, he had the advice of Ariadne, the beautiful daughter of King Minos. She gave him a string that he used, like a stack, for the purpose of keeping track of where he had been. She also told him to keep his left hand on the wall so that he could search the Labyrinth exhaustively. That's what Computer Scientists call depth-first-search.

In this problem, you will implement Theseus' search. You will complete a program to search a two-dimensional maze, and you will use a Stack to store information about the path that is followed during the search. You will implement the depth-first-search strategy to find a successful path between start and goal locations in the maze.

The maze pattern will be stored in a two-dimensional (2D) array. Before you begin programming, you should familiarize yourself with how to create, initialize and access the contents of a 2D array. For simplicity, the maze will be stored in a 2D array of int values. Different integers can be used to represent free space and walls in the maze. In the sample maze below, 0 represents a free space and 1 represents a wall:

0 1 1 0 0 1
0 0 0 0 1 1
0 1 1 0 0 1
1 0 0 0 0 1
0 0 1 1 0 0
1 0 0 0 0 0

Assume that during the search for a path through the maze, it is only possible to move in the horizontal or vertical direction (not diagonal). Given a starting location at the upper left corner of the maze, and a goal location in the lower right corner, the following picture shows a successful path through the maze, using the integer 8 to label the positions along the path:

8 1 1 0 0 1
8 8 8 8 1 1
0 1 1 8 0 1
1 8 8 8 0 1
0 8 1 1 0 0
1 8 8 8 8 8

In general, a different path could be found, depending on the details of how the search process is implemented.

One of the first steps in the design of an object-oriented program is to consider what information needs to be represented in the problem solution. For the maze search problem, this information includes the maze itself, locations in the maze, and the path through the maze. If you hand simulate the search process, you will soon discover that it also helps to keep track of locations that you have already explored, to avoid running around in circles. Some of the information to be represented in a problem solution may be grouped within separate classes of objects that have instance variables to store the information.

Partial code for this problem can be found in the directory /home/cs230/download/Maze, which you should copy into your own directory. Study the existing code before starting your programming. This directory contains three code files:

MazeTest.java

This file contains a main() method with code to test your program. As you develop your program, you can comment out some of this testing code, or add further examples.

Place.java

The Place class can be used to represent an individual location in the 2D maze, using the row and column for this location. During the search process, Place objects corresponding to locations along the search path can be stored on a Stack. This code file is already complete.

Maze.java

When completed, the Maze class will include code to store a 2D maze and to search the maze for a path from a starting location to a goal location. This class contains two instance variables that are each a 2D array. The variable mazeArr should be used to store the maze pattern, and the variable visitArr should be used to keep track of locations in the maze that have been visited during the search process. You can assume that these arrays are square and of the same size. This code file also contains a method printArray() that prints the contents of an input 2D array, and a method showPath() that prints the locations along the path stored on an input Stack, and also displays the path superimposed on the maze stored in mazeArr, as shown above.

Your task is to complete the definition of the Maze class. First, write a constructor method that has a single input that is a 2D array that contains a sample maze. The MazeTest.java file contains code that illustrates how this constructor method can be invoked. Second, write a method named searchMaze() that searches for a path through the maze stored in mazeArr. This method should have four inputs that specify the row and column of the starting location for the search, and the row and column for the goal location. The MazeTest.java file also contains code to illustrate how this method can be invoked. The searchMaze() method should use a Stack to represent the current partial path through the maze during the search process. The items placed on the Stack should be single Place objects. The following English description embodies the basic search strategy. The overall strategy is similar to the graph search algorithm that we discussed in class. The expression "current Place" is used to refer to the location of the maze that is currently occupied during the search.

Push the starting Place onto the Stack, mark this location as visited, and set the current
Place to the starting Place

Repeat the following actions until the goal Place is reached:

Search for a new Place that is adjacent to the current Place, and is an
open space in the maze that has not yet been visited

If such a new Place is found, push it onto the Stack, mark this new location
as visited, and set the current Place to this new location

      If no such Place is found, the search process has reached a dead end and needs
      to back up. In this case, pop the Place that is on top of the Stack, and set
      the current Place to the new Place that is now on top of the Stack

When the loop is done, print the successful path that is stored on the Stack

You should consider the possibility that the maze cannot be solved, given the pattern of walls (i.e. there does not exist a valid path from the start to the goal position). How can you modify the above English description to detect this situation? The searchMaze() method should print a message in this case, indicating that the maze cannot be solved. Also keep in mind that when searching for a new Place that is an open space in the maze that has not yet been visited, you should only consider the four neighboring locations to the left, right, above and below the current location. It does not matter what order you consider these four locations. It is ok to define one or more helper methods, in addition to the searchMaze() method.

Submission details: First, make sure that you have included enough testing code in your program to show us that you have done a reasonable job in testing it. (You need to figure out what is "enough"). Hand in a hardcopy of your final Maze.java code file, and drop off an electronic copy of your program by connecting to your Maze directory and executing the command:

submit cs230 Maze *.*

Problem 2: Implementing Your Own Stack Class [35 points]

Suppose that Java did not provide a built-in Stack class. Fortunately, we can create our own Stack class using any of a variety of data structures to store the contents of the stack. In lecture, we created a stack interface, StackInterface, and implemented the interface with a class called StackLinkedListBased, which used a LinkedList to store the contents of the stack. In this problem, you will define a new class that implements StackInterface using a Vector to store the contents of the stack.

Early in the semester, we emphasized the importance of separating the formal specification of an abstract data type from its implementation details. One advantage of doing this is that the implementation can be changed, perhaps to be more efficient, without affecting the correctness of application code that uses this data type. Since your new class, StackVectorBased will implement StackInterface, any code that uses an implementation of StackInterface will run correctly if it utilizes your new class.

To begin your implementation, download the directory /home/cs230/download/StackVectorBased into your own directory. This directory contains the file StackInterface.java that you must implement, the file StackLinkedListBased.java that was developed in class and implements the StackInterface, the file StackException.java specifying how stack exceptions are handled, and the file StackVectorBasedTest.java that you can use to test your implementation. Here is what you need to do:

Remind yourself of how Vectors may be used by consulting the Java API for the Vector class.
In a new file StackVectorBased.java, create a new class, StackVectorBased, that implements StackInterface. Instances of the StackVectorBased class must use a Vector to store the contents of the stack.
Test your class by executing the StackVectorBasedTest application.
You must include comments at the top of your program and before each method so that your StackVectorBased.java file is Javadoc compliant. Javadoc is a style of commenting that allows generation of HTML documents. As an example, the CS230Date.java file from Assignment 3 is Javadoc compliant (note the comments at the top of the file and before each method) and enables generation of online documentation for the CS230Date class. First, you should comment your StackVectorBased.java file in the javadoc style, then you should generate the online documentation using the javadoc command, and finally you should check to ensure that your documentation is similar to our documentation for the StackVectorBased class.

Submission details: Hand in a hardcopy of your StackVectorBased.java code file, and drop off an electronic copy of your program by connecting to your StackVectorBased directory and executing the command:

submit cs230 StackVectorBased *.*

Problem 3: Comparing Algorithm Efficiency [10 points]

In class, we discussed the issue of algorithm efficiency and the important question, "As the size of the problem grows, how does the amount of computation grow?" In this problem, you will compare two strategies for performing the same task, with this question in mind. Here is a code file named Algorithms.java that contains two methods that each determine whether an input array contains integers that are sorted in increasing order. First examine the two methods carefully and summarize each implementation strategy in words. Let the size of the problem be defined as the size of the input array, and denote this size by n. For each method, what situation represents the "best case" for the algorithm, requiring the least number of array references to determine the value to be returned? What situation represents the "worst case", requiring the most array references? For the worst case, determine the total number of distinct array references performed by each implementation, as a function of n. Which strategy is most efficient, and why?

Submission details: Hand in a typed (not handwritten) hardcopy of your work. You can draw by hand any graphs that might help us understand your work.