Divide and Conquer & Recurrences Cheat Sheet
Maximum Subarray Sum Problem (1D):
– **Problem**: Given an array \( A \) of size \( n \), find the subarray with the maximum sum.
– **Definitions**:
– **Max Subarray Sum**: \( \text{max}_{l, u} \sum_{j=l}^{u} A[j] \)
– **Max Prefix Sum**: \( \text{max}_{u} \sum_{j=0}^{u} A[j] \)
– **Max Suffix Sum**: \( \text{max}_{l} \sum_{j=l}^{n-1} A[j] \)
– **Algorithm (Divide and Conquer)
**:
1. Divide array into two halves.
2. Recursively compute max subarray for the left and right halves.
3. Combine step: Compute max suffix for the left and max prefix for the right. Combine to get cross sum.
4. Return \( \text{max}(\text{ml}, \text{mr}, \text{suffl} + \text{prefr}) \).
– **Time Complexity**: Original \( O(n \log n) \); optimized linear \( O(n) \).
#### **Solution for Max Subarray Sum (Linear Time)**:
1. Use the following expressions:
– \( \text{pref} = \max(\text{pref}_l, s_l + \text{pref}_r) \)
– \( \text{suff} = \max(s_r + \text{suff}_l, \text{suff}_r) \)
2. Track total sums and use divide-and-conquer strategy for \( O(n) \) solution.
### **Maximum Submatrix Sum Problem (2D)**:
– **Problem**: Given a matrix \( A \) of size \( n \times n \), find the rectangular submatrix with the maximum sum.
– **Key Idea**: Reduce 2D problem to 1D by “squishing” rows:
– **Squish** array \( \text{squish}(A, r1, r2)[i] = \sum_{j=r1}^{r2} A[i, j] \).
– Use Kadane’s algorithm on each squished array to find the max subarray sum for every pair of rows.
– **Algorithm**:
1. For each pair of rows \( r1 \leq r2 \), squish the matrix.
2. Apply Kadane’s algorithm to the squished array to find the maximum subarray sum.
3. Track the global maximum sum.
– **Time Complexity**: \( O(n^3) \).
#### **Solution for Maximum Submatrix Sum (O(n^3))**:
1. Compute squished array \( \text{squish}(A, r1, r2) \).
2. Run **Kadane’s algorithm** on squish arrays for max subarray sum for every pair of rows.
### **
Master Theorem for Divide and Conquer Recurrences*
*
The **Master Theorem** solves recurrences of the form:
\[
T(n) = aT\left(\frac{n}{b}\right) + f(n)
\]
Where:
– \( a \geq 1 \), \( b > 1 \), and \( f(n) \) is an asymptotically positive function.
### **Cases**:
1. **Case 1 (Polynomially smaller work at leaves)**:
If \( f(n) = O(n^d) \) where \( d < \log_b a \), then:
\[
T(n) = \Theta(n^{\log_b a})
\]
**Case 2 (Equal work at all levels)**: If \( f(n) = \Theta(n^d) \) where \( d = \log_b a \), then:
\[
T(n) = \Theta(n^d \log n)
\]
3. **Case 3 (More work done at the root)**:
If \( f(n) = \Omega(n^d) \) where \( d > \log_b a \), and if \( a f(n/b) \leq c f(n) \) for some constant \( c < 1 \) and sufficiently large \( n \), then:
\[
T(n) = \Theta(f(n))
\]
#### **Example Applications**:
– **\( T(n) = 2T(n/2) + n \)**:
– Here, \( a = 2 \), \( b = 2 \), \( f(n) = n \), and \( \log_b a = 1 \). Since \( d = 1 \), we are in Case 2.
– Solution: \( T(n) = \Theta(n \log n) \).
– **\( T(n) = T(n/2) + n \)**:
– Here, \( a = 1 \), \( b = 2 \), \( f(n) = n \), and \( \log_b a = 0 \). Since \( d = 1 \), we are in Case 3.
– Solution: \( T(n) = \Theta(n) \).
### **Recursion Tree Expansion Method**:
– **Recursion Tree**: Visualize the recurrence as a tree.
– **Steps**:
1. Compute work done at each level.
2. Sum the work across all levels to get the total time complexity.
#### **Recurrence Examples**:
– \( T(n) = 2T(n/4) + \sqrt{n} \):
– Solution: \( \Theta(\sqrt{n} \log n) \).
– \( T(n) = T(n/3) + n^3 \):
– Solution: \( \Theta(n^3) \).
– \( T(n) = 7T(n/2) + n^2 \):
– Solution: \( \Theta(n^{\log_2 7}) \).
### **
Euclidean Algorithm and Continued Fractions**
#### **Euclidean Algorithm**:
– Computes the greatest common divisor (GCD) of two numbers \( a \) and \( b \):
\[
\text{gcd}(a, b) = \text{gcd}(b, a \% b)
\]
– Time Complexity: \( O(\log(\min(a, b))) \).
#### **Continued Fractions**:
– **Definition**: Representation of a rational number as:
\[
\frac{a}{b} = 1 / (a_1 + 1 / (a_2 + 1 / (a_3 + \dots)))
\]
– **Algorithm**: Repeatedly divide and take the remainder to get the sequence \( [a_1, a_2, \dots, a_n] \).
– **Key Functions**:
1. Convert a rational number \( \frac{a}{b} \) into a continued fraction.
2. Convert a continued fraction back into a rational number.
### **Subarray and Submatrix Query Problems**
#### **Subarray Sum Query**:
– **Goal**: Given indices \( l \) and \( u \), compute the sum of all entries in subarray \( A[l, u] \).
– **Preprocessing**:
– **Prefix Sum Array**: Store cumulative sums up to index \( i \) in a new array \( B \).
– Query time: \( O(1) \) by computing \( B[u] – B[l-1] \).
#### **Subarray Maximum Query**:
– **Goal**: Given indices \( l \) and \( u \), compute the maximum element in the subarray \( A[l, u] \).
– **Sparse Table**:
– Preprocess array to build table \( C \) where \( C[i, j] \) stores the maximum value in the range \( [i, i + 2^j – 1] \).
– Query time: \( O(1) \) by looking up two precomputed values.
### **Kadane’s Algorithm (Max Subarray Sum)**:
– **Problem**: Find the contiguous subarray with the maximum sum in a 1D array.
– **Algorithm**:
1. Initialize two variables: `max_so_far` and `max_ending_here`.
2. Traverse the array:
– \( \text{max\_ending\_here} = \max(A[i], \text{max\_ending\_here} + A[i]) \)
– \( \text{max\_so\_far} = \max(\text{max\_so\_far}, \text{max\_ending\_here}) \)
– **Time Complexity**: \( O(n) \).
#### **Kadane’s Algorithm Applied in 2D**:
– Squish each submatrix to convert it into a 1D array.
– Use Kadane’s algorithm to solve the maximum subarray problem for that submatrix.
### **Additional Exam Tips**:
1. **Master Recurrences**: Be proficient in solving recurrences with the Master Theorem and recursion tree methods.
2. **Understand Divide
and Conquer**: Pay attention to combining solutions for subproblems efficiently.
3. **Algorithm Time Complexities**: Memorize time complexities for standard algorithms (Euclidean Algorithm, Kadane’s Algorithm, divide and conquer algorithms).
4. **Sparse Table Queries**: Understand how to preprocess arrays for fast range queries, both sum and max.
This cheat sheet should cover all key topics, formulas, algorithms, and problem solutions you need for the exam. Make sure to practice these problems and revise the concepts for maximum efficiency. Good luck!