Problems from the "Theory Problems" section of algo-class.org.
- [Posted March 22nd] You are given as input an unsorted array of n distinct numbers, where n is a power of 2. Give an algorithm that identifies the second-largest number in the array, and that uses at most
- [Posted March 22nd] You are a 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. Give an algorithm to compute the maximum element that runs in O(log n) time.
- [Posted March 22nd] You are given a sorted (from smallest to largest) array A of n 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.
- [Posted March 22nd] Give the best upper bound that you can on the solution to the following recurrence: T(1)=1 and T(n)≤T([n])+1 for
n>1. (Here [x] denotes the "floor" function, which rounds down to the nearest integer.)
- [Posted March 22nd] You are given an n by n grid of 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 n2 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.)