Name _____________________________

CPTR247 Fall '08 (100 points) Exam 1

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

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

a) constant

b) logarithmic

c) linear

d) quadratic

e) exponential

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

a) constant

b) logarithmic

c) linear

d) quadratic

e) exponential

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

a) constant

b) logarithmic

c) linear

d) quadratic

e) exponential

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

a) constant

b) logarithmic

c) linear

d) quadratic

e) exponential

5. If a problem is intractable, then the most efficient known algorithm to solve it is at best

a) O(1)

b) O(n)

c) O(n²)

d) O(log₂n)

e) O(2ⁿ)

6. You are solving a problem that requires the use of a container where objects will be inserted and removed from both the front and the back of the container. Which container is best to use?

a) array

b) vector

c) deque

d) stack

e) queue

SHORT ANSWER:

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

______ Ì ______ Ì ______ Ì ______ Ì______ Ì______ Ì______ Ì______ Ì______ Ì______

8. Complete the following table by entering the algorithmic complexity for each method. (1 point each)

Enter one of the following for each:

C for constant time – O(1)

log for logarithmic time – O(log₂n)

n for linear time – O(n)

n² for quadratic time – O(n²)

Data Type	Implementations	Methods	averageTime(n)	worstTime(n)
vector	dynamically allocated array with pointers start, finish, and end-of-storage	push_back
		insert
		erase
		operator [ ]
		pop_back
list	doubly linked list with a dummy header node, node (a pointer to the dummy node), and length	push_front
		begin
deque	dynamically allocated blocks (array-based) with a map array, start, and finish	push_front
		push_back
		pop_front
		operator [ ]
		end
queue	deque	front
		push

9. Explain how the erase method works for the vector class and why the averageTime(n) and worseTime(n) are both O(n). (4 points)

10. Explain how the erase method works for the list class and why the averageTime(n) and worseTime(n) are both O(1). (4 points)

11. Explain the statement, “The list class does not support direct access.” (2 points)

12. Why does the list class not support direct access? (2 points)

13. What is the primary advantage that the deque class has over the vector class? (3 points)

14. Give two advantages that the vector class has over arrays. (6 points)

15. Describe the use of The Stack and The Heap during the execution of a program. Include in your explanation code examples for the use of each. (6 points)

16. Explain how binary search works to find an element in a sorted array or vector. It is not necessary to provide any code, but if it helps you explain the algorithm, feel free to include it. (4 points)

17. 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 …

18. 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.

b.

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

a. (value is a two-dimensional array with n rows and n columns)

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

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

cout << value[i][j];

}

cout << endl;

}

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++)

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

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

total = total + (i * j * k);

cout << “The total is:” << total << endl;

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

{

cout << value[i];

}

cout << endl;

d.

int n;

cout << “Enter value of n: “;

cin >> n;

cout << n*n << endl;

20. Give a description of each of the following classic problems. Describe the set-up and explain what the “answer” is that we’re searching for. (3 points each)

a. Knight’s tour

b. n-Queens