The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I
Project #5

Due Date: beginning of class, Tuesday, December 11, 2001
THIS IS A FINAL DEADLINE; NO LATE SUBMISSIONS CAN BE ACCEPTED.

The new material in this project comes from Chapter 11 of the CSci 131 book.

This project gives you an opportunity to work further with linked lists, binary search trees, and generic packages. In this project you will develop part of a course-registration system.

From your work in Projects 3 and 4, you should have a working generic package to handle linked lists. If you completed Project 4, you will be able to use your list package without a single change.Chapter 11 introduces the concept of Binary Search Trees (BSTs), and shows several application examples, including a cross-reference generator.

Figure 11.23 shows a cross-reference tree. The registration data will look similar--each student is a node in the tree; that student's courses are contained in a singly-linked list. The student node's data field will be a record with the following fields:

  • student ID (positive, range 1111..9999) -- the student key
  • student name (10-character fixed-length string, e.g., "Mary Smith")
  • header block for a linked list that will store the courses for which this student has registered
The linked list node's data field will contain a course reference number (CRN - positive, range 11..99) -- the course key. Each student will register for a maximum of 3 courses.

The set of valid courses will, in this simple example, be stored in a "hard-wired" 100-element array of 11-character course title strings. For example, if course 77 is CSci 131-10, then array element 77 will be "CSci 131-10". Not all CRNs will be valid; each invalid one will be indicated by the string "invalid CRN" in the corresponding array element. The valid courses are:

11 Engl 10-43
20 CSci 51-10
24 CSci 123-11
34 Math 21-10
39 Phil 45-12
42 Mus 8-10
50 BiSc 11-11
77 CSci 131-10

The application program will read an external file of transactions, and process each transaction before reading the next transaction. An appropriate feedback message will be written to the console each time a transaction is processed. Each transaction will be a 2-character transaction code, followed by the data for that transaction. Here are the transactions:

  • AS ID Name -- add new student to the tree; error if student is already in the tree
  • DS ID -- student withdraws from the university; error if student is not in the tree
  • AC ID CRN -- student adds a course to his/her registration; error if
    • course is invalid
    • student is not in tree
    • student is already registered for course
    • student is already registered for 3 courses
  • DC ID CRN -- student drops course; error if course invalid or student not registered for it
  • SS ID -- show this student's current registration status - show ID, name, CRNs, and course titles, in CRN order
  • SA -- show all - display the whole structure, one student per line, in ID sequence
We will provide a file of test data and some sample output.

What to submit: You figure it out. You must persuade the reader that your project meets its specs; submit whatever you think is necessary. Grading will be 60% program correctness, 20% external documentation, 20% code style and layout. This is not all-or-nothing; partial credit is possible.