Name _____________________________

 

CPTR247 Fall '05 (100 points) Exam 1

 

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

 

1.        Provides the user of a class with the explicit information that the user needs to invoke (or call) a method:

a)       class instance

b)       method interface

c)       overriding method

d)       calling object

 

2.        The code account.setRate(newValue) is best described as a

a)       class

b)       message

c)       calling object

d)       parameter

 

3.        In the code account.setRate(newValue), account is best described as a

a)       class

b)       message

c)       calling object

d)       parameter

 

4.        The separation of what a class provides to programmers from how the class is defined:

a)       overriding methods

b)       generic algorithms

c)       derived classes

d)       data abstraction

 

5.        If an object of class X is one of class Ys fields (aka instance variables or data members), we say that

a)       X is-a Y

b)       Y is-a X

c)       X has-a Y

d)       Y has-a X

 

6.        If the worstTime(n) of a function is quadratic, its smallest upper bound is

a)       O(n2)

b)       O(log2n)

c)       O(2n)

d)       O(n)

 

7.        If a problem is intractable, then the most efficient known algorithm that solves it is at best

a)       O(n2)

b)       O(log2n)

c)       O(2n)

d)       O(n)

 

8.        When a variable is defined using the new operator, memory for that variable is taken from

a)       The Stack

b)       The Heap

c)       The Standard Template Library

d)       None of the above. The new operator only gets a pointer.

 

 

 


SHORT ANSWER:

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

 

 

______ ______ ______ ______ ______ ______ ______ ______ ______ ______

 

 

10.     Give the complexity (smallest upper bound) for each of these common operations on arbitrary arrays and linked lists of size n. (10 points)

 

Operation

Arbitrary arrays

Linked lists

find by value

O( )

O( )

find by location

O( )

O( )

insert at head

O( )

O( )

insert at tail

O( )

O( )

insert by position

O( )

O( )

 

 

11.     Describe the O(log 2 n) algorithm for finding a value in a sorted array. (4 points)

 


12.     Complete the following definition of Big-O notation. (5 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. (8 points each)

 

a.       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.      


14.     Prove that . (10 points)

 

 

 

 


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

 

a.        (value is an array with n elements)

 

int total = 0;

 

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

total = total + value[i];

 

cout << The array contains: << endl;

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

{

cout << value[i];

}

cout << endl << Total: << total << endl;;

 

 

 

 

 

 

 

 

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

 

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

{

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

{

value [i][j] = value[j][i];

}

}

 

 

 

 

 

 

 

 

c.         

int computedValue = 0;

 

for (int i = n; i > 1; i = i/2)

computedValue *= i;

 


16.     Give a brief description of each of the following classic problems. (3 points each)

 

a.        Knights Tour

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.       Towers of Hanoi

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c.        n-Queens problem