Algorithms and Data Structures

Algorithms and Data Structures — CIE A Level Computer Science 9618

1. Algorithm Analysis

Time complexity: How runtime grows with input size n.

| Notation | Name | Example |

|---|---|---|

| O(1) | Constant | Array element access |

| O(log n) | Logarithmic | Binary search |

| O(n) | Linear | Linear search |

| O(n log n) | Log-linear | Merge sort |

| O(n²) | Quadratic | Bubble sort |

| O(2ⁿ) | Exponential | Brute-force subset problems |

Space complexity: Memory used relative to input size.

2. Searching Algorithms

Linear Search:

• Check each element sequentially until found or list exhausted
• Time complexity: O(n) best case O(1), worst case O(n)
• Works on unsorted lists

~~~

FOR i ← 1 TO Length

IF List[i] = Target THEN

RETURN i

ENDIF

NEXT i

RETURN -1 // not found

~~~

Binary Search: (requires sorted list)

• Compare target to middle element
• If target < middle: search left half; if target > middle: search right half
• Halves the search space each step
• Time complexity: O(log n)

~~~

Low ← 1

High ← Length

WHILE Low <= High DO

Mid ← (Low + High) DIV 2

IF List[Mid] = Target THEN

RETURN Mid

ELSEIF List[Mid] < Target THEN

Low ← Mid + 1

ELSE

High ← Mid - 1

ENDIF

ENDWHILE

RETURN -1

~~~

Why binary over linear? For 1,000,000 elements: linear needs up to 1,000,000 comparisons; binary needs at most 20 (log₂ 1,000,000 ≈ 20).

3. Sorting Algorithms

Bubble Sort: Compare adjacent pairs, swap if out of order. Repeat.

• Time: O(n²). Space: O(1). Stable. Simple but slow.

Insertion Sort: Build sorted list one element at a time; insert each new element into correct position.

• Time: O(n²) worst case; O(n) best case (already sorted). Good for nearly-sorted data.

Merge Sort: Divide and conquer — split list in half recursively until single elements; merge sorted halves.

• Time: O(n log n) always. Space: O(n). Stable. Efficient for large data.

Quick Sort: Choose a pivot; partition into elements smaller/larger; recurse on each partition.

• Time: O(n log n) average; O(n²) worst case (bad pivot). Space: O(log n). Fastest in practice.

4. Stacks

A stack is a Last In, First Out (LIFO) data structure.

Operations:

• PUSH: Add element to top. O(1)
• POP: Remove and return top element. O(1)
• PEEK/TOP: View top without removing. O(1)
• isEmpty: Check if stack is empty. O(1)

Implementation with array:

~~~

DECLARE Stack : ARRAY[1:100] OF INTEGER

DECLARE Top : INTEGER ← 0

PROCEDURE Push(Item : INTEGER)

IF Top = 100 THEN

OUTPUT "Stack overflow"

ELSE

Top ← Top + 1

Stack[Top] ← Item

ENDIF

ENDPROCEDURE

FUNCTION Pop() RETURNS INTEGER

IF Top = 0 THEN

OUTPUT "Stack underflow"

ELSE

Pop ← Stack[Top]

Top ← Top - 1

ENDIF

ENDFUNCTION

~~~

Applications: Function call stack (recursion), undo operations, expression evaluation, browser history (back button).

5. Queues

A queue is a First In, First Out (FIFO) data structure.

Operations:

• ENQUEUE: Add to back (rear). O(1)
• DEQUEUE: Remove from front. O(1)
• isEmpty / isFull: Check state. O(1)

Circular queue: Front and rear pointers wrap around — avoids wasted space problem of simple queue.

Applications: Print job scheduling, CPU process scheduling, network packet routing, keyboard buffer.

Priority queue: Elements dequeued in order of priority, not arrival. Used in Dijkstra's shortest path algorithm, A* search.

6. Linked Lists

A linked list stores elements in nodes. Each node contains:

• Data (payload)
• Pointer (address of next node)

Types:

• Singly linked: Each node → next only
• Doubly linked: Each node → previous AND next (enables backward traversal)
• Circular: Last node → first node

Advantages over arrays:

• Dynamic size — nodes allocated as needed (no fixed size)
• Efficient insertion/deletion at any position: change pointers, O(1) if position known

Disadvantages:

• No random access — must traverse from head: O(n) to find element
• Extra memory for pointers
• Cache-unfriendly (nodes scattered in memory)

7. Binary Trees

A tree is a hierarchical data structure. A binary tree has at most 2 children per node.

Key terms:

• Root: Topmost node (no parent)
• Leaf: Node with no children
• Height: Longest path from root to leaf
• Subtree: Any node and its descendants

Binary Search Tree (BST):

• Left subtree: all values < current node
• Right subtree: all values > current node
• Search: O(log n) balanced, O(n) worst case (degenerate/linear)

Tree traversals:

• Pre-order (root, left, right): Used to copy/serialize tree
• In-order (left, root, right): Gives sorted output for BST ✓
• Post-order (left, right, root): Used to delete tree, evaluate expressions

Example BST with values 5, 3, 7, 1, 4:

~~~

5

/ 3 7

/ 1 4

~~~

In-order traversal: 1, 3, 4, 5, 7 (sorted!)