**Practice
Questions**

1. Suppose
B(n) and W(n) are respectively the best case and worst case running times for
an algorithm on an input of size n. Which of these statements MUST be true?

A. B(n) is Ο(W(n))

B. B(n) is Θ(W(n))

C. W(n) is Ο(B(n))

D. W(n) is Θ(B(n))

2. The input
for an algorithm is an array of size n and the answer is a single integer. The
algorithm uses a divide-and-conquer strategy that takes Ο(n) steps to
first split the array into 3 sub-arrays, each of which is half the size of the
original array. Next, it recursively solves the problem for the 3 sub-arrays,
and returns the smallest of these answers as the overall answer. If the running
time of the algorithm for an array of size n is T(n), which of the following
recurrences could T(n) satisfy?

A. T(n) = min{T(2n/3), Ο(n)}

B. T(n) = 2T(n/3) + Ο(n)

C. T(n) = 3T(n/2) + Ο(n)

D. T(n) = T(3n/2) + Ο(n)

3. Suppose
a[1..n] is an array of distinct integers and n >= 2. The following code
should return true if the array a[1..n] is sorted in increasing order and return
false otherwise, but it is INCORRECT:

1: checkSorted(a[1..n]):

2: count = 0

3: for i = 1 to n-1:

4: if a[i] < a[i+1]:

5: count = count + 1

6: if count == n:

7: return true

8: return false

Which of
the following changes will FIX the code:

A. change Line 2 to count
= 1

B. change Line 3 to for
i = 1 to n:

C. change Line 4 to if
a[i] < a[n]:

D. swap true and false
on lines 7 and 8

4. A hypothetical
machine called an IntraComparator can execute most instructions for free,
including arithmetic instructions, comparison instructions, and reading the
values of an array. However, writing to
an element of an array still requires Θ(1) time. What is the most efficient sorting algorithm
on an IntraComparator?

A. Bubble sort

B. Selection sort

C. Merge sort

D. Quick sort

5. Consider the following
undirected graph G with vertices V = {1...8} and with the set of edges E =
{(1,3), (1,4), (1,6), (2,5), (2,6), (2,7), (3,4), (4,6), (4,8), (5,8), (6,8)}.
We asked several people to come up with a spanning tree for this graph. Whose
answer is correct?

A. Leander gave E = {(1,4), (1,6), (2,5), (2,6), (4,6), (4,8),
(5,8)}

B. Sania gave
E = {(1,4), (1,6), (2,5), (2,6), (3,4), (5,8)}

C. Usha gave E
= {(1,3), (1,4), (1,6), (2,6), (2,7), (3,4), (4,6), (5,8), (6,8)}

D. Tendulkar
gave E = {(1,3), (1,6), (2,5), (2,6), (2,7), (4,8), (5,8)}

E. Anand gave
E = {(1,3), (2,5), (2,7), (3,4), (4,6), (6,8)}

6. Consider a sorted array a[1..15] that has the following
elements:

2, 20, 37, 56,
75, 111, 127, 175, 196, 258, 367, 735, 768, 831, 959.

Assume we do a binary search to find a number in this array. In
this search, when searching in the range A[low..high], we check A[mid] where
mid= (low+high)/2 and then recurse on A[low..mid-1] or A[mid+1..high],
accordingly. The low and high variables are initialized to 1 and 15,
respectively. Amongst the following numbers, searching for which number will
take the longest time?

A. 768

B. 175

C. 258

D. 56

7. The brute-force
string matching algorithm is used to search for a string x within a string y.
For which of the following inputs will the algorithm perform the most number of
comparisons?

A. x = “MEC”, y = “ALGORITHMS”

B. x = “ADA”, y = “ALGORITHMS”

C. x = “MEC”, y = “AAAAAAAAAA”

D. x = “ADA”, y = “AAAAAAAAAA”

8. Consider the
following recursive function whose argument is an array a[1..n] of integers,
where n >= 1:

1: f(a[1..n]):

2: if n <= 2: return a[n]

3: else: return
(f(a[1..n-2]) + a[n]) XOR f(a[1..n-1])

Which of the following
ideas can vastly improve the running time of this function?

