Paper 2 Implementing Algorithms Answers

These answers correspond to Paper 2 Implementing Algorithms Drills.

Verification note: the model snippets in this file were executed locally as standalone Python snippets on 2026-07-09.

Answer 1: Implement Linear Search

def linear_search(values, target):
    for index in range(len(values)):
        if values[index] == target:
            return index
    return -1
 
 
print(linear_search([14, 3, 27, 9], 27))
print(linear_search([14, 3, 27, 9], 5))

Expected output:

2
-1

Mark points:

• loops through valid indexes;
• compares each item with the target;
• returns the found index;
• returns -1 only after the loop;
• shows both required outputs.

Common weak answer:

• returning False instead of the required index or -1.

Answer 2: Implement Insertion Sort

def insertion_sort(values):
    result = values[:]
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position = position - 1
        result[position + 1] = current
    return result
 
 
data = [8, 4, 6, 2]
print(insertion_sort(data))
print(data)

Expected output:

[2, 4, 6, 8]
[8, 4, 6, 2]

Mark points:

• copies the input list;
• scans from the second item;
• stores the current value;
• shifts larger values right;
• inserts the current value in the correct gap;
• returns the sorted copy;
• leaves the original list unchanged;
• shows both required outputs.

Common weak answer:

• sorting the original list in place when the question asks for a new sorted list.

Answer 3: Implement Fixed Stack

class FixedStack:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.top = -1
        self.capacity = capacity
 
    def push(self, value):
        if self.top == self.capacity - 1:
            return False
        self.top = self.top + 1
        self.items[self.top] = value
        return True
 
    def pop(self):
        if self.top == -1:
            return None
        value = self.items[self.top]
        self.items[self.top] = None
        self.top = self.top - 1
        return value
 
 
s = FixedStack(2)
print(s.push("A"))
print(s.push("B"))
print(s.push("C"))
print(s.pop())
print(s.pop())
print(s.pop())

Expected output:

True
True
False
B
A
None

Mark points:

• initialises fixed storage, top, and capacity;
• checks overflow before push;
• updates top before storing pushed data;
• returns False when full;
• checks underflow before pop;
• returns last pushed item first;
• clears or ignores the removed slot safely;
• returns None when empty;
• shows required outputs.

Common weak answer:

• incrementing top before checking for overflow.

Answer 4: Implement Circular Queue

class CircularQueue:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.front = 0
        self.rear = -1
        self.count = 0
        self.capacity = capacity
 
    def enqueue(self, value):
        if self.count == self.capacity:
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.items[self.rear] = value
        self.count = self.count + 1
        return True
 
    def dequeue(self):
        if self.count == 0:
            return None
        value = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.count = self.count - 1
        return value
 
    def display_array(self):
        return self.items[:]
 
 
q = CircularQueue(3)
print(q.enqueue("A"))
print(q.enqueue("B"))
print(q.enqueue("C"))
print(q.dequeue())
print(q.enqueue("D"))
print(q.display_array())
print(q.dequeue())

Expected output:

True
True
True
A
True
['D', 'B', 'C']
B

Mark points:

• initialises array, front, rear, count, and capacity;
• checks full condition before enqueue;
• updates rear with modulo arithmetic;
• stores new value at rear;
• checks empty condition before dequeue;
• removes from front;
• updates front with modulo arithmetic;
• updates count correctly;
• shows wrap-around in the displayed array;
• produces the required outputs.

Common weak answer:

• using rear = rear + 1 without modulo, so enqueue after wrap-around fails.

Answer 5: Implement Linked Insert

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
def insert_head(head, value):
    new_node = Node(value)
    new_node.next = head
    return new_node
 
 
def to_list(head):
    values = []
    current = head
    while current is not None:
        values.append(current.data)
        current = current.next
    return values
 
 
head = None
for value in [30, 20, 10]:
    head = insert_head(head, value)
 
print(to_list(head))

Expected output:

[10, 20, 30]

Mark points:

• defines a node with data and next;
• creates a new node;
• points the new node to the old head;
• returns the new node as the new head;
• updates head after each insertion;
• traverses the list to show the result;
• produces the required output.

