School of Engineering and Applied Science
Department of Computer Science
CSci 133 -- Algorithms and Data Structures I
http://www.seas.gwu.edu/~csci133/spring03
Prof. Michael B. Feldman
mfeldman@gwu.edu

Project #2

Due Date: beginning of class, Monday, Feb. 10, 2003

This project extends Project 1. It depends on the readings so far, and also on the handouts Incremental ADT Development with Stubs and Passive and Active Iteration in Collection Classes, which is online and linked from the course page.

In Project 1, a Knight's Tour is played with data received interactively from a human user.

In this project, you will extend Project 1 so that once a game begins, the program will "remember" all valid moves in the
game, and, once the game ends, allow the user to select a "replay" option that will re-run the latest game. Each actual
move will be displayed in sequence on the board; after each move the program will wait for the user to press RETURN
before continuing.

Before you start, copy your Project 1 file from your csci53 directory to your csci133 directory, so you can now keep the two courses separated. After you've copied the files, delete the files from csci53 -- especially the .class file, so as not to confuse the compiler or the Java virtual machine!

Part 1:

Copy programs133/ChessPosition.java into your csci133 directory. This file is a skeleton for an ADT class each of whose objects is a position, that is, a pair consisting of a file and a rank. The class provides four methods: a constructor, two accessors or "getters" that return the rank and file, and a toString method that returns the position as you might type it in: a3, for example. The bodies of the four methods are stubbed out; they are very simple and you will complete them. You should develop a small test program to test them.

Part 2:

Copy programs133/KnightSequence.java into your csci133 directory. This file is a skeleton for an ADT class each of whose objects is a sequence of chess positions.

The move sequence is "remembered" in a collection called a sequence; each new move will be added to the end of the sequence, and the replay will be done by means of an active traversal of the sequence. A few of the methods are coded for you; the rest are stubbed out. Again, you will complete the class and test it with a test program.

Part 3:

Finally, you are ready to integrate everything. Modify your knight's tour program to have the following characteristics:
  • detect the move q0 as a "quit" sentinel to end the current game;
  • when the game ends, ask the user whether (s)he wants to
  • replay the current game
  • play a whole new game, or
  • terminate the program.

    • What to submit:

    With this project, the deliverables change from the CSci 53 style, because you are developing two classes and an aplication, instead of just an application as in Project 1. You'll need to submit:
    • For each of the two classes, a test plan, test run(s), test program listing, and class source listing;
    • For the application, an algorithm, test plan, test run, and source listing.
    Grading:

    Grading for the overall project will be the sum of the grades for the three parts.