Which is the formal definition of f(n) = O(g(n))?
To prove that 3n² + 10n = O(n²), you must give constants c and n₀ with 3n² + 10n ≤ c · n² for all n ≥ n₀. Which pair works?
What does f(n) = Θ(g(n)) mean?
Which statement is false?
Which list is in increasing order of growth rate?
What is the tightest bound on the running time of this code?
int sum = 0, count = 0, max = a[0];
for (int i = 0; i < n; i++) sum += a[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i] < a[j]) count++;
for (int i = 1; i < n; i++) max = Math.max(max, a[i]);
What does this code print?
int n = 10, count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
count++;
System.out.println(count);
What does this code print, and how does the number of iterations grow?
int m = 100, steps = 0;
while (m > 1) {
m = m / 2;
steps++;
}
System.out.println(steps);
What is the tightest bound on the number of times ops++ runs?
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < n; j++)
ops++;
What is the tightest bound on the number of times ops++ runs?
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < i; j++)
ops++;
What does this code print?
int n = 5, count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
for (int k = 0; k < j; k++)
count++;
System.out.println(count);
Linear search looks for x in an unsorted array of n elements. Which statement is correct?
How much extra space does this method use when called as sum(a, 0) on an array of length n?
static long sum(int[] a, int i) {
if (i == a.length) return 0;
return a[i] + sum(a, i + 1);
}
A dynamic array grows by 10 slots (capacity + 10) each time it is full, copying all elements. What is the amortized cost of one append over n appends?
This simulation starts with capacity 1 and doubles it whenever the array is full. What does it print?
int capacity = 1, size = 0, copies = 0;
for (int k = 0; k < 9; k++) {
if (size == capacity) {
copies += size;
capacity *= 2;
}
size++;
}
System.out.println(copies + " " + capacity);
Which is a correct loop invariant for this loop, checked each time the condition i < a.length is evaluated?
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) max = a[i];
}
In a loop-invariant proof, which step combines the invariant with the loop's exit condition to conclude that the result is correct?
Which invariant justifies the standard binary search on a sorted array (while (lo <= hi), lo = mid + 1 or hi = mid - 1)?
This binary search has a bug. With int[] a = {2, 4, 6, 8};, which call never terminates?
static int search(int[] a, int t) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] == t) return mid;
if (a[mid] < t) lo = mid; else hi = mid - 1;
}
return -1;
}
In the worst case, how many iterations of the while loop does a correct binary search (lo <= hi, mid + 1 / mid - 1) perform on a sorted array of 1000 elements?
Why do we compare algorithms by counting basic operations rather than by measuring running time in seconds?
A Θ(n²) algorithm takes 3 seconds for n = 1000. Roughly how long do you expect it to take for n = 4000?
Which assumption belongs to the RAM model used for analysing algorithms?
What is the tightest bound on the running time of this method, counting characters copied?
static String stars(int n) {
String s = "";
for (int i = 0; i < n; i++) {
s += "*";
}
return s;
}
list is an ArrayList<Integer> with n elements. What is the tightest bound on the running time of this loop?
while (!list.isEmpty()) {
list.remove(0);
}
(a) Prove from the definition that 5n + 3 = O(n) by giving explicit constants c and n₀. (b) Prove that n² is not O(n).
The loop below computes the sum of an array. State a loop invariant and prove the loop correct with the three steps (initialisation, maintenance, termination).
long s = 0;
int i = 0;
while (i < a.length) {
s += a[i];
i++;
}
Using the accounting method, explain why appending n elements to a dynamic array that doubles its capacity when full costs O(1) amortized per append. Say how many credits you charge per append and why they are always enough.
A student times two sorting methods on an array of 200 random numbers and concludes that method X (Θ(n²)) is faster than method Y (Θ(n log n)) "in general". Give three reasons why this experiment can mislead, and describe a better experiment.
Write a method
static long maxWindowSum(int[] a, int k)
that returns the largest sum of k consecutive elements of a (1 ≤ k ≤ a.length). The obvious solution recomputes each window and is Θ(n · k); yours must run in Θ(n). Example: {4, -1, 2, 7, -3, 5}, k = 3 → 9 (the window 7, -3, 5).
Write a method
static int countLess(int[] sorted, int x)
that returns how many elements of the ascending array sorted are strictly less than x, in Θ(log n) time. Duplicates are allowed. State the loop invariant you rely on. Example: {1, 3, 3, 3, 8}, x = 3 → 1; x = 9 → 5.