Advanced Algorithms and Recursion: Computer Science 9618 (Cambridge International AS & A Level)

A programmer writes the following recursive function to add together the individual digits of a positive integer.

FUNCTION SumDigits(N : INTEGER) RETURNS INTEGER
    IF N < 10 THEN
        RETURN N
    ELSE
        RETURN (N MOD 10) + SumDigits(N DIV 10)
    ENDIF
ENDFUNCTION

The statement OUTPUT SumDigits(4831) is then executed.

(a) State the base case and the general (recursive) case of this function, and explain the purpose of each. [2]

(b) Complete a trace of the calls placed on the call stack, in the order they are called, when SumDigits(4831) is evaluated, and state the value returned by each call once the base case is reached. [4]

(c) State the value output by OUTPUT SumDigits(4831), and explain why expressing this algorithm recursively is appropriate for this problem. [2]

A software company implements two Abstract Data Types (ADTs) using arrays, each with pointer variables to keep track of the current position.

An undo stack for a text editor stores the names of formatting actions the user has applied, so that the most recently applied action can be undone first. It is implemented using this pseudocode:

DECLARE MaxSize : INTEGER
CONSTANT MaxSize ← 5
DECLARE ActionStack : ARRAY[1:MaxSize] OF STRING
DECLARE Top : INTEGER
Top ← 0

PROCEDURE Push(Item : STRING)
    IF Top = MaxSize THEN
        OUTPUT "Stack full"
    ELSE
        Top ← Top + 1
        ActionStack[Top] ← Item
    ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS STRING
    DECLARE Removed : STRING
    IF Top = 0 THEN
        OUTPUT "Stack empty"
    ELSE
        Removed ← ActionStack[Top]
        Top ← Top - 1
        RETURN Removed
    ENDIF
ENDFUNCTION

(a) Starting from an empty stack (Top = 0), these calls are made in order:

CALL Push("Bold")
CALL Push("Italic")
CALL Push("Underline")
LastAction ← Pop()
CALL Push("ResizeFont")
NextAction ← Pop()

Complete a trace showing the value of Top after each call, and state the final values of LastAction and NextAction. [4]

A print queue for a shared office printer stores the names of documents waiting to print, so that documents are printed in the order they were sent. It is implemented using this pseudocode:

DECLARE MaxSize : INTEGER
CONSTANT MaxSize ← 5
DECLARE PrintQueue : ARRAY[1:MaxSize] OF STRING
DECLARE Front, Rear : INTEGER
Front ← 0
Rear ← 0

PROCEDURE Enqueue(Item : STRING)
    IF Rear = MaxSize THEN
        OUTPUT "Queue full"
    ELSE
        Rear ← Rear + 1
        PrintQueue[Rear] ← Item
        IF Front = 0 THEN
            Front ← 1
        ENDIF
    ENDIF
ENDPROCEDURE

FUNCTION Dequeue() RETURNS STRING
    DECLARE Removed : STRING
    IF (Front = 0) OR (Front > Rear) THEN
        OUTPUT "Queue empty"
    ELSE
        Removed ← PrintQueue[Front]
        Front ← Front + 1
        RETURN Removed
    ENDIF
ENDFUNCTION

(b) Starting from an empty queue (Front = 0, Rear = 0), these calls are made in order:

CALL Enqueue("Report.docx")
CALL Enqueue("Invoice.pdf")
CALL Enqueue("Timetable.xlsx")
FirstPrinted ← Dequeue()
CALL Enqueue("Poster.png")
SecondPrinted ← Dequeue()

Complete a trace showing the values of Front and Rear after each call, and state the final values of FirstPrinted and SecondPrinted. [4]

A school stores a linked list of exam candidates' names, kept in alphabetical order, using two parallel arrays and a start pointer:

DECLARE CandidateName : ARRAY[1:5] OF STRING
DECLARE NextPointer : ARRAY[1:5] OF INTEGER
DECLARE StartPointer : INTEGER

NextPointer[i] holds the array index of the next node in the list, or -1 if there is no next node. Array positions not currently part of the list are unused. The list currently holds this data:

StartPointer = 3.

(a) State the sequence of names produced by traversing this list from StartPointer, following each NextPointer value in turn. [2]

(b) The name "Dinesh" is inserted into the list at the unused array position 2, so that the list remains in alphabetical order. State the new value of NextPointer[2] and the new value of NextPointer[3] after this insertion, explaining how each value is determined. [3]

(c) The node holding "Halima" (at index 1) is now deleted from the list. State which NextPointer value must change to remove "Halima" from the list, its new value, and state the resulting sequence of names produced when the list, as it now stands after both (b) and (c), is traversed from StartPointer. [3]

A binary search tree (BST) stores integer values so that, for every node, all values in its left subtree are smaller than the node's value and all values in its right subtree are larger. Nodes are implemented using pointers:

TYPE TreeNode
    DECLARE NodeValue : INTEGER
    DECLARE LeftPointer : INTEGER
    DECLARE RightPointer : INTEGER
ENDTYPE

DECLARE Tree : ARRAY[1:10] OF TreeNode
DECLARE RootPointer : INTEGER

LeftPointer and RightPointer hold the array index of a node's left/right child, or -1 if that child does not exist. To insert a new value, the tree is searched starting from RootPointer: at each node, if the new value is smaller than that node's value the search moves to LeftPointer; if larger, it moves to RightPointer; when a pointer of -1 is reached, a new node holding the value is created there.

The values 50, 25, 75, 10, 30, 60, 90 are inserted, in that order, into an initially empty tree.

