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: 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:


5. Question 3

Write the following procedure:
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)
{ ... }