Problem 1

You are given as input an unsorted array of $n$ distinct numbers, where $n$ is a power of $2$. Provide an algorithm that identifies the second largest number in the array, and that uses at most $n + \lg{(n)} - 2$ comparisons.

Problem 2

You are given a unimodal array of $n$ distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Provide an algorithm to compute the maximum element that runs in $O(\log(n))$ time.

Problem 3

You are given a sorted (from smallest to largest) array $A$ of $n$ distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index $i$ such that $A_{i} = i$. Design the fastest algorithm that you can for solving this problem.

Problem 4

Give the best upper bound that you can on the solution to the following recurrence:

$$T(1) = 1, \qquad T(n) \leq T([\sqrt{n}]) + 1, \qquad n > 1$$

(Here $[x]$ denotes the "floor" function, which rounds down to the nearest integer.)

Problem 5

You are given an $n \times n$ grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only $O(n)$ comparisons between pairs of numbers. (Note: since there are $n^{2}$ numbers in the input, you cannot afford to look at all of them. Hint: think about what types of recurrences would give you the desired upper bound.)

M.E. Irizarry-Gelpí

Algorithm Theory Problems (Week 1)

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5