THINK FIRST·CODE LATER
Let n be the number of elements from index i to the end of the array. Which recurrence describes the running time of this method?
static int countNeg(int[] a, int i) {
if (i == a.length) return 0;
int rest = countNeg(a, i + 1);
return (a[i] < 0 ? 1 : 0) + rest;
}
A recursive method does constant work and then calls itself once on half of its input. What is its running time?
Which is the solution of T(n) = 2T(n/2) + cn, T(1) = c?
What does this program print?
public class Calls {
static int calls = 0;
static void f(int n) {
calls++;
if (n <= 0) return;
f(n - 1);
f(n - 1);
}
public static void main(String[] args) {
f(4);
System.out.println(calls);
}
}
The Towers of Hanoi move count satisfies M(n) = 2M(n − 1) + 1 with M(1) = 1. How many moves are needed for 10 discs?
Solve T(n) = T(n − 1) + n with T(0) = 0.
Solve T(n) = T(n/2) + n with T(1) = 1.
Use the Master theorem to solve T(n) = 4T(n/2) + n.
Use the Master theorem to solve T(n) = 8T(n/2) + n³.
Use the Master theorem to solve T(n) = 3T(n/4) + n².
To which recurrence can the Master theorem (T(n) = aT(n/b) + f(n)) not be applied directly?
In the recursion tree of T(n) = 3T(n/2) + n (n a power of 2), how many leaves (calls of size 1) are there?
What does this program print?
public class Work {
static int count = 0;
static void g(int n) {
if (n <= 1) return;
for (int i = 0; i < n; i++) count++;
g(n / 2);
g(n / 2);
}
public static void main(String[] args) {
g(8);
System.out.println(count);
}
}
What does this code print?
static int search(int[] a, int key, int lo, int hi) {
if (lo > hi) return -1;
int mid = (lo + hi) / 2;
System.out.print(a[mid] + " ");
if (a[mid] == key) return mid;
if (key < a[mid]) return search(a, key, lo, mid - 1);
return search(a, key, mid + 1, hi);
}
// in main:
int[] a = {3, 7, 11, 15, 19, 24, 30, 36, 41};
System.out.println(search(a, 31, 0, a.length - 1));
What happens when find(new int[]{1, 3, 5}, 0, 0, 2) is called?
static int find(int[] a, int key, int lo, int hi) {
if (lo > hi) return -1;
int mid = (lo + hi) / 2;
if (a[mid] == key) return mid;
if (key < a[mid]) return find(a, key, lo, mid);
return find(a, key, mid + 1, hi);
}
In merge sort, which step of the divide-and-conquer pattern does most of the non-recursive work?
How many times is comparisons++ executed by merge(new int[]{1, 4, 7}, new int[]{2, 3, 9})?
static int comparisons = 0;
static int[] merge(int[] l, int[] r) {
int[] out = new int[l.length + r.length];
int i = 0, j = 0, k = 0;
while (i < l.length && j < r.length) {
comparisons++;
if (l[i] <= r[j]) out[k++] = l[i++];
else out[k++] = r[j++];
}
while (i < l.length) out[k++] = l[i++];
while (j < r.length) out[k++] = r[j++];
return out;
}
How many inversions (pairs i < j with a[i] > a[j]) does the array {5, 2, 4, 1, 3} contain?
During the merge-based inversion count, the sorted halves left = {2, 5, 8} and right = {1, 6, 7} are merged. With the rule "when an element of right is copied, add the number of elements still waiting in left", how many split inversions are counted in this merge?
What is the maximum sum of a contiguous, non-empty subarray of {2, -5, 3, 1, -2, 4, -6, 1}?
In the divide-and-conquer maximum-subarray algorithm, why is the whole algorithm Θ(n log n) rather than Θ(n²)?
What does this code print?
int[] a = {4, -6, 3, -1, 5, -9, 2};
int cur = 0, best = Integer.MIN_VALUE;
for (int x : a) {
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
System.out.println(best + " " + cur);
What does this program print?
public class Pow {
static int calls = 0;
static long power(long a, int n) {
calls++;
if (n == 0) return 1;
long half = power(a, n / 2);
if (n % 2 == 0) return half * half;
return a * half * half;
}
public static void main(String[] args) {
long r = power(2, 13);
System.out.println(r + " " + calls);
}
}
A student "simplifies" fast exponentiation to:
static long power(long a, int n) {
if (n == 0) return 1;
if (n % 2 == 0) return power(a, n / 2) * power(a, n / 2);
return a * power(a, n / 2) * power(a, n / 2);
}
What is its running time in terms of n?
Does this method compile?
static int search(int[] a, int key, int lo, int hi) {
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (a[mid] == key) return mid;
else if (key < a[mid]) return search(a, key, lo, mid - 1);
else if (key > a[mid]) return search(a, key, mid + 1, hi);
}
Solve T(n) = T(n − 1) + 2 with T(0) = 1 by iteration. Give the closed form, the value T(10) and the Θ-class.
Draw (or describe) the recursion tree of T(n) = 2T(n/2) + n², and use it to find the running time. Which Master-theorem case confirms your answer?
A divide-and-conquer algorithm splits its input into parts of sizes n/3 and 2n/3 and does linear work to combine: T(n) = T(n/3) + T(2n/3) + n. Explain why the Master theorem cannot be used, and use a recursion tree to find a tight bound.
Describe the divide, conquer and combine steps of the divide-and-conquer maximum-subarray algorithm, give its recurrence and running time, and name the faster algorithm for the same problem.
Write a divide-and-conquer method static int max(int[] a, int lo, int hi) that returns the largest element of the non-empty range a[lo..hi] by splitting the range in two halves. Then give its recurrence and running time.
Write static int countOccurrences(int[] a, int key) for a sorted array that may contain duplicates. It must run in O(log n): use a recursive binary search that finds the first index of key and another that finds the last index. For {1, 2, 2, 2, 5, 7} and key 2 it returns 3; for key 4 it returns 0.