An n times n grid is a graph whose node set is the set of all ordered pairs of n

Question

An n times n grid is a graph whose node set is the set of all ordered pairs of natural numbers (i, j) with 1 lessthanorequalto i lessthanorequalto n and 1 lessthanorequalto j lessthanorequalto n; the nodes (i, j) and (k, l) are joined by an edge if and only if |i - k| + |j - l| = 1. In other words, it is the adjacency graph of an n times n chessboard. In this problem, you are given a grid with each node v labeled by a distinct number X_upsilon. upsilon is called a local minimum if is smaller than the labels of each of upsilon's neighbors. Develop a divide and conquer algorithm for finding any local minimum in the grid that runs in O(n) time. (Recall that the number of nodes in the grid is n^2.) Describe your algorithm succinctly but precisely. Prove its correctness. Analyze its running time.

Explanation / Answer

1. At each iteration in addition to the grid itself we keep track of current minimum candidate (in the initial state we

can say minimum candidate is plus infinity).

2. We calculate minimum of middle row and column and compare it to minimum candidate. If the latter is smaller

we recurse into the quadrant containing minimum candidate.

3. Otherwise we forget previous candidate and only then check whether new middle row/column minimum is

actually a local minimum. And if not then recurse as usual to whatever quadrant we slope down from it (and track

new minimum candidate).

This algorithm takes time 2n + 2n/2 + 2n/4 + ..., which equals 4n, which is O(n)

Also we can find the local minima by following algorithm

1) Divide the n x n matrix into four n/2 x n/2 sub matrices.

2) Keep dividing the sub matrices recursively until you end up with a 2 x 2 matrix

3) Check if any element of 2 x 2 matrix is a local Minimum.

Recurrence equation is : T(n) = 4*T(n/2) + O(1)

4*T(n/2) for 4 n/2 x n/2 sub matrices and O(1) for checking if 2 x 2 sub matrix has a local minimum

Master theorem says this is a O(n^2) worst case bound.

But, we can get a best case O(n) bound, if we exit the recursion stack after we have have found a local minimum in step 3.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.