This recursive procedure then performs an in-order traversal of the tree, starting with CALL InOrder(RootPointer):

PROCEDURE InOrder(P : INTEGER)
    IF P <> -1 THEN
        CALL InOrder(Tree[P].LeftPointer)
        OUTPUT Tree[P].NodeValue
        CALL InOrder(Tree[P].RightPointer)
    ENDIF
ENDPROCEDURE

(a) Describe the structure of the resulting tree after all seven values have been inserted, stating each node's parent, and whether it is a left or right child of that parent. [3]

(b) State the sequence of values output by CALL InOrder(RootPointer), and explain why an in-order traversal of a binary search tree always produces a sequence of this kind. [3]

(c) State the sequence of values that would be produced by a pre-order traversal, and by a post-order traversal, of the same tree. [2]

A program defines a class NotificationChannel, with two subclasses, EmailChannel and SMSChannel, that inherit from it. Each subclass provides its own version of a method called Send(). A procedure stores a list of NotificationChannel objects. Some are EmailChannel objects, some are SMSChannel objects, and calls Send() on each object in turn. Each object automatically executes its own subclass's version of the method, without the procedure needing to check which subclass any particular object belongs to.

Which object-oriented programming concept does this best illustrate?

A programmer writes the following function to search an array of student ID numbers using linear search.

FUNCTION LinearSearch(Arr : ARRAY[1:8] OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index : INTEGER
    FOR Index ← 1 TO 8
        IF Arr[Index] = Target THEN
            RETURN Index
        ENDIF
    NEXT Index
    RETURN -1
ENDFUNCTION

The array currently holds Arr = [23, 47, 12, 89, 56, 34, 78, 61] (index 1 to index 8).

(a) State the values of Index checked, the number of comparisons made, and the value returned, when LinearSearch(Arr, 56) is called. [3]

(b) State the number of comparisons made and the value returned when LinearSearch(Arr, 99) is called, explaining why every element of Arr must be checked in this case. [3]

(c) State one precondition that must be satisfied about the contents of an array before binary search could correctly be used to search it, and explain whether this precondition is currently satisfied for Arr. [2]

A sorted array stores n integer values, where n is large. Which statement correctly compares the worst-case time complexity of linear search and binary search on this array, using Big O notation, as n increases?

A programmer writes the following procedure to sort an array of six race times, in seconds, into ascending order using insertion sort.

PROCEDURE InsertionSort(Arr : ARRAY[1:6] OF INTEGER)
    DECLARE i, j, Key : INTEGER
    FOR i ← 2 TO 6
        Key ← Arr[i]
        j ← i - 1
        WHILE (j >= 1) AND (Arr[j] > Key) DO
            Arr[j + 1] ← Arr[j]
            j ← j - 1
        ENDWHILE
        Arr[j + 1] ← Key
    NEXT i
ENDPROCEDURE

InsertionSort is called on Arr = [29, 10, 14, 37, 8, 22] (index 1 to index 6).

(a) State the contents of Arr, in order, immediately after the outer loop iteration where i = 3 completes (i.e. once Key = 14 has been inserted into its correct position). [2]

(b) State the contents of Arr, in order, immediately after the outer loop iteration where i = 5 completes, showing which values are shifted rightward by the WHILE loop to make room for Key = 8. [4]

(c) State the final, fully sorted contents of Arr once the procedure completes, and explain one way in which insertion sort's method of placing each Key differs from bubble sort's method of repeatedly comparing and swapping adjacent elements. [2]

A programmer solves the same simple task, deciding whether a number is even or odd, three times, using three different programming paradigms.

Snippet 1, a simplified low-level (assembly-style) instruction sequence, operating on a register R1:

LOAD R1, Num
AND R1, R1, #1
CMP R1, #0
JUMPIFEQUAL IsEven

Snippet 2, written in pseudocode:

DECLARE Num : INTEGER
IF (Num MOD 2) = 0 THEN
    OUTPUT "Even"
ELSE
    OUTPUT "Odd"
ENDIF

Snippet 3, written in a declarative, logic-based style:

even(X) :- 0 is X mod 2.
odd(X) :- 1 is X mod 2.

(a) Identify which programming paradigm (low-level, imperative, or declarative) each of the three snippets represents. [3]

(b) For Snippet 1, explain one feature of the code that identifies it as low-level programming, referring to what the instructions directly manipulate. [2]

(c) For Snippet 3, explain how declarative programming differs fundamentally from imperative programming, in terms of what the programmer specifies to the computer. [3]

A programmer writes the following pseudocode to count how many records are stored in a text file, using exception handling in case the file cannot be found.

DECLARE StudentRecord : STRING
DECLARE Total : INTEGER
Total ← 0

TRY
    OPENFILE "Scores.txt" FOR READ
    WHILE NOT EOF("Scores.txt")
        READFILE "Scores.txt", StudentRecord
        Total ← Total + 1
    ENDWHILE
    CLOSEFILE "Scores.txt"
    OUTPUT "Records read", Total
CATCH FileNotFound
    OUTPUT "Error, file could not be opened"
ENDTRY

(a) Explain the purpose of EOF("Scores.txt") in the WHILE loop's condition, and state what would be likely to happen if the loop instead used WHILE TRUE DO with no EOF check. [2]

(b) Explain the purpose of the TRY ... CATCH ... ENDTRY structure in this pseudocode, describing what the program does if "Scores.txt" does not exist, compared with what would be likely to happen without exception handling. [3]

(c) "Scores.txt" exists and contains 5 records. State the value of Total output by this program, explaining your reasoning; then state what would instead be output if "Scores.txt" did not exist. [3]