Common weak answer:

• setting head to the new node before linking the new node to the old head.

Answer 6: Implement Linked Search

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
def linked_search(head, target):
    current = head
    while current is not None:
        if current.data == target:
            return True
        current = current.next
    return False
 
 
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
 
print(linked_search(head, 20))
print(linked_search(head, 99))

Expected output:

True
False

Mark points:

• starts from head;
• loops until None;
• compares each node’s data;
• returns True when found;
• moves to the next node each iteration;
• returns False when absent;
• shows both required outputs.

Common weak answer:

• forgetting to advance to current.next, causing an infinite loop.

Answer 7: Implement BST Insert

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root
 
 
root = None
for value in [40, 25, 60, 15, 30]:
    root = insert(root, value)
 
print(root.data)
print(root.left.data)
print(root.right.data)

Expected output:

40
25
60

This implementation ignores duplicate values; another valid implementation may consistently place duplicates on one side if documented.

Mark points:

• defines node fields data, left, and right;
• creates a node when the current root is None;
• places smaller values in the left subtree;
• places larger values in the right subtree;
• preserves the returned subtree root;
• ignores or handles duplicates consistently;
• produces the required output.

Common weak answer:

• replacing the root every time a value is inserted.

Answer 8: Implement BST Traversal

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.data:
        root.left = insert(root.left, value)
    elif value > root.data:
        root.right = insert(root.right, value)
    return root
 
 
def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.data] + inorder(root.right)
 
 
root = None
for value in [40, 25, 60, 15, 30]:
    root = insert(root, value)
 
print(inorder(root))

Expected output:

[15, 25, 30, 40, 60]

This implementation ignores duplicate values; another valid implementation may consistently place duplicates on one side if documented.

Mark points:

• handles an empty subtree;
• visits the left subtree first;
• includes the current node between left and right;
• visits the right subtree last;
• returns a list;
• produces the correct inorder output.

Common weak answer:

• using root-left-right order, which is preorder rather than inorder.

Answer 9: Serial File Search

with open("serial_records.txt", "w", encoding="utf-8") as file:
    file.write("C03,Asha\n")
    file.write("C01,Ben\n")
    file.write("C04,Chen\n")
    file.write("C02,Divya\n")
 
 
def serial_search(filename, key):
    with open(filename, "r", encoding="utf-8") as file:
        for line in file:
            record = line.strip()
            record_key = record.split(",")[0]
            if record_key == key:
                return record
    return "NOT FOUND"
 
 
print(serial_search("serial_records.txt", "C01"))

Expected output:

C01,Ben

Mark points:

• opens the file for reading;
• reads records from the start;
• strips newline characters;
• extracts the key field;
• compares the key with the target;
• returns the first matching record;
• returns not found only after the file ends.

Common weak answer:

• assuming the serial file is sorted and stopping early.

Answer 10: Sequential File Early Stop

with open("sequential_records.txt", "w", encoding="utf-8") as file:
    file.write("101,Asha\n")
    file.write("105,Ben\n")
    file.write("109,Chen\n")
    file.write("114,Divya\n")
 
 
def sequential_search(filename, key):
    with open(filename, "r", encoding="utf-8") as file:
        for line in file:
            record = line.strip()
            current_key = record.split(",")[0]
            if current_key == key:
                return record
            if current_key > key:
                return "NOT FOUND STOPPED AT " + current_key
    return "NOT FOUND"
 
 
print(sequential_search("sequential_records.txt", "105"))
print(sequential_search("sequential_records.txt", "107"))

Expected output:

105,Ben
NOT FOUND STOPPED AT 109

In this example the keys have the same length, so text comparison gives the same order as numeric comparison. If numeric keys of different lengths are used, convert them before comparing.

Mark points:

• opens the ordered file;
• reads records in key order;
• extracts the key field;
• returns the matching record when found;
• compares current key with target key;
• stops early when current key has passed the target;
• returns a clear not-found result;
• shows both required outputs.

Common weak answer:

• scanning to the end even after reading key 109 while searching for 107.