Introduction to Computer Science I by James Tam Return to the course web page

CPSC 231: Assignment 9 (Worth 8%)

Grading Scales

Grade out of 24 Letter
55 - 56 A++
53 - 54 A+
51 - 52 A
48 - 50 A-
44 - 47 B+
40 - 43 B
36 - 39 B-
32 - 35 C+
28 - 31 C
24 - 27 C-
18 - 23 D+
12 - 17 D
6 - 11 D-
0 - 5 F

 

New concepts to be applied for the assignment

  1. Dynamic (singly linked) lists

 

Writing a list management program:

Unless otherwise indicated the features for this assignment are the same as with the previous assignment. The main difference is that rather than storing the information in an array of records that is of some arbitrary size, this version of the program stores the list information in a linked list. The size of the list should not be capped at some fixed size but instead it should grow and shrink as necessary.

Features to be implemented
 
  1. Declare a new type 'RoomPointer' that is a pointer to a RoomNode (analogous to 'NodePointer' from my notes on linked lists): 1 mark
 
  1. Declare a new type 'RoomNode' (analogous to 'Node' from my notes on linked lists) which is a record with two fields: a) 'Data' which is of type 'Room' as declared in the previous assignment b) 'Next' which is a RoomPointer: 1 mark
 
  1. Declares a head pointer of type 'RoomPointer': 1 mark
 
  1. Displays instructions on how to use the program each time that it is run: 1 mark
 
  1. Display a signoff message to indicate to the user that he or she has quit the program: 1 mark
 
  1. Some form of debug mode has been implemented: 1 mark
 
  1. Displays a menu showing the list management functions: 1 mark
 
  1. (Q)uit: The user can quit the program: 1 mark
 
  1. (D)isplay: The program display the list in a fashion that is similar to the previous assignment: 2 marks
 
  1. (L)oad: This feature can be implemented in one of the two ways that was described in the previous assignment: 4 marks maximum for this feature
   
  1. As the information for each room is read in from file it's added to the end of the list: 2 marks
   
  1. As the information for each room is read in from file it's inserted in correct alphabetical order according to the room code (no shifting of elements should be necessary): 4 marks
 
  1. Correctly handle the case of an empty input file. This feature is identical to the previous assignment: 1 mark
 
  1. (S)ave: This feature is identical to the previous assignment : 3 marks
 
  1. (F)ind: This feature is identical to the previous assignment: 3 marks
 
  1. (P)resent: This feature is identical to the previous assignment: 3 marks
 
  1. (A)dd: This feature is identical to the previous assignment except that there should no longer be any need to shift elements. You can implement this feature in one of two possible ways: 4 marks maximum for this feature
   
  1. New rooms will be added to the end of the list: 2 marks
   
  1. New rooms will be inserted in it's correct alphabetical order according to the room code (no shifting of elements should be necessary): 4 marks
 
  1. (R)emove: This feature is identical to the previous assignment except there should be no need to shift list elements : 4 marks
 
  1. (O)rder reverse display: In order to receive credit for this feature you cannot use doubly linked lists (which has pointers to the previous and successor nodes - don't worry if you don't know what I am referring to because this topic will covered in a later course: CPSC 331).  Instead you must use a recursive function or procedure call to display the list in reverse order.  That is, the last element is displayed first, the second last element is displayed second until the first element is reached and it is displayed last.  Note: The list should only be displayed in reverse order, the list should not actually be resorted into reverse order by invoking this feature.  Because this features is a 'bonus' (actually a bonus on top of a bonus) you may have to do some extra reading to in order to sufficiently understand recursion to implement it for this assignment.  Consequently I recommend that you work on this feature last, after you've gotten all the other features working because it will likely take up substantially more time than everything else.   (JT:  Hint  completing this feature depends upon your ability think and trace code in a backwards fashion).

 

Submission requirements

In addition to having fulfill the generic assignment requirements, the requirements specific to this assignment include:

  1. Include a README file in your submission:  For this assignment your README file must include your contact information: your name, university identification number and UNIX login name so that your marker knows whose assignment that he or she is marking.   For this assignment you should also list the features of the game that you actually implemented.

  2. Assignments (source code/'dot-p' file and the README file) must be electronically submitted.  In addition a paper print out of the source code and README must be handed into the assignment drop box (located on the second floor of the Math Sciences building) for the tutorial that you are registered in.  Electronically submitting the assignment allows your marker to run the code in order to quickly determine what features were implemented.  Providing a paper printout makes it easier for your marker to read and flip through your source code.  Unless you are told otherwise you are to email your source code and readme file to your TA and to me.  Make sure that include the following information in the subject line: "CPSC 231 Assignment X" where 'X' stands for the assignment number that you are submitting e.g., "CPSC 231 Assignment 3".

  3. As a reminder, you are not allowed to work in groups for this class.   Copying the work of another student will be regarded as academic misconduct (cheating).  For additional details about what is and is not okay for this class please refer to the following link.

To help make sure that you haven't missed anything here is a checklist of items to be used in marking.  A sample executable 'rooms' can be found in UNIX under the directory: /home/231/assignments/assignment9. Sample input files that you can use include 'empty.txt', 'mini.txt' and 'rooms.txt'.