Jheel Patel | Cloud Systems & Software Engineer

Problem 3.1

This problem asks to find the asymptotic running time of fast exponentiation algorithm, assuming each multiplication and division can be performed in constant time.

Solution

The fast exponentiation algorithm works by repeatedly squaring the base and reducing the exponent by half at each step. The key observation is that the number of times we can halve the exponent before it reaches zero is logarithmic in relation to the size of the exponent. Thus, the running time of the fast exponentiation algorithm is $O(\log b)$ , where $b$ is the exponent.

Problem 3.2

It asks for an algorithm to find the maximum element in an unimodal array which takes $O(\log n)$ time, where $n$ is the size of the array.

Solution

We can use divide-and-conquer approach here.
Divide array into left and right subarray, $L$ and $R$ respectively, preserving the order. By the definition of unimodal array, if max element is in $L$ then, $L[-1] > \forall x \in R$ (given distint elements constraint). Similarly, if max element is in $R$ then, $R[0] > \forall x \in L$ .
Thus, we can compare the last element of $L$ and first element of $R$ to determine which subarray contains the maximum element. We can then recursively apply the same logic to the chosen subarray until we find the maximum element.

Python Code Implementation:

def find_max_unimodal(arr):
    def find_max(left, right):
        if left == right:
            return arr[left]
        mid = (left + right) // 2
        if arr[mid] > arr[mid + 1]:
            return find_max(left, mid)
        else:
            return find_max(mid + 1, right)
    return find_max(0, len(arr) - 1)

The time complexity of this algorithm is $O(\log n)$ , as we are halving the search space at each step.

Problem 3.3

In this problem we are given a sorted array with distinct integers, and we need to find an index $i$ such that $A[i] = i$ in $O(\log n)$ time. Elements can be negative, possitve or zero.

Solution

We can use a modified binary search approach here.
At each step, we compare the middle element $A[mid]$ $A [mi d]$ with its index $mid$ $mi d$ .
- If $A[mid] == mid$ , we have found the index and return it.
- If $A[mid] > mid$ , then the desired index must be in the left subarray, since all elements to the right will be greater than their indices (due to the distinctness and sorted property).
- If $A[mid] < mid$ , then the desired index must be in the right subarray.
We continue this process recursively until we find the index or exhaust the search space.

Python Code Implementation:

def find_index_equal_value(arr):
    def binary_search(left, right):
        if left > right:
            return -1  # Not found
        mid = (left + right) // 2
        # distinct elements guarantee unambiguity
        if arr[mid] == mid:
            return mid
        elif arr[mid] > mid:
            return binary_search(left, mid - 1)
        else:
            return binary_search(mid + 1, right)
    return binary_search(0, len(arr) - 1)

The time complexity of this algorithm is $O(\log n)$ , as we are halving the search space at each step.

Problem 3.4

In this problem we are asked to find a local minimum in an $n \times n$ grid of distinct numbers with only $O(n)$ comparisons.

Solution

