FIT2004 - Algorithms & Data Structures (Monash) Flashcards

Question 1

Dynamic Programming: Key Properties

Accepted Answer

What two key properties must a problem exhibit to be solvable using Dynamic Programming?

1. **Optimal Substructure**: An optimal solution to the problem contains optimal solutions to its subproblems.
2. **Overlapping Subproblems**: A recursive algorithm revisits the same subproblems repeatedly rather than generating new ones.

Question 2

Top-Down vs. Bottom-Up Dynamic Programming

Accepted Answer

Compare Top-Down (Memoization) and Bottom-Up (Tabulation) DP approaches:

- **Top-Down (Memoization)**: Uses recursion and caches subproblem results in a lookup table (array/hash map) to avoid recomputation.
- **Bottom-Up (Tabulation)**: Uses iteration to fill a lookup table starting from the smallest base cases up to the desired result, avoiding recursion stack overhead.

Question 3

Greedy Choice Property & Exchange Argument

Accepted Answer

What is the Greedy Choice Property and how is it typically proven?

- **Greedy Choice Property**: A locally optimal choice leads to a globally optimal solution.
- **Exchange Argument**: A proof technique where you assume an optimal non-greedy solution exists, then systematically modify (exchange) its choices with greedy choices without decreasing solution quality, proving the greedy solution is also optimal.

Question 4

Huffman Coding Complexity & Strategy

Accepted Answer

How does Huffman Coding work and what is its time complexity?

- **Strategy**: Constructs an optimal prefix code for data compression using a greedy approach by repeatedly merging the two lowest-frequency nodes.
- **Complexity**: $O(N \log N)$ using a Min-Heap/Priority Queue, where $N$ is the alphabet size.

Question 5

Trie (Prefix Tree) Operations Complexity

Accepted Answer

What is a Trie and what are its search, insertion, and prefix matching time complexities?

- **Definition**: A tree structure where nodes represent characters along shared prefixes of keys.
- **Complexity**: $O(L)$ time for search, insertion, and prefix search, where $L$ is the length of the string, independent of the total number of keys $N$ stored in the Trie.

Question 6

KMP Algorithm: Failure Function (\pi Array)

Accepted Answer

What is the Failure Function ($\pi$ array or Lookup Table) in the Knuth-Morris-Pratt (KMP) string matching algorithm?

- **Definition**: $\pi[i]$ stores the length of the longest proper prefix of `P[0..i]` that is also a suffix of `P[0..i]`.
- **Purpose**: Dictates how far to shift the pattern on mismatch without re-evaluating characters in the text already matched.

Question 7

KMP Algorithm Time Complexity

Accepted Answer

What is the overall time complexity of the KMP algorithm for searching a pattern of length $M$ in a text of length $N$?

- **Precomputation**: $O(M)$ to compute the failure function $\pi$.
- **Matching**: $O(N)$ time.
- **Total Complexity**: $O(N + M)$ time and $O(M)$ extra space.

Question 8

Residual Network $G_f$

Accepted Answer

Define a Residual Network $G_f = (V, E_f)$ for a flow network $G=(V,E)$ with flow $f$.

For each edge $(u,v)$ in $G$ with capacity $c(u,v)$ and flow $f(u,v)$:
- **Forward Edge**: $c_f(u,v) = c(u,v) - f(u,v)$ (remaining available capacity).
- **Backward Edge**: $c_f(v,u) = f(u,v)$ (capacity to push back/cancel existing flow).

Question 9

Augmenting Path

Accepted Answer

What is an Augmenting Path in Network Flow?

- A simple directed path from source $s$ to sink $t$ in the residual network $G_f$ where every edge has residual capacity $c_f(u,v) > 0$.
- The maximum flow that can be pushed along path $P$ is bounded by its **bottleneck capacity**: $b = \min_{(u,v) \in P} c_f(u,v)$.

Question 10

Ford-Fulkerson Algorithm Steps

Accepted Answer

Outline the steps of the Ford-Fulkerson algorithm for finding Maximum Flow:

1. Initialize flow $f(u,v) = 0$ for all edges.
2. While an augmenting path $P$ from $s$ to $t$ exists in $G_f$:
   a. Find bottleneck capacity $c_f(P) = \min \{ c_f(u,v) : (u,v) \in P \}$.
   b. Augment flow along $P$ by $c_f(P)$ and update residual capacities in $G_f$.
