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(n2) 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(2n) 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(n2)

d)       O(log2n)

e)       O(2n)

 

 

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(log2n)

                      n    for linear time – O(n)

                    n2    for quadratic time – O(n2)

 

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