Name _____________________________

CPTR247 Fall '04 (50 points in written portion / 20 points additional code) Exam 1

Multiple Choice: Circle the letter of the best answer for each of the following questions. (2 points each)

1. An algorithm for which the least upper bound on worstTime(n) is O(n) is said to be

a) constant

b) linear

c) quadratic

d) exponential

2. An algorithm for which the least upper bound on worstTime(n) is O(n²) is said to be

a) constant

b) linear

c) quadratic

d) exponential

3. An algorithm that is intractable can also be said to be

a) constant

b) linear

c) quadratic

d) exponential

4. Describes a program that can “withstand the slings and arrows of outrageous inputs.”

a) free

b) friendly

c) tractable

d) robust

5. The binary search algorithm for finding an element in an array requires that the array

a) is filled with elements

b) is sorted

c) contains only integers

d) all of the above

6. The worstTime(n) (where n is the number of elements in the array) of binary search is

a) O(n²)

b) O(log₂n)

c) O(2ⁿ)

d) O(n)

7. The worstSpace(n) (where n is the number of elements in the array) of binary search is

a) O(n²)

b) O(log₂n)

c) O(2ⁿ)

d) O(n)

8. A variable than consists of a collect of items is called a

a) container

b) dynamic variable

c) iterator

d) calling object

SHORT ANSWER:

9. Briefly describe how the backtracking algorithm is used to find the way out of a maze. (4 points)

10. What did Dijkstra have to say about testing, either the quote or a paraphrase? (3 points)

11. Enter the elements in the box into the hierarchy of order so as to make the following statement true. (8 points)

_______ Ì _______ Ì _______ Ì _______ Ì_______ Ì_______ Ì_______ Ì ××× Ì_______ ×××

12. Complete the following definition of Big-O notation. (3 points)

Let f(n) be a function of n. We say that “f is O(g)” if …

13. For each of the following functions f, where n = 0, 1, 2, …, find a function g such that O(g) is the smallest upper bound of f. You are to use the definition in the previous question to prove your answer. (4 points each)

a. f(n) = 3n² + log₂n

b. f(n) = (n + 2)(log₂n + 1)

14. Determine the worstTime(n) in Big-O notation for each of the following snippets of code. (2 points each)

a. (value is an array with n elements)

int total = 0;

int sum = 0;

for (int i = 0; i < n; i++)

{

total = total + value[i];

for (int j = 0; j < n; j++)

{

sum = sum + total;

}

}

b. (value is an array with n elements)

while (n > 1)

{

i = n – 1;

value[i] = 0;

n = n / 2;

}

c. (value is an array with n elements)

int total = 0;

for (int i = 0; i < n; i++)

total = total + value[i];

for (int i = 0; i < n; i++)

value [i] = 0;

cout << ″The total is ″ << total << endl;

d.

int k = 1;

int j = 1;

for (int i = 0; i < n; i++)

k = k * 2;

for (int i = 0; i < k; i++)

j = j * 2;

ADDITIONAL CODE:

Write the following two methods for the IntSet class. (10 points each)

• function InSet(value) -- returns true if the integer value is in the set and false otherwise
• function Intersection(A, B) -- C.Intersection(A, B) stores in C the intersection of IntSets A and B; returns nothing; does not change A or B.

An extra page has been added for you use