COMP9024 - Data Structures & Algorithms (UNSW) Flashcards

Question 1

Big-$O$ Notation (Formal Definition)

Accepted Answer

A function $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

It provides an asymptotic **upper bound** on the growth rate of a algorithm's running time or memory usage.

Question 2

Big-$\Omega$ and Big-$\Theta$ Notation

Accepted Answer

- **Big-$\Omega$ ($f(n) = \Omega(g(n))$)**: Asymptotic **lower bound**. Exists $c > 0, n_0 > 0$ such that $f(n) \ge c \cdot g(n)$ for all $n \ge n_0$.
- **Big-$\Theta$ ($f(n) = \Theta(g(n))$)**: Asymptotic **tight bound**. $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ simultaneously.

Question 3

Master Theorem for Divide-and-Conquer Recurrences

Accepted Answer

For $T(n) = aT(n/b) + f(n)$ where $a \ge 1, b > 1$:
1. If $f(n) = O(n^{\log_b a - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ and regularity holds, then $T(n) = \Theta(f(n))$.

Question 4

Breadth-First Search (BFS)

Accepted Answer

Graph traversal algorithm that explores vertices level-by-level using a **Queue** (`FIFO`).

- **Time Complexity**: $O(V + E)$
- **Space Complexity**: $O(V)$
- **Key Property**: Finds the shortest path in an **unweighted** graph.

Question 5

Depth-First Search (DFS)

Accepted Answer

Graph traversal algorithm that explores as deep as possible along each branch before backtracking using a **Stack** (`LIFO`) or recursion.

- **Time Complexity**: $O(V + E)$
- **Space Complexity**: $O(V)$
- **Applications**: Topological sorting, detecting cycles, finding strongly connected components.

Question 6

Dijkstra's Algorithm

Accepted Answer

Single-source shortest path algorithm for graphs with **non-negative edge weights**.

- **Strategy**: Greedy selection using a Priority Queue (`Min-Heap`).
- **Time Complexity**: $O((V + E) \log V)$ with Binary Heap; $O(E + V \log V)$ with Fibonacci Heap.
- **Failure Case**: Fails on graphs with negative edge weights.

Question 7

Bellman-Ford Algorithm

Accepted Answer

Single-source shortest path algorithm that handles graphs with **negative edge weights** and detects **negative-weight cycles**.

- **Strategy**: Relaxes all $|V| - 1$ edges $|V| - 1$ times.
- **Time Complexity**: $O(V \cdot E)$
- **Space Complexity**: $O(V)$

Question 8

Kruskal's Algorithm

Accepted Answer

Greedy Minimum Spanning Tree (MST) algorithm that sorts all edges by weight and adds them if they don't form a cycle.

- **Data Structure**: Uses a Disjoint-Set / Union-Find data structure with Path Compression.
- **Time Complexity**: $O(E \log E)$ or $O(E \log V)$ due to edge sorting.

Question 9

Prim's Algorithm

Accepted Answer

Greedy Minimum Spanning Tree (MST) algorithm that grows a single tree by adding the cheapest edge connecting a vertex in the tree to a vertex outside it.

- **Data Structure**: Min-Heap (Priority Queue).
- **Time Complexity**: $O(E \log V)$ using a binary heap, identical to Dijkstra's implementation structure.

Question 10

AVL Tree: Balance Factor & Invariant

Accepted Answer

An AVL tree is a self-balancing Binary Search Tree.

- **Balance Factor ($BF$)**: $BF(v) = 	ext{height}(	ext{left}(v)) - 	ext{height}(	ext{right}(v))$
- **AVL Invariant**: For every node $v$, $BF(v) \in \{-1, 0, 1\}$.
- **Tree Height**: $h = O(\log n)$, guaranteeing search, insertion, and deletion in $O(\log n)$ time.

Question 11

AVL Tree Rotations

Accepted Answer

Restores the AVL invariant after insertion/deletion when $BF(v) = \pm 2$:
- **Single Rotation**: Left-Left (LL) -> Right Rotation; Right-Right (RR) -> Left Rotation.
- **Double Rotation**: Left-Right (LR) -> Left Rotation on child, then Right Rotation on node; Right-Left (RL) -> Right Rotation on child, then Left Rotation on node.

Question 12

2-3-4 Tree Node Types & Properties

Accepted Answer

A multi-way search tree where all leaves are at the same depth:
- **2-node**: 1 key, 2 children
- **3-node**: 2 keys, 3 children
- **4-node**: 3 keys, 4 children

Isomorphic to Red-Black Trees. Guarantees $O(\log n)$ search, insert, and delete operations.

Question 13

2-3-4 Tree Preemptive Insertion

Accepted Answer

When searching down the tree to insert a key, any encountered **4-node is split** immediately before moving down.

- **Middle key** moves up to the parent node.
- Prevents cascade splits back up the tree, making insertion a single top-down pass.

Question 14

Hash Collision Resolution: Separate Chaining vs Open Addressing

Accepted Answer

- **Separate Chaining**: Each hash table slot stores a linked list (or dynamic array) of elements mapping to that index. Load factor $\alpha = n/m$ can exceed 1.
- **Open Addressing**: All elements reside in the hash table itself ($n \le m$). Collisions are resolved via probing sequences. Requires deletion markers (tombstones).

Question 15

Open Addressing Probing Techniques

Accepted Answer

1. **Linear Probing**: $h(k, i) = (h'(k) + i) \pmod m$. Subject to *primary clustering*.
2. **Quadratic Probing**: $h(k, i) = (h'(k) + c_1 i + c_2 i^2) \pmod m$. Subject to *secondary clustering*.
3. **Double Hashing**: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod m$. Eliminates primary and secondary clustering.

Question 16

Binary Heap Indexing & Properties

Accepted Answer

A complete binary tree implemented in a continuous array indexed from `0` to `n-1`:
- **Parent**: `floor((i - 1) / 2)`
- **Left Child**: `2i + 1`
- **Right Child**: `2i + 2`
- **Max-Heap Property**: `A[parent(i)] >= A[i]`
- **Height**: $\lfloor \log_2 n \rfloor$

Question 17

Adjacency Matrix vs Adjacency List

Accepted Answer

| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| **Space Complexity** | $O(V^2)$ | $O(V + E)$ |
| **Edge Lookup** `(u, v)` | $O(1)$ | $O(	ext{degree}(u))$ |
| **Find Neighbors** | $O(V)$ | $O(	ext{degree}(u))$ |
| **Best Used For** | Dense graphs ($E \approx V^2$) | Sparse graphs ($E \ll V^2$) |

Question 18

Topological Sort & Kahn's Algorithm

Accepted Answer

Linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge $u 	o v$, $u$ comes before $v$.

**Kahn's Algorithm (BFS-based)**:
1. Compute in-degree for all vertices.
2. Enqueue all vertices with `in-degree == 0`.
3. Dequeue $u$, append to order, and decrement in-degree of $u$'s neighbors.
4. Repeat until queue is empty. Time complexity: $O(V + E)$.

Question 19

Strongly Connected Components (SCC)

Accepted Answer

A maximal subgraph of a directed graph where every vertex is reachable from every other vertex in the subgraph.

- **Kosaraju's Algorithm**: $O(V + E)$ using 2 DFS passes (one on graph $G$, one on transposed graph $G^T$).
- **Tarjan's Algorithm**: $O(V + E)$ using a single DFS pass with low-link values and a stack.

Question 20

Tree Traversals: In-order, Pre-order, Post-order

Accepted Answer

- **Pre-order** (Root, Left, Right): Useful for copying/cloning a tree structure.
- **In-order** (Left, Root, Right): Yields keys in sorted order for a Binary Search Tree (BST).
- **Post-order** (Left, Right, Root): Useful for bottom-up evaluations (e.g., deleting nodes or expression tree evaluations).

COMP9024 - Data Structures & Algorithms (UNSW)

Cards in this deck

Related Flashcard Sets

MONASH MTH2010 - Multivariable Calculus & Vector Calculus

SYDNEY CHEM1111 - Chemical Bonding, Thermochemistry & Chemical Equilibrium

GCP Associate Cloud Engineer - Cloud IAM, Compute Engine & Networking

JLPT N4 - Intermediate Japanese Grammar, Particles & High-Frequency Kanji