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?

Smiley face

        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?

Smiley face 

               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!