Assignment 4

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: 5pt, Question 2: 25pt, Question 3: 20pt, Question 4: 20pt.

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

2. Program Handout

In this assignment, you are given the main program, the memory management procedures, and a C definition of `collection' and related types, and implementations of most of the `collection' operations. These are available as a disk file that you can copy (so you do not have to type it in) - ask your teaching assistant where and how to obtain this.

You must use the given parts of the program without changing them. For example, all memory management must be done using the given procedures get...memory and return...memory - do not directly use C's built-in procedures malloc and free.

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.

3. Question 1

Write the procedure delete(collection c, collection_element e) so that it meets the specification given in class. The procedure must be linear time, i.e. its execution time should be proportional to the size of the collection c. This means you are permitted to loop through the elements of c one at a time.

This procedure is tricky enough that it needs to be carefully designed before you begin writing code. For example, when you delete a node, say N, it is necessary to update the next pointer of the node preceding N in the list. In order to do the update, you will need a pointer to that node: N itself does not contain a pointer to the node that precedes it, so your algorithm for deleting a node will include a method for getting a pointer to the node preceding the one to be deleted. Try to do this as efficiently as you can. As suggested in the lecture, node-and-arc diagrams will be very helpful for designing this procedure.

4. Question 2

Write a procedure called separate having four arguments:

Inputs: C, a collection, P, a function of one argument, a collection_element, that returns a boolean value.
Outputs: Ctrue, Cfalse, collections.
Preconditions: C is defined.
Postconditions: Ctrue contains a copy of every element, X, in C for which P(X) returns true. Cfalse contains a copy of every element, X, in C for which P(X) returns false. C is unchanged.

separate must use the map procedure, and it must not depend on the implementation details of `collections' - all its processing of collections must be done by using the operations in the specification of `collection'.

In the model solution, the implementation of separate is 4 lines of code excluding declarations, and uses an auxiliary function (1 line of code).

5. Type Definitions

These are the type definitions you are given:

        typedef int collection_element;

        typedef struct collection_node {
          collection_element value;
          struct collection_node * next;
        } collection_node;

        typedef struct {
          int size;
          collection_node *first,*last;
        } collection_header;

        typedef collection_header *collection;