LN5 Divide-and conquer

Question 1

What is the goal of the Sequence Comparison problem in dynamic programming?

Answer 1

To transform one sequence A into another sequence B with the minimum number of edit operations.

Question 2

Define OPT(i, j) in the context of sequence comparison.

Answer 2

OPT(i, j) represents the minimum number of edit steps required to transform the prefix A[1 … i] into B[1 … j].

Question 3

What are the three cases for defining OPT(i, j) in sequence comparison?

Answer 3

1. Align last characters: Align a_i and b_j and add mismatch cost delta_ij.
2. Delete last character of A: Align A[1 … i-1] with B[1 … j] and add a deletion cost.
3. Insert last character of B: Align A[1 … i] with B[1 … j-1] and add an insertion cost.

Question 4

What is the recursive formula for OPT(i, j) in sequence comparison?

Answer 4

OPT(i, j) = min{OPT(i-1, j-1) + delta_ij, OPT(i-1, j) + 1, OPT(i, j-1) + 1}.

Question 5

How is delta_ij defined in the sequence comparison problem?

Answer 5

delta_ij equals 1 if a_i does not equal b_j (mismatch), and 0 if a_i equals b_j (match).

Question 6

What is the time complexity of solving the sequence comparison problem with dynamic programming?

Answer 6

O(n * m), where n and m are the lengths of sequences A and B.

Question 7

Why is backtracking useful in dynamic programming solutions for sequence comparison?

Answer 7

Backtracking from OPT(n, m) helps reconstruct the optimal sequence alignment by tracing the choices that minimized edit distance.

Question 8

For sequences “BOOK” and “BACK,” manually compute the edit distance matrix for practice.

Answer 8

Use the recursive formula and initialize with OPT(i, 0) = i and OPT(0, j) = j. Fill out the matrix row by row, using the three cases at each step.

Question 9

What is the divide-and-conquer strategy?

Answer 9

It is a problem-solving approach that divides a problem into smaller, independent subproblems, solves them recursively, and then combines their solutions.

Question 10

Differentiate between dynamic programming and divide-and-conquer approaches.

Answer 10

Dynamic programming solves overlapping subproblems with memoization to avoid redundant work. Divide-and-conquer splits problems into independent subproblems and does not reuse subproblem solutions.

Question 11

What is the basic recurrence relation for divide-and-conquer time complexity analysis?

Answer 11

T(n) = 2T(n/2) + O(n), which often simplifies to T(n) = O(n log n) for problems like mergesort and the skyline problem.

Question 12

Explain how binary search applies divide-and-conquer principles.

Answer 12

Binary search divides a sorted array in half with each comparison, recursively reducing the search space by half until the element is found or the array cannot be divided further.

Question 13

If you have an unsorted array of integers, why can’t binary search be applied directly?

Answer 13

Binary search relies on a sorted array, allowing comparisons to eliminate half of the remaining elements. In an unsorted array, binary search is ineffective because there is no guaranteed order.

Question 14

What is the skyline problem in algorithm design?

Answer 14

Given n rectangles representing buildings, the skyline problem involves computing the upper contour (or union) of these rectangles from a front view.

Question 15

Describe the naive approach for solving the skyline problem and its complexity.

Answer 15

The naive approach inserts each rectangle individually into an evolving skyline, with an O(n^2) complexity due to repeated updates.

Question 16

How does divide-and-conquer improve the efficiency of solving the skyline problem?

Answer 16

By dividing the set of rectangles into two halves, solving for each half, and merging the results, the problem can be solved in O(n log n) time.

Question 17

What is the merge phase in the divide-and-conquer solution to the skyline problem?

Answer 17

The merge phase combines two skylines by scanning from left to right and keeping the higher contour at each position.

Question 18

Outline the merge steps for two skyline arrays: [2, 5, 7] and [4, 6, 8].

Answer 18

Iterate through both arrays, keeping the higher value at each point. For ties, use the highest point from both arrays.

Question 19

Why are recurrence relations essential for analyzing divide-and-conquer algorithms?

Answer 19

Recurrence relations express the time complexity of recursive calls, helping us understand the total complexity of divide-and-conquer solutions.

Question 20

What is the solution to the recurrence T(n) = T(n/2) + O(1)?

Answer 20

T(n) = O(log n), applicable to binary search and similar logarithmic time complexity algorithms.

Question 21

How is T(n) = 2T(n/2) + O(n) solved, and what does it represent in algorithm analysis?

Answer 21

T(n) = O(n log n), typical for mergesort and skyline problem algorithms.

Question 22

Why is it sometimes beneficial to defer decisions in dynamic programming, as noted in the sequence comparison paradox?

Answer 22

Deferring decisions reduces unnecessary complexity by leaving alignment positions open until the global minimum edit distance is calculated.

Question 23

What optimization can be made to the DP matrix in sequence comparison when sequences are similar?

Answer 23

Compute only entries close to the main diagonal, as the optimal path likely follows the region with minimal values, reducing unnecessary calculations.

Question 24

Create the recurrence relation and solve it for an algorithm that splits a problem into three parts, each half the size, plus O(n) merge time.

Answer 24

The recurrence is T(n) = 3T(n/2) + O(n), which has a solution T(n) = O(n^{log_2 3}) approximately O(n^{1.585}).