The George Washington University
School of Engineering and Applied Science
Department of Computer Science

CSci 131 -- Algorithms and Data Structures I
Project #4

Due Date: April 17, 2000

The purpose of this project  is to give you more practice in dealing with generic packages, and illustrate the advantages of a clearly-specified generic interface in supporting multiple implementations and multiple clients. This project uses material from Chaps. 2, 3, 4, 5, and 8. Project 5 will build on this project to develop a concurrent simulation.

In Project 3 you developed a generic table handler package that uses ordered arrays for the tables. In this project you have two main subtasks: develop a new client for the package, and then modify the package to support a different implementation of the tables.

You have three weeks for this project. You cannot hopeto have the full project completed in time unless you complete Part I by the end of the first week!

Part I:

A. Develop a package Accounts, analogous to Students, to handle a very simple bank account record, Account, with 3 fields:
  • Branch (the bank branch -- office -- where the account was opened, 1..100)
  • ID (like the student ID)
  • Balance (a currency quantity).
Then modify a copy of Students.IO to produce an IO child package Accounts.IO. Test this with a test program. This project will NOT use the interactive interface, so don't bother to change it.

B. Now develop a package BankDatabase, that will use an instantiation of Tables_Generic to store account records. Instead of creating a single table for all records, use an array of 100 tables, one table for each branch. The database will maintain the array of tables, and also keep track of the latest account number that was assigned. Operations on this database will be

  • Create a new account at a given bank branch. This operation will assign an account number and return it to the caller.
  • Close an existing account. Don't reuse the account number.
  • Deposit a given amount of money into a given account.
  • Withdraw a given amount of money from a given account.
  • Query the current balance in a given account.
  • SaveDatabase
  • RestoreDatabase
Each operation should return a completion code taken from the set OK, InvalidID, and InsufficientFunds, and should have a set of parameters that makes sense for that operation. It is up to you to design the details of the operations and their pre- and postconditions.

This is NOT an interactive program, just a package! Test it with a test program.

Part II:

A. Copy the generic table handler and backup/restore packages into a new set of files, then modify the private section, and bodies, of the original files so that each table is implemented as an ordered singly linked list with head and tail pointers. The idea is not to throw away the array version, and also not to change the public part of the specs at all!

Students in a course like this need to get an oppportunity to write their own linked-list operations. Therefore, you are not permitted to use the generic list package from Chapter 9. Use dynamic allocation and access types directly in implementing the table operations; use the various procedures from Chapter 8 as your starting point.

You should develop this package as you did the original array version: one or two procedures at a time, testing as you go. You will be overwhelmed if you try to do it all at once. You should be able to reuse your Project 3 test programs here; just recompile using WITHs of the new packages instead of the old ones.

B. Now recompile the programs from Part I to use the new version of the table package instead of the old one.

Regarding test plans and user guides: write test plans for everything you change; write user guides for any package(s) that don't have them yet.