December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 1 (Compulsory)

Total Marks: 30 Marks

• Question 2
• Question 3
• Question 4
• Question 5
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 1

Briefly explain the main characteristics of the following terms:

(i)Binary trees [1 mark ]

A binary tree is a data structure which consists of nodes which can have up to 2 child nodes.

(ii)N-ary trees [1 mark ]

An N-ary tree is a data structure which consists of nodes which can have up to N child nodes.

(iii)FIFO queue [1 mark ]

In a FIFO queue the oldest items are the ones to be removed first.

(iv)LIFO queues [1 mark ]

In a LIFO queue the newest items are the ones to be removed first.

[4]

In terms of lookup and update times, briefly identify the differences between arrays and dynamic linked lists .

•An array is a fixed size data structure with a constant lookup and update time. (1 mark)

•A dynamic linked list is a variable size data structure where lookup and update times are proportional to the length of the list.
(1 mark)

[2]

(i)Explain, informally, how a bubble sort works.[3 marks ]

A bubble sort

•Compares an element with its adjacent element,along the length of the list to be sorted;(1 mark)

•Swapping the two if the order requires it;(1 mark)

•Continually iterating over the list until it is sorted.(1 mark)

(ii)Explain, informally, how hashing works.[3 marks ]

In Hashing

•Every data item has an associated key value;(1 mark)

•Which is calculated using a specific hash function;(1 mark)

•Where the key value directly relates to the items storage location.(1 mark)

(iii)Briefly identify the most common problem with hashing.[1 mark ]

The most common problem with Hashing is collisions,where addresses may not be unique.

[7]

(i)Write an iterative function, called Remainder , the signature of which is given below, which takes in two integer parameters by value and returns the remainder of x /y .You may not use any library functions.[3 marks ]

FUNCTION Remainder(x: INTEGER, y: INTEGER): INTEGER;

A sample definition of Remainder follows:

FUNCTION Remainder(x: INTEGER, y: INTEGER):INTEGER;
BEGIN
       WHILE(x >= y) DO
             x:= x-y;
        Remainder:= x;
END; {Remainder }

The following marking scheme should be used:

•Defining a suitable iteration structure with an appropriate continuing (or terminating)condition (1 mark)

•On each iteration,ensuring that the value which is being tested is suitably updated (probably by reducing x by y );(1 mark)

•Correctly returning the value when the condition is reached.
(1 mark)

(ii)Write an iterative function, called IsPrime , the signature of which is given below, which takes an integer parameter by value and returns TRUE if the parameter is prime and FALSE otherwise. Note that an integer N (for N2)is prime if the result of dividing it by each of 2 through to (N/2)-1 produces a non zero remainder. [4 marks ]

FUNCTION IsPrime(x: INTEGER): BOOLEAN;

A sample definition of IsPrime follows:

FUNCTION IsPrime(x:INTEGER):BOOLEAN;
BEGIN
     FOR i: =2 TO ((x/2)-1) DO
             IF Remainder(x, i)= 0 THEN
                IsPrime:= FALSE;

      IsPrime:= TRUE;
END; { IsPrime }

The following marking scheme should be used:

•Declaring a suitable iteration structure with an appropriate continuing (or terminating)condition;(1 mark)

•Checking that the number is still known to be prime on each iteration usingthe Remainder function;(1 mark)

•Returning as soon as it is known not to be prime;(1 mark)

•Correctly returning at exit if it is prime.(1 mark)

[7]

Assume the following definition of a double linked list,together with the signature of the procedure Remove ,which removes from the list x the item pointed to by y :

(i)Write a recursive function, called Search , the signature of which is given below. This function takes in two parameters by value, the first of which is a double linked list, and the second being an integer, and returns either a pointer to the first occurrence of the integer in the list or a NULL pointer if the integer is not in the list.[5 marks ]

FUNCTION Search(x: List,y: INTEGER) : NodePtr;

A sample definition of Search follows:

FUNCTION Search(x: List, y: INTEGER) : NodePtr;
BEGIN
       IF(x.Front ˆ.Datum= y)THEN
            Search:= x.Front
       ELSE
            IF(x.Front ˆ.Forward= NULL)THEN
                Search:= NULL
             ELSE
                Search:= Search(x.Front ˆ.Forward, y);
END;{ Search }

The following marking scheme should be used:

•Testing that the data item at the front of the list is equal to the one of interest;(1 mark)

•Returning a pointer to it if it is;(1 mark)

•Returning NULL if the end of the list has been reached without a match being found;(1 mark)

•Recursing with an incremented pointer if a match has not been found and there is still more list to traverse;(1 mark)

•Correctly using the return value of the recursive call to climb back up the recursion stack.(1 mark)

(ii)Write a recursive procedure, called SearchAndRemove , the signature of which is given below, which takes in a reference parameter which is a list, and a value parameter which is an integer. Upon termination of the procedure, the list should have all occurrences of the integer removed.You should assume the existence of the Search function defined above, as well as the procedure Remove , the signature of which is given above.
[5 marks ]

PROCEDURE SearchAndRemove(VAR x :LIST,y: INTEGER);

A sample definition of SearchAndRemove follows:

PROCEDURE SearchAndRemove(VAR x: LIST, y :INTEGER);
VAR Temp : NodePtr;
BEGIN
      Temp:= Search(x, y);
      IF(Temp<> NULL)
      BEGIN
            Remove(x, Temp);
            SearchAndRemove(x, y);
      END;
END;{ SearchAndRemove }

And the following marking scheme should be used:

•Creating a local temporary pointer;(1 mark)

•And assigning it to the first occurrence of y by calling Search ;
(1 mark)

•Terminating if the value of the pointer is NULL (implicitly, by continuing if it is non-null);(1 mark)

•Calling the Remove procedure, to remove the current item from the list. (1 mark)

•Recursing with the updated list to search for the next item in the list. (1 mark)

[10]