Department of Mathematics and Computer Science

Machine Problem 4 and 5

Math 61 D. C. Smolarski, S.J. Winter 2000

Data Structure Concepts: MANAGING DATA BASES

PRELIMINARY VERSION (MP 4) = 30 points
FINAL VERSION (MP 5) = 30 points
DUE: (MP 4) Noon, Thursday, February 10, 2000
and (MP 5) Noon, Thursday, February 17, 2000

Santa Clara University now uses a computer-based "T-reg" program to register students for classes. As you probably realize, any such system is far from perfect. This assignment is for you to design a running data base management system modeling a university registrar's office course registration system. My hope is that you will come to understand and appreciate the difficulties inherent in such a system, so that when you don't get the classes you want when you register, you will understand why.

The input file consists of two major sections: (1) the course control section, and (2) the student request section.

The first section of the input file begins with a single integer number on the first line, indicating the number of sections that follow. Following this number, each line contains two integer numbers, the course section number followed by the capacity number.

Your program should read in this first section and initialize an appropriate data-base structure for each section number, with the appropriate capacity limit.

In the student request section, each line can have a maximum of three fields: (1) column 1 gives a code letter indicating the type of line it is; (2) columns 3-17 give a student's name; and (3) columns 18-22 give the section number.

The code letters in column 1 are to be interpreted as follows:

• The letter r indicates that the student wishes to REGISTER for the section noted. If the section is at capacity, the student should be put on a waiting list for that section. (The waiting list feature does not have to be implemented until MP 6.)

• The letter d indicates that the student wishes to DROP the section noted. If no section is noted, the student should be dropped from all courses in which he/she has been registered.

• The letter i indicates that the student wishes to INQUIRE as to which courses he/she has been registered.

• The letter c indicates that a CLASSLIST is being requested for the section indicated (no student name will appear). This listing should produce a list of all students registered for the section, as well as any students on the waiting list.

(The key letters in the input file can be either small letters or capital letters. Your program should adapt to this.)

My suggestions:

1. Code a separate function for each major function, i.e., a REGISTER function to register a student, a DROP function to drop a student, a CLASSLIST function to produce the classlists, an INQUIRE function to determine which sections the students has been registered in, and other functions as needed.
2. I suggest you create a small array (perhaps of size 10) of class SECTIONTYPE in which each element is a structure (class) variable that stores several pieces of information: (a) the section number, (b) the section capacity, (c) the number of students already registered, (d) a pointer to the list of registered students, and (e) a pointer to the waiting list of students.
3. When each student request line is read, the first character is checked to determine which function is called. Each function makes use of the same array, searching the appropriate field in each element to determine the correct section number and processing the information as needed.
4. As was hinted above, I suggest that the list of registered students and the list of wait-listed students be implemented as linked lists.
5. Using header nodes for each class list and each waiting list may simplify certain routines!

Note the following:

1. Procedure DROP may also be invoked with a blank argument. In that case, remove a student from all courses in which he/she has been registered.
2. Do NOT allow the same student to be registered twice for the same course!
3. In the CLASSLIST routine, do NOT worry about alphabetical order. The names are not in an appropriate form to alphabetize them. It is up to you to decide whether you want to insert a new student at the beginning or end of the class list.
4. The REGISTER routine should determine that a valid section number has been requested or output an appropriate error message.
5. The waiting list for each section must be a queue. Each time someone drops from a closed section (i.e., one at full capacity), the waiting list should be checked and someone moved from the waiting list to the class list. However, the queue should be such that the program can scan the queue and delete someone in the middle of the queue who decides to drop that course.
6. You will have to write (or copy from some book) appropriate code to use for several routines, among which are: inserting a new element in a linked list, deleting an element from a linked list, finding an element in a linked list, enqueuing and dequeing elements in/from a queue, removing an element from the middle of a queue, finding the desired section among all legitimate section numbers (by scanning the array elements and then returning the proper subscript number).

***** SPECIAL NOTE: YOU MAY WORK IN TEAMS ON THIS PROJECT.*****

The "teams" should consist of no more than 3 students. If you plan to work in teams, submit your names to me ON A PIECE OF PAPER SIGNED BY ALL THREE MEMBERS OF THE TEAM by 5pm Monday, February 7. [Any student if free to work alone on these programs, if you wish.]

You have nearly two weeks to complete this joint project--start early, since NO EXTENSIONS WILL BE GIVEN.

Do NOT exchange passwords. Instead, if individuals write separate functions of the total program, email your programs to each other, and turn in ONE copy of the cade with ALL NAMES on it.

(To send file on "math" [e.g., mp4.cxx] to another person on "math" whose username is "jdoe", type

         math 21:mailx jdoe < mp4.cxx

NOTE: You are to turn in a RUNNING preliminary version of the program as MP 4 on Thursday, February 10, 2000. This first version should implement REGISTER, INQUIRE, and CLASSLIST. The class capacities will be large enough so that waiting lists will not be necessary.

The final version should also implement DROP and the waiting lists and should be turned in as MP 5 on Thursday, February 17, 2000.

In both cases, one output per "team" shoud be submitted, indicating (in the comments) all the "team" members.

You can run the preliminary version (MP 4) using the input file: mp4pre.inp.

The final version (MP 5) should be run using input file: mp4in.inp.

Both input files can also be copied from my ma61 subdirectory on the HP Unix server as with previous files (cf. MP 2).