Assignment 5

Due date:

Late assignments will be penalized 10% per day, and will not be accepted after .

1. Hand In

Each student is required to do this assignment individually and to hand in the following:

A disk containing only two files: the source listing and executable for the program in the assignment.
Printouts of the program and the output it produces in test data of your own choice.

Place these items in a 9"x11" envelope, with the following information clearly marked on the outside of the envelope:

Name, Student Number, Assignment Number, Course Number (T26)

Assignments which are not in an envelope will not be marked

Deposit your envelope in .

Marking Scheme

Programming standards: 10pt, Each question: 20pt, Total: 70pt.

Your program must conform to the programming standards. These are described in a separate sheet.

2. Program Handout

In this assignment, you are given a partial implementation of the abstract type `list'. This is actually the original (complete) implementation of `collection' (renamed) plus all but one of the `window' functions.

Note that the main program writes out information about how much memory has been allocated by your procedures but not returned to the global pool. These numbers should always be 0: if they are not, you have bugs to fix.

The program handout consists of 4 files: Partial5.c, Partial5a.h, Partial5b.h, and Partial5c.h. The only file you should modify is Partial5.c. The '.h' files each provide a testing procedure for each of the questions. You must remember to properly define the macro QUESTION at the top of Partial5.c to be the appropriate question number. For example:

        #define QUESTION 2

is the correct definition for answering question 2, and it causes file Partial5b.h to be automatically included, thus providing your program with the appropriate testing function.

3. Question 1

The split operation cannot always update the size information in a list header in constant time. In class we discussed a ``lazy evaluation'' approach to updating this information. Implement that strategy.

4. Question 2

The given implementation is ``singly-linked''. Change it to be doubly-linked (i.e. add back pointers). Also, Add two operations on windows:

move_backward

Input: W (a window)
Output: W'
Preconditions: W is not on the first element of a list
Postconditions: W' is on the element that precedes the element W was on.

is_first

Input: W (a window)
Output: boolean
Preconditions: W is defined
Postconditions: true if W is on the first element in a list, false otherwise

5. Question 3

Write the following procedure:

sorted_insert

Inputs: L (a list), V (a value)
Output: L'
Preconditions: L is sorted in ascending order.
This is a good example of a precondition that normally is too time-consuming for a procedure to test every time it is called. Your implementation should not test this precondition, but should document it.
Postconditions: L' = L with value V added. Storage is allocated as needed. L' is sorted in ascending order (this requirement determines the exact position at which to insert V).

Your sorted_insert procedure must be implementation-independent - it must do all its list manipulations using the operations defined in the specification (including the new ones in question 2); it must not rely on the details of how lists are implemented.

void sorted_insert (list l, element e)
{ ... }