Given an element with index $i$ in the array$-$representation of a heap, which of the following correctly computes the index of the left child of that element?

a$.\frac{i+1}{2}$

b$.2**i$

c$.(i+1)\%2$

d$.2**i+1$

e$.2**i+2$

What is the running$-$time $($as a tight big$-$O bound$)$ of restoring the heap$-$order of a heap after a deleteMax operation?

a$.O(1)$

b$.O(logN)$

c$.O(N)$

d$.O(NlogN)$

e$.O(N^2)$

For the interval scheduling problem, which greedy paradigm produces an optimal solution?

a$.$ the shortest jobs

b$.$ the job with the fewest conflicts

c$.$ the job with the earliest starting time

d$.$ the job with the earliest ending time

e$.$ none of the above

What is the best$-$case running time $($as a tight big$-$O bound$)$ for quicksort to sort an array of $n$ elements?

a$.O(logn)$

b$.O(n)$

c$.O(nlogn)$

d$.O(n^2)$

e$.O(n^{2}logn)$

Merge Sort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

a$.$ The array elements form a heap.

b$.$ Elements in each half of the array are sorted amongst themselves.

c$.$ Elements in the first half of the array are less than or equal to elements in the second half of the array.

d$.$ Both $($a$)$ and $($b$)$ are true.

d$.$ None of the above.

Suppose you have coins of denominations $1,3$ and $4.$ You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?

a$.20$

b$.12$

c$.6$

d$.5$

e$.7$

Median of three quick sort is an in$-$place sort.

ALWAYS

SOMETIMES

NEVER

For the fractional knapsack problem, being greedy on the item with the smallest weight yields an optimal solution.

ALWAYS

SOMETIMES

NEVER