2.1, 2.3

OOP v Procedural

OOP defines objects as independent entities with private attributes and methods; allows multiple instances without rewriting declarations; reduces code quantity and errors via reuse; subroutines self-contained ⟶ Procedural code executes statements in written order, requiring correct variable passing or use of globals

How private attributes improve the integrity of data

Properties are encapsulated and only accessible via methods; validation enforced on assignment; prevents accidental access or modification

What is meant by a record

A data structure storing multiple values (possibly of different types) under one identifier

Why a 1D array is suitable for a record

Enables indexed access to each item; holds multiple elements of the same type

Function

A routine that returns a value

Procedure

A routine that does not return a value

Similarities and differences of a record and a class

A record is a passive data structure; a class is a template for objects with private attributes and methods; both can store multi-type data under one name

Count-controlled loop meaning

A loop that repeats a fixed number of times

Purpose of pointerValue in stack

Points to the top of the stack (next free slot in the array)

Implementing a stack as a 1D array

Define array size; maintain a stack pointer; increment on push, decrement on pop

How a queue can be implemented using an array

Use head and tail pointers; increment tail on enqueue, head on dequeue (wrap via modulo)

Describe enqueue

Check for full: if (tail+1)%length == head then fail; advance tail = (tail+1)%length; store element at tail

Purpose of head pointer in a queue

Points to the first element (next to be removed)

Purpose of tail pointer in a queue

Points to the last element (most recently added)

Define queue

A dynamic FIFO data structure

Queue vs Stack

Queue is FIFO; Stack is LIFO

Characteristics of trees

Hierarchical with a root and leaves; nodes linked by edges; no cycles

How a leaf node is deleted from a BST

Locate node; clear its content; have parent point to node’s right child (or null); add cleared node to free list

Adding a node to a BST

Traverse to find parent; create new node; link parent to this node

Describe how a BST can be searched

Check root; if equal, done; if less traverse left subtree; if greater traverse right; repeat until found or empty

Directed vs Undirected graphs

Directed graphs have one-way edges; undirected have two-way

Graph vs Tree

Graphs have no fixed root, may have cycles and weights; trees are acyclic, rooted, hierarchical

Similarities of graph and tree

Both consist of nodes connected by edges; both are dynamic, non-linear structures

Purpose of headPointer in linked list

Indicates the first node in the list

Purpose of freeListPointer in linked list

Points to the next free node for insertion

Meaning of null pointer in linked list

Indicates end of the list (no further node)

Describe how a new item is added to end of a linked list

Check freeListPointer != null; insert at freeListPointer; traverse to last node; link its next to new; update freeListPointer

How an item is removed from a linked list

Traverse to node before target; set its next pointer to target.next

How backtracking is used in depth-first traversal

Descend one branch to leaf, pushing visited nodes onto stack; on leaf backtrack to last node with unvisited children; repeat

Breadth-first vs Depth-first

Breadth-first uses a queue, good when target is near root, O(n) time; Depth-first uses a stack (or recursion), good when target is deep, O(n) time, linear space

Max number of passes to bubble sort list of length N

N

Describe bubble sort

Compare each pair of adjacent elements, swapping if out of order; repeat passes until no swaps occur

Bubble sort complexities

Best O(n); average/worst O(n²); space O(1)

Disadvantages of bubble sort

Inefficient O(n²) worst time; outperformed by insertion, quick-, and merge-sort

Insertion sort complexities

Best O(n); worst O(n²); space O(1)

Describe merge sort

Recursively split list into sublists until single items; merge pairs by comparing heads into a new list; repeat until fully merged

Describe quicksort

Select pivot; partition elements into less-and greater-than lists; recursively sort partitions

Why quicksort is divide-and-conquer

Decomposes problem into smaller subsets, sorts each, then combines

Define heuristics

Rules-of-thumb estimating distance to goal, guiding search order

Precondition of binary search

Data must be ordered

Binary search complexities

Time O(log n); space O(1)

Describe binary search

Compute midpoint; compare to target; if equal return; if less search right (or left if greater); repeat until bounds cross

Describe linear search

Scan sequentially comparing each element to target until found or end reached

Linear search complexity

Time O(n); space O(1)

Define abstraction

Removal of unnecessary details to focus on core aspects

Need for abstraction

Reduces development time and code complexity; lowers resource requirements; simplifies understanding

Define caching

Storing previously accessed data for faster future retrieval

Benefits and drawbacks of caching

Improves speed when items repeat; relies on data locality

Need for reusable components

Improves efficiency, maintainability and readability; enables independent testing; saves development time; supports libraries and collaboration

Define decomposition

Breaking a problem into smaller sub-problems

Why decompose

Makes development, testing and reuse easier; enables parallel work; clarifies design

Describe concurrent processing

Multiple threads/processes run in parallel (or interleaved), each with processor time slices

Benefits of concurrent processing

Better CPU utilisation; long tasks don’t block short; keeps UI responsive

Benefits on shared data structures

Handles multiple simultaneous requests; avoids queuing delays; allows parallel reads/writes

Drawbacks of concurrent processing

Some tasks must remain serial; speedup not linear with cores; adds complexity

Drawbacks on shared data structures

Storage bottlenecks; requires locking (risk of deadlocks); complicates programming