• University of Waterloo

• CS 234

PART I – True/False – 5 marks

1. State whether the following statements are true of false. You do not need to provide any explanations.

 For any three positive functions f(n), g(n) and h(n), if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)), then

f(n) * g(n) ∈ O(h(n)). False

 2𝑛 + 𝑛2 ∈ 𝑂(3𝑛). True

 No matter how complex a problem is, we can have at most three layers of abstraction. False

 Merge Sort has the worst-case running time better than that of Quicksort. True

 Any comparison-based sorting algorithm requires 𝛺(𝑛 log 𝑛) time to sort a list of n elements.

True

PART II – Multiple Choice – 10 marks

2. [1 mark] Which of the following statements is NOT correct about the Abstract Data Types (ADTs)?

a) One reason for using ADTs is that we can focus on implementation instead of functionality.

b) ADTs are implementation independent; that is, implementation details are hidden.

c) ADT operations can be grouped into four categories constructors, accessors, mutators and iterators.

d) In designing an ADT, we focus on what the ADT can do, not how it does it.

3. [1 mark] Which of the following statements about Array data structure is NOT correct?

a) An array has a fixed size.

b) An array can store different types of values.

c) Two-dimensional arrays are a good choice for implementing matrices.

d) Arrays are used to implement other data structures.

4. [1 mark] Suppose that A and B are two 2-dimenssional arrays of size n×n. Which of the following

statements is NOT correct?

a) There exists an algorithm to compute A+B in O(𝑛2) time.

b) There is no algorithm to compute A+B in O(𝑛3) time.

c) There exists an algorithm to compute A*B in O(𝑛3) time.

d) There exists an algorithm to compute (A*B)+(A*A) in O(𝑛3) time.

5. [1 mark] Suppose that A is an array of n elements sorted in increasing order. Which of the following

statements is correct?

e) Sorting A in increasing order using Insertion Sort takes O(n) time.

f) Sorting A in increasing order using Quicksort with the last element as pivot takes O(n) time.

g) Sorting A in decreasing order using Insertion Sort takes O(n) time.

h) Sorting A in increasing order using Quicksort with the first element as pivot takes O(n) time.

6. [1 mark] Assuming n is the input parameter, which of the followings correctly lists the expressions

from lowest to highest asymptotic growth rate?

a) n * log(log n), n * log n, n3/2, 22016

b) 22016, n * log(log n), n3/2, n * log n

c) 22016, n * log n, n * log(log n), n3/2

d) 22016, n * log(log n), n * log n, n3/2

7. [1 mark] Which of the following sorting algorithms has the worst-case running time O(n log n) for

sorting an array of size n?

a) Insertion Sort

b) Merge Sort

c) Quicksort with first element as pivot

d) Both b) and c) are correct

8. [1 mark] Consider the following code fragment in which x is an integer and A is an array of n integer

values.

for i <-- 0 to n-2:

for j <-- i+1 to n-1:

if A[i]+A[j]=x:

return i+j

return -1

What is the return value of the above code fragment if x=11 and A=3, -2, 2, 7, 9, 6, 13?

a) -1

b) 6

c) 7

d) 8