A. Sort the array in ascending order

B. Use divide and conquer by splitting the array in
half

C. Use dynamic programming instead of recursion

D. Build a graph and compute a minimum spanning tree

9. Given a graph G with
n vertices, you want to design an efficient algorithm for finding the number of
vertices of degree <= log n. Which of
the following representations for G would enable your algorithm to have the
most efficient runtime in the worst case?

A. An adjacency list

B. An adjacency matrix

C. The most efficient algorithm can operate on either an adjacency
list or an adjacency matrix

D. The most efficient algorithm requires both an adjacency list and
an adjacency matrix simultaneously

10. Consider the problem
of giving change for any amount. And consider the greedy strategy for giving
change, where we give as many notes of the highest denomination possible,
followed by the notes of the next highest denomination, etc. Let the set of
denominations be 380, 175, 80 and 1. Professor Moriarty claims that the greedy
algorithm gives the optimal number of notes as change. Which of the following
amounts would you use to prove the professor wrong?

A. 27

B. 183

C. 380

D. 243

E. 222

11. Consider the problem
of giving change for any amount. And consider the greedy strategy for giving
change, where we give as many notes of the highest denomination possible,
followed by the notes of the next highest denomination, etc. Let the set of
denominations be 375, 180, 69 and 1. Professor Moriarty claims that the greedy
algorithm gives the optimal number of notes as change. Which of the following
amounts would you use to prove the professor wrong?

A. 186

B. 69

C. 211

D. 26

E. 192

12. Your friend wrote
the following recursive function that tries to sort an array of n integers in
ascending order:

1: sort(a[1..n]):

2: if n > 1:

3: sort(a[1..n-1])

4: for i = 1 to n-1:

5: if a[i] > a[n]:

6: temp = a[i]

7: a[i] = a[n]

8: a[n] = temp

9: return

10: else

11: return

A. The above function
does NOT ALWAYS correctly sort the array

B. The above function always correctly sorts the array
in Θ(n) time

C. The above function always correctly sorts the array
in Θ(n log n) time

D. The above function always correctly sorts the array
in Θ(n^2) time

13. Consider an unsorted
array a[1..n] that stores integers in the range 0 to 120, representing ages of
people. We want to be able to solve the following problem repeatedly: given a
particular age x, find the number of people whose age is less than or equal to
x. The most efficient algorithm for this requires P(n) pre-processing time, and
T(n) time for each given age x in the worst case, where:

A. P(n) is Θ(1) ; T(n) is Θ(log n)

B. P(n) is Θ(n) ; T(n) is Θ(1)

C. P(n) is Θ(n log n) ; T(n) is Θ(1)

D. P(n) is Θ(n log n) ; T(n) is Θ(log n)

14. Given a sorted array
S[] of size n and an unsorted array U[] of size log n, the most efficient way
to combine the elements of S[] and U[] into a single sorted array requires how
much time in the worst case?

A. Θ(log log n)

B. Θ((log n)^2)

C. Θ(n)

D. Θ(n log n)

15. Consider the
following undirected graph G = (V,E) where the vertex set V = {1...8} and the
edge set with weights is E = {(1,3,14), (2,3,5), (2,4,20), (2,6,3), (2,7,21),
(3,4,25), (3,8,3), (4,5,30), (4,8,8), (5,8,6), (7,8,4)}. Triples in E like
(u,v,w) mean that there is an undirected edge between u and v of weight w.
Assume you are running Prim's algorithm starting from vertex 1. Which of the
following edges would you add to the minimum spanning tree at step 5?

A.
Edge: (5,8)

B.
Edge: (7,8)

C.
Edge: (2,3)

D.
Edge: (2,6)

16. A connected,
undirected graph G has two types of edges: risky and safe. Given two distinct
vertices u and v in G, we want to find a path from u to v using the fewest
number of risky edges.

Please give a brief and clear description of an efficient
algorithm to solve this problem. You may call other standard algorithms as
subroutines. For example, you could write
“Delete all risky edges and then perform a breadth-first search starting from
vertex u”. This answer is brief and
clear, and it calls the standard BFS algorithm as a subroutine, but it is
incorrect!