3. Return total flow into sink $t$.

Question 11

Max-Flow Min-Cut Theorem

Accepted Answer

State the Max-Flow Min-Cut Theorem.

In any network flow graph, the value of the **Maximum Flow** from source $s$ to sink $t$ is equal to the capacity of the **Minimum $s$-$t$ Cut** (the minimum sum of capacities of edges leaving $S$ in any cut $(S, T)$ separating $s \in S$ and $t \in T$).

Question 12

Edmonds-Karp Algorithm & Complexity

Accepted Answer

How does the Edmonds-Karp algorithm improve Ford-Fulkerson, and what is its complexity?

- **Improvement**: Uses **Breadth-First Search (BFS)** to select the shortest augmenting path (fewest edges) in $G_f$.
- **Time Complexity**: $O(V \cdot E^2)$, rendering performance independent of maximum edge capacity values.

Question 13

Master Theorem Formula

Accepted Answer

For recurrence $T(n) = a T(n/b) + f(n)$ with $a \ge 1, b > 1$:

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \ge 0$, then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ and $a f(n/b) \le c f(n)$ for $c < 1$, then $T(n) = \Theta(f(n))$.

Question 14

Suffix Array vs. Suffix Tree

Accepted Answer

Compare Suffix Arrays and Suffix Trees:

- **Suffix Tree**: $O(N)$ construction and space, but high memory overhead due to tree pointers.
- **Suffix Array**: An array of sorted suffix indices. Uses $O(N)$ space with significantly smaller constant factors and footprint; built in $O(N)$ or $O(N \log N)$ time.

Question 15

0/1 Knapsack vs. Fractional Knapsack

Accepted Answer

Why is Fractional Knapsack solvable with a Greedy algorithm while 0/1 Knapsack requires Dynamic Programming?

- **Fractional Knapsack**: Items can be split; picking by highest value-to-weight ratio satisfies the greedy choice property.
- **0/1 Knapsack**: Items cannot be split. Taking a high value/weight item may leave empty space that causes worse overall utility, breaking greedy choice property.

Question 16

LCS (Longest Common Subsequence) Recurrence

Accepted Answer

What is the DP recurrence relation for Longest Common Subsequence of strings $X[1..m]$ and $Y[1..n]$?

$$DP[i, j] = \begin{cases} 0 & 	ext{if } i=0 	ext{ or } j=0 \ DP[i-1, j-1] + 1 & 	ext{if } X[i] == Y[j] \ \max(DP[i-1, j], DP[i, j-1]) & 	ext{if } X[i] 
eq Y[j] \end{cases}$$

Question 17

Divide and Conquer Paradigm

Accepted Answer

Name and describe the 3 core steps of the Divide and Conquer framework.

1. **Divide**: Break the problem into smaller, independent subproblems of the same type.
2. **Conquer**: Recursively solve the subproblems. If base cases are reached, solve them directly.
3. **Combine**: Merge subproblem solutions into the solution for the original problem.

Question 18

Maximum Bipartite Matching via Network Flow

Accepted Answer

How do you solve Maximum Bipartite Matching using Network Flow?

1. Direct edges from set $L$ to set $R$ with capacity 1.
2. Add super-source $s$ with directed edges to all $u \in L$ (capacity 1).
3. Add super-sink $t$ with directed edges from all $v \in R$ to $t$ (capacity 1).
4. Compute max flow; the max flow value equals the size of the maximum matching.

Question 19

Z-Algorithm Concepts & Array

Accepted Answer

What does the $Z$-array store in the Z-algorithm for string matching?

For a string $S$ of length $N$, $Z[i]$ is the length of the longest substring starting from $S[i]$ that is also a prefix of $S$. The algorithm computes all $Z[i]$ in $O(N)$ linear time using previously computed $Z$-box boundaries $[L, R]$.

Question 20

Boyer-Moore Bad Character Rule

Accepted Answer

How does the Bad Character Rule function in the Boyer-Moore string matching algorithm?

Upon mismatch at pattern index $j$ with text character $c$:
- If $c$ exists in pattern, shift pattern to align the rightmost occurrence of $c$ in pattern with text character $c$.
- If $c$ does not exist in pattern, shift pattern past $c$ completely.

FIT2004 - Algorithms & Data Structures (Monash)

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