Practice Questions

Question 1:

Let A(n) and B(n) denote the worst-case running time for algorithms A and B, respectively, as a function of the input size n.  Consider the following statements:

I.  If A(n) is Theta(B(n)), then B(n) is Theta(A(n))

II. If A(n) is O(B(n)), then B(n) is O(A(n))

A. Statement I is true and Statement II is false

B. Statement I is false and Statement II is true

C. Both Statement I and Statement II are true

D. Both Statement I and Statement II are false

Question 2:

Consider the following algorithms:

Insertion sort

Merge sort

Selection sort

Bubble sort

Binary search

Which of the following recurrences does NOT describe the worst-case running time of any of the above algorithms (for an input of size n)?

A. T(n) = T(n/2) + Theta(1)

B. T(n) = 2T(n/2) + Theta(n)

C. T(n) = T(n-1) + Theta(1)

D. T(n) = T(n-1) + Theta(n)

Question 3:

Consider a modified version of Merge sort in which the base case of the recursion has been changed.  In the original version, the base case checked whether the array had one element (or less); if so, it returned the array without any modifications.  In the new version, the base case checks whether the array has 1000 elements (or less); if so, it sorts those elements using insertion sort and returns the sorted elements.  Given an array of n elements, what is the worst-case running time of this hybrid sorting algorithm?

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(n^2 log n)

Question 4:

Consider an algorithm that is operating on a sparse graph (that is, a graph with n vertices and O(n) edges).  If the algorithm changes the representation of matrices from an adjacency list to an adjacency matrix, which of the following is NOT possible?

A. The algorithm will run slower.

B. The algorithm will run faster.

C. The algorithm will use more space.

D. The algorithm will use less space.

Question 5:

Suppose that each edge e of an undirected graph G has a unique positive edge weight w(e). Suppose T is a Minimum Spanning Tree of G. Consider the following statements

I. The heaviest edge in G is an edge in T

II. The lightest edge in G is an edge in T

A. Statement I must be true and Statement II must be false

B. Statement I must be false and Statement II must be true

C. We cannot say for sure whether Statement I is true

D. We cannot say for sure whether Statement II is true

Question 6:

Suppose you are asked to implement a binary search.  The procedure should input an array A of integers, indices hi and lo, and a value val to search for.  It should search the array elements between A[lo] and A[hi], inclusive.  If the value appears in this range, the procedure should return an index i such that A[i]=x.  If the value does not appear in this range, the procedure should return -1.

Your friend suggests using the following code:

int buggy_search(int A[], int lo, int hi, int val) {

int mid = (lo+hi)/2;

if A[mid]==val

return mi

else if lo==hi

return -1

else if (val<A[mid])

return buggy_search(A, lo, mid, val)

else

return buggy_search(A, mid, hi, val)

}

However, this code has a bug.  When an execution is affected by the bug, what is the program behavior?

A. It returns -1 when it should have returned a non-negative value

B. It returns an index i such that A[i]!=x

C. It causes an infinite recursion (stack overflow error)

D. It causes an array out-of-bounds exception

Question 7:

Let f(n) represent the total number of times that QuickSort calls itself recursively on an array of size n.  What is the tightest upper bound on f(n)?

A. f(n) = O(log n)

B. f(n) = O(n)

C. f(n) = O(n log n)

D. f(n) = O(n^2)

Question 8:

In the following procedure, the parameter A represents an unweighted, directed graph as an adjacency matrix.  A[i][j]=1 if and only if there is a directed edge from vertex i to vertex j.

procedure Mystery(int A[N][N])

for i = 1 to N:

for j = 1 to i:

if A[i][j] == 1 then:

return FALSE

return TRUE

Mystery(A) returns true if and only if:

A.  A represents an acyclic graph.

B.  The vertex ordering 1, 2, … N represents a topological sort of the graph.

C.  The graph is not connected.

D.  All of the above.

Question 9:

For which of the following graphs does Prim’s algorithm and Kruskal’s algorithm add edges to the Minimum Spanning Tree in the same order?  Assume that Prim's algorithm starts from vertex v.

Question 10:

A group of n students left their shoes outside the classroom.  Unfortunately, when they returned the shoes had been re-arranged.  All the shoes are identical except for the size, which is different for every student and is not labeled in any way.  The only possible actions are to compare the size of two shoes, to compare the size of two students' feet, or to test whether a pair of shoes is too big or too small for a student.  What is the worst-case runtime of the most efficient algorithm for matching every student with their shoes?

A. O(n)

B. O(n log log n)

C. O(n log n)

D. O(n^2)

Question 11:

Reconsider the prior problem, with one small change:  not only have the shoes been reordered, but most of them have been stolen.  In fact, only O(log n) of the shoes are remaining.  Using the same possible actions as before, what is the worst-case runtime of the most efficient algorithm for matching the remaining shoes with their owners?

A. O(n)

B. O(n log log n)

C. O(n log n)

D. O(n^2)

Question 12:

A courier service delivers packages to a single long street.  The houses are numbered in order, from 1 to n.  For convenience, the driver prefers to park the car and walk to nearby houses whenever possible.  However, when the car is parked at a given house, the driver is only willing to walk up to k houses in either direction.  On a given day, let d(i) denote whether a delivery is required to house i.  The driver wants to deliver all the packages while minimizing the number of parking locations.  What is the best approach?

A. A dynamic programming algorithm

B. A greedy algorithm

C. A sorting algorithm

D. A binary search algorithm

Question 13:

You have invented a new mechanical scale that can compare the weight of three items at a time.  After loading the scale, you can immediately tell which of the three items is the lightest, which is the heaviest, and which is in between.  What is the best lower bound on the number of three-way comparisons needed to completely sort n items?

A. log_2 (n!)

B. log_3 (n!)

C. log_6 (n!)

D. log_10 (n!)

Question 14:

Consider a weighted, connected undirected graph G, with source vertex s and end vertex t.  Suppose there is a unique shortest path between s and t, consisting of k edges.  Let x denote the number of edges along this path that also belong to a Minimum Spanning Tree of G.  What is the tightest correct bound on the value of x?

A. x = 1

B. x = k

C. 0 <= x <= k

D. 1 <= x <= k

Question 15:

Consider a network containing n nodes and m links. If we try to send a packet of data from some node u along a link to a different node v, the probability that the packet will be successfully transmitted is p(u, v), where 0 < p(u, v) < 1. Assume that p(u, v) = p(v, u) for all links (u, v) in the network, and that all failures occur independently of each other. Given this network, and start vertex s and end vertex t, describe an algorithm to determine the “best” way to send a packet from s to t, so that the probability that the packet will be successfully transmitted is as high as possible.