CMS 702 · Data Structures & Computer Algorithms

Types of algorithms (10): Brute force · Recursive · Encryption · Backtracking · Search · Sort · Divide and conquer · Greedy · Dynamic programming · Randomized

Three cases in asymptotic analysis: Worst · Best · Average

Three asymptotic notations: Big O (upper) · Θ (tight) · Ω (lower)

Five complexity classes: O(1) constant · O(log n) logarithmic · O(n) linear · O(n²) quadratic · O(2ⁿ) exponential

Five sort algorithms from class: Merge · Quick · Bucket · Heap · Counting

Three components of hashing: Key · Hash function · Hash table

Four properties of a good hash function: efficiently computable · uniformly distributes the keys · minimizes collision · low load factor

Two collision-handling methods: Separate chaining (each cell points to a linked list of records) · Open addressing (all elements stored in the table itself)

Three types of data structure: Inbuilt/primitive (integer, float, boolean) · Derived (stack, queue, list, array) · Complex (linked list, tree, graph)

Six basic operations: Traversal · Searching · Sorting · Merging · Insertion · Deletion

Three types of linked list: Simple (singly) · Complex (doubly) · Circular

Three properties of a tree: one root node, which has no parent · each node has one parent only but may have many children · each node connects to its children via an edge

Four properties of a BST: left sub-tree strictly less · right sub-tree strictly greater · recursively true of every sub-tree · no duplicate keys

Upper complexity bound guarantees performance in the worst case · the algorithm will never behave unexpectedly poorly. Average complexity is the expected performance given that all inputs of a certain size follow a certain distribution.

Third example worth naming: BST search · exploits the BST property to discard half the tree at each node, O(log n) on a balanced tree.

Binary search worked · find 7 in 1 2 3 4 7 9

Step 1:  1  2  3 [4] 7  9    middle = 4, 7 > 4
                             → discard the LEFT half
Step 2:              7 [9]   middle = 9, 7 < 9
                             → discard the RIGHT half
Step 3:             [7]      FOUND

Each step halves the search space · n → n/2 → n/4 → … · which is exactly why the cost is log₂ n.

Example · Fibonacci

Naïve recursion · O(2ⁿ)
fib(5) → fib(4) + fib(3)
         fib(3)+fib(2)  fib(2)+fib(1)
         ↑ fib(3), fib(2) recomputed

With DP · O(n)

fib[0] = 0
fib[1] = 1
for i = 2 to n:
    fib[i] = fib[i-1] + fib[i-2]

Diagram · key → hash function → bucket

Worked example from class

Store {"ab", "cd", "efg"} in a table of size 7, with a=1, b=2 … g=7. Rule: index = sum mod table_size.

ab  = 1 + 2     =  3  →  3 mod 7 = index 3
cd  = 3 + 4     =  7  →  7 mod 7 = index 0
efg = 5 + 6 + 7 = 18  → 18 mod 7 = index 4

index:  0     1    2    3     4    5    6
      ┌────┬────┬────┬────┬─────┬────┬────┐
      │ cd │    │    │ ab │ efg │    │    │
      └────┴────┴────┴────┴─────┴────┴────┘

Always show three steps: the sum → the modulo → the slot. If two keys land on the same slot, name it a collision and give the fix.

Height · Depth · Degree · the classic 5-mark question

• Depth of a node = number of edges from the root down to that node.
• Height of a node = number of edges from that node down to its deepest leaf.
• Height of the tree = height of the root = the longest path in edges to a leaf.
• Degree of a node = the total number of branches at that node.

            10        d=0, h=3   ← height of tree = 3
           /  \
          5    8      5: d=1, h=2
         / \  / \
        2   3 7  9    2: d=2, h=1
       /
      1                1: d=3, h=0  (leaf)

Memory hook: the position of Root in the name is its position in the visit order · pre = first, in = middle, post = last. Left always comes before Right.

          20
         /  \
        8    22
       / \
      4   12
         /  \
       10    14

In-order   : 4, 8, 10, 12, 14, 20, 22   ← sorted
Pre-order  : 20, 8, 4, 12, 10, 14, 22
Post-order : 4, 10, 14, 12, 8, 22, 20

• In-order successor of K = the node with the smallest value greater than K. If no such node exists, return −1.
• In-order predecessor of K = the previous node in the in-order traversal. It is null for the first node.

On the tree above, in-order = 4, 8, 10, 12, 14, 20, 22:

(a) From a list of values

Insert one value at a time starting from the root: go left if smaller, right if larger. From (37, 21, 13, 40, 36, 50):

          37
         /  \
       21    40
      /     /  \
    13    36    50

