Paper 1 Implementing Algorithms Answers

These answers correspond to Paper 1 Implementing Algorithms Drills.

Answer 1: Implementation Preconditions

1. Binary search requires the array/list to be sorted and indexable.
2. BST search requires the tree to obey the BST ordering rule used by the implementation, e.g. smaller values go left and larger values go right; if duplicates are allowed, the duplicate policy must be consistent.

Mark points:

• 1 mark for sorted indexed data for binary search;
• 1 mark for BST ordering invariant.

Common weak answer:

• saying binary search only needs “many values”; the important precondition is sorted order.

Answer 2: Array Stack Trace

Trace:

Operation	array state	top
start	[-, -, -, -]	-1
PUSH 11	[11, -, -, -]	0
PUSH 6	[11, 6, -, -]	1
POP	[11, -, -, -]	0
PUSH 9	[11, 9, -, -]	1
PUSH 14	[11, 9, 14, -]	2

Final state:

items = [11, 9, 14, -]
top = 2

Mark points:

• push 11 at index 0;
• push 6 then pop it;
• push 9 at index 1;
• push 14 at index 2;
• final top is 2.

Common weak answer:

• leaving 6 in the stack after POP.

Answer 3: Circular Queue Full and Empty Checks

1. Empty condition: count = 0.
2. Full condition: count = capacity, so here count = 5.
3. Next rear index: (1 + 1) MOD 5 = 2.
4. Modulo arithmetic wraps the rear or front index back to 0 after the end of the array is reached.

This uses the convention that rear stores the index of the most recently enqueued item, so the next insertion position is (rear + 1) MOD capacity.

Mark points:

• correct empty condition;
• correct full condition;
• correct next rear index 2;
• explains wrap-around.

Common weak answer:

• checking only whether rear is at the final array index. A circular queue may wrap and use earlier positions.

Answer 4: Linked Insert at Head

Correct creation/use and pointer updates:

newNode.data <- 12
newNode.next <- head
head <- newNode

The essential pointer order is:

newNode.next <- head
head <- newNode

Final list:

head -> [12 | next] -> [20 | next] -> [35 | NULL]

Mark points:

• create/use the new node containing 12;
• point the new node to the old head first;
• update head to point to the new node.

Common weak answer:

• updating head first, which loses access to the original list.

Answer 5: BST Insert Trace

Comparisons:

25 < 45, so move left to 20.
25 > 20, so move right to 30.
25 < 30, so insert as the left child of 30.

Updated tree:

        45
      /    \
    20      70
   /  \    /
 10   30  60
     /
    25

Mark points:

• starts comparison at root 45;
• moves left to 20;
• moves right to 30;
• places 25 as left child of 30;
• preserves the rest of the tree.

Common weak answer:

• inserting 25 as the right child of 20 directly even though 30 already occupies that position.

Answer 6: Serial File Search

Records inspected:

C03,Asha
C01,Ben
C04,Chen
C02,Divya

The search stops when C02,Divya is found. Because the file is serial, there is no useful key order, so the program cannot stop early before either finding the target or reaching the end of the file.

Mark points:

• records are read from the start;
• all four records are inspected before C02 is found;
• search stops when the matching key is found.

Common weak answer:

• assuming the records are sorted by key and stopping at C03.

Answer 7: Sequential File Search

Records inspected:

101,Asha
105,Ben
109,Chen

The target key is 107. When the program reaches key 109, the current key has passed 107. Since the file is ordered, 107 cannot appear later, so the search can stop and return not found.

Mark points:

• reads 101;
• reads 105;
• reads 109;
• explains early stop because 109 > 107 in an ordered file.

Common weak answer:

• continuing to inspect 114,Divya; this is unnecessary once the key has been passed.

Answer 8: Implementation Choice

1. Sorted Python list of 1000 IDs: binary search, because the list is sorted and indexable.
2. Browser Back button: stack, because the most recent page should be returned to first.
3. Print jobs in arrival order: queue, because jobs should be processed first-in-first-out.

Mark points:

• binary search linked to sorted indexed data;
• stack linked to last-in-first-out;
• queue linked to first-in-first-out.

Common weak answer:

• choosing linear search for the sorted list without mentioning why binary search is available.

Answer 9: Pseudocode Completion

Completed pseudocode:

FUNCTION Pop()
    IF top = -1 THEN
        RETURN "UNDERFLOW"
    ENDIF
    item <- stack[top]
    top <- top - 1
    RETURN item
ENDFUNCTION

item is saved first because after top is decremented, stack[top] would refer to a different position.

Mark points:

• 1 mark for item <- stack[top];
• 1 mark for top <- top - 1;
• 1 mark for RETURN item;
• 1 mark for explaining why the item is saved before changing top.

Common weak answer:

• decrementing top before saving stack[top], which returns the wrong item.

Answer 10: Error Identification

The error is that head <- newNode is done before newNode.next <- head. After head is changed, head no longer refers to the old first node, so the original list is lost.

Correct order:

newNode.data <- 12
newNode.next <- head
head <- newNode

Mark points:

• identifies that updating head too early loses the old list;
• explains that newNode.next points to the new node itself in the faulty code;
• gives newNode.next <- head before updating head;
• gives head <- newNode after preserving the old head link.

Common weak answer:

• only swapping the first two lines. The data assignment is not the problem; the pointer order is.