We can use hill climbing approach here (analogous to gradient descent in continuous environments). As all values are distinct we can assume there are no valleys and atleast one minimum is guaranteed to be present (this can be proved easily given the definite value of $n$ ).
In naive approach, we can start from a cell and jump to the smallest neighboring cell. Repeat this until we reach a local minimum at which point all the neighboring cells will be larger than the current cell.
Worst case time complexity of the naive approach is $O(n^2)$ . Example, imagine zig-zag shaped decreasing numbers.
To improve the time complexity, we can use divide-and-conquer approach.
Motivation: If we divide the grid into 4 quadrants of $\frac{n}{2} \times \frac{n}{2}$ grid size, a local mimimum can be found in one of the quadrants. Once we know in which quadrant a local minimum can be found, we can recurse on the quadrant grid using that same process until base case is reached.
Dividing the quandrant in half (in each dimension) in each recursion implies there will be approximately $\log_2 n$ recursive calls in worst case.
Hence, in each recursion we need to do $O(n)$ work to achieve $O(n\log n)$ time complexity.
We can use something similar to mean value theorem to select a quadrant to recurse in each recursion.
1. Given the grid of size $n \times n$ , find minimum element from the elements in row $\frac{n}{2}$ and column $\frac{n}{2}$ (clearly this row and column divides the grid into 4 quadrants). As all values are distinct we are guaranteed to find a unique mimimum. Here we do $O(n)$ comparisons.
2. Then check the neighbours of this minimum element. If the minimum is smaller than all its neighbours then we have found our local minimum. Here we do $O(1)$ comparisons.
3. If any of the neighbours are smaller than the above selected element, then the quadrant of the smallest neighbor is selected for further recurson.
4. Base case: In the base case of grid of size $1 \times 1$ , the single element of the grid is our local minimum. The proof is evident from the above selection criteria of the quadrant.
Now we need to prove that the quadrant chosen using the above method for recursion is guaranteed to contain a local minimum.
- Let the minimum element found in step 1 be $M$ .
- If $M$ is smaller than all its neighbors, we are done.
- Otherwise, let’s say one of its neighbors, say $N$ , is smaller than $M$ .
- Since all elements are distinct, $N$ must be less than $M$ .
- Now, consider the quadrant that contains $N$ . Since $N$ is less than $M$ , and $M$ was the minimum in its row and column, it follows that there must be a local minimum in the quadrant containing $N$ . This is because if we keep moving in the direction of decreasing values, we will eventually reach a point where all neighboring values are greater (a local minimum). This is similar to the naive approach but we are narrowing down our search space by jumping to the point near a local minimum.
It takes $O(\frac{n}{2^k})$ comparisons in $k^{th}$ recursion where $k$ starts from $0$ . Hence total comparisons will be: $O(n) + O(\frac{n}{2}) + O(\frac{n}{4}) + ... = O(n) \sum_{i=0}^{\log n} \frac{1}{2^i} = O(n)$

Python Code Implementation:

def find_local_minimum(grid):
    n = len(grid)
    quadrant = [(0, n - 1, 0, n - 1)]  # (row_start, row_end, col_start, col_end)

    def get_neighbors(i, j):
        neighbors = []
        if i > 0:
            neighbors.append((i - 1, j))
        if i < n - 1:
            neighbors.append((i + 1, j))
        if j > 0:
            neighbors.append((i, j - 1))
        if j < n - 1:
            neighbors.append((i, j + 1))
        return neighbors
    
    def find_min_in_cross(row_start, row_end, col_start, col_end):
        min_val = float('inf')
        min_pos = (-1, -1)
        mid_row = (row_start + row_end) // 2
        mid_col = (col_start + col_end) // 2
        
        for j in range(col_start, col_end + 1):
            if grid[mid_row][j] < min_val:
                min_val = grid[mid_row][j]
                min_pos = (mid_row, j)
        
        for i in range(row_start, row_end + 1):
            if grid[i][mid_col] < min_val:
                min_val = grid[i][mid_col]
                min_pos = (i, mid_col)
        
        return min_pos
    
    def search(row_start, row_end, col_start, col_end):
        if row_start == row_end and col_start == col_end:
            return (row_start, col_start)
        
        mid_row = (row_start + row_end) // 2
        mid_col = (col_start + col_end) // 2

        min_i, min_j = find_min_in_cross(row_start, row_end, col_start, col_end)

        neighbors = get_neighbors(min_i, min_j)
        smallest_neighbor = (min_i, min_j)
        for ni, nj in neighbors:
            if grid[ni][nj] < grid[smallest_neighbor[0]][smallest_neighbor[1]]:
                smallest_neighbor = (ni, nj)
        
        if smallest_neighbor == (min_i, min_j):
            return (min_i, min_j)
        else:
            if smallest_neighbor[0] <= mid_row and smallest_neighbor[1] <= mid_col:
                return search(row_start, mid_row, col_start, mid_col)
            elif smallest_neighbor[0] <= mid_row and smallest_neighbor[1] > mid_col:
                return search(row_start, mid_row, mid_col + 1, col_end)
            elif smallest_neighbor[0] > mid_row and smallest_neighbor[1] <= mid_col:
                return search(mid_row + 1, row_end, col_start, mid_col)
            else:
                return search(mid_row + 1, row_end, mid_col + 1, col_end)

    return search(0, n - 1, 0, n - 1)

# Example usage:
# Distinct elements grid
grid = [
    [20, 8, 21, 23],
    [14, 13, 12, 11],
    [15, 9, 8, 7],
    [16, 17, 18, 19]
]
local_min_pos = find_local_minimum(grid)
print(f"Local minimum found at position: {local_min_pos} with value: {grid[local_min_pos[0]][local_min_pos[1]]}")