In-order   : 13, 21, 36, 37, 40, 50   ← sorted ✓
Pre-order  : 37, 21, 13, 40, 36, 50
Post-order : 13, 21, 36, 50, 40, 37

(b) From two traversals

Pre-order + In-order: the first element of the pre-order is the root → find it in the in-order → everything to its left is the left sub-tree, everything to its right is the right sub-tree → recurse on each side.
Post-order + In-order: identical method, except the last element of the post-order is the root.

Pre-order = 1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7
In-order  = 8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7

Root = 1 → left = 8,4,10,9,11,2,5 | right = 6,3,7

              1
            /   \
           2      3
          / \    / \
         4   5  6   7
        / \
       8   9
          /  \
        10    11

Representation in memory

ARRAY
Name: Int Array(10)
        ↑      ↑
      Type    Size
Elements: {35,33,42,10,14,19,27,44,26,31}

LINKED LIST
[Head] → [Data|•] → [Data|•] → [Data|•] → NULL
            Node       Node       Node

Types of array: fixed-size · cannot be altered, indexes are numbered; dynamic-size · can be altered/resized, may be one-, two- or three-dimensional.
Types of linked list: simple (singly) · complex (doubly) · circular.

Deleting a node from a singly linked list

Head → [A|•] → [TARGET|•] → [C|•] → NULL
          └──────────────────↗
Locate the target, then redirect the previous
node's pointer past it to the target's next node.

Stack · LIFO

An abstract data type named after a real-world stack (a pile of plates, a stack of pizza), which allows operations at one end only, one at a time. Insertion is PUSH, removal is POP. It can be implemented with arrays, pointers, linked lists or structures, and can be fixed-size or dynamic.

        PUSH ↓   ↑ POP
       ┌──────────────┐
       │ ▓▓▓▓▓▓▓▓▓▓▓▓ │   LIFO
       │ ▓▓▓▓▓▓▓▓▓▓▓▓ │   one end only
       └──────────────┘

Queue · FIFO

Similar to the stack but open at both ends and following FIFO. Enqueue() adds at the rear, Dequeue() removes from the front.

   Dequeue                          Enqueue
  (remove) ←── [A][B][C][D] ←── (insert)
               front       rear
                    F I F O

Example · undirected, vertices A B C, edges AB and BC

Adjacency Matrix        Adjacency List
    A  B  C             A → B
A [ 0  1  0 ]           B → A, C
B [ 1  0  1 ]           C → B
C [ 0  1  0 ]

Traversals · link them back to the notes:
BFS (Breadth-First Search) uses a queue (FIFO) and visits level by level · O(V + E).
DFS (Depth-First Search) uses a stack (LIFO) or recursion and goes as deep as possible first · O(V + E).

Stack allocation vs heap allocation

Run-time storage management is the system's job of allocating memory while a program runs and reclaiming it afterwards · the stack for call frames, the heap for dynamic data, plus garbage collection (automatic reclamation of unreachable objects) or manual deallocation.

Recursive algorithms

A recursive algorithm solves a problem by calling itself on smaller sub-problems. Every recursion needs (1) a base case that stops it and (2) a recursive case that moves toward the base case.

factorial(n):
    if n <= 1:  return 1                  # base case
    else:  return n * factorial(n - 1)    # recursive

• Each call consumes a stack frame → recursion costs O(depth) space.
• A missing or wrong base case causes infinite recursion → stack overflow.
• Recursion vs iteration: recursion is shorter and natural for trees and divide-and-conquer; iteration avoids call-stack overhead.

Time–space tradeoff

An algorithm can often be made faster by using more memory, or made to use less memory at the cost of running longer. Examples to cite:

• A hash table spends O(n) extra space to turn an O(n) search into O(1) · space buys speed.
• Merge sort uses O(n) extra space to guarantee O(n log n); quick sort uses only O(log n) but risks O(n²).
• Counting sort uses an O(k) count array to avoid comparisons entirely.
• Memoization in DP stores sub-results to avoid recomputation.

Ten easy marks people lose

1. Writing O for the tight bound · the tight bound is Θ.
2. Saying a queue is open at one end · that is the stack. A queue is open at both ends.
3. Forgetting the −1 when an in-order successor does not exist (and null for a missing predecessor).
4. Swapping depth and height. Depth counts down from the root; height counts up from the leaves.
5. Running binary search on unsorted data · it requires a sorted dataset. O(log n).
6. Forgetting that a BST's in-order traversal is sorted · the free check on every tree you draw.
7. Defining a term without giving the example the question asked for.
8. Answering a comparison question in prose instead of a table.
9. Drawing an asymptotic diagram with no axes labels and no n₀.
10. Confusing the stack/heap memory regions with the stack/heap data structures.

Self-test · cover the right column