____ Those things that must be true in order to call a method, generally coded as comments underneath the method header.
____ Those things that will be true after a method is called, generally coded as comments underneath the method header.
____ Gives the explicit information that the user needs to invoke (or call) a method (i.e. return type, method name, number and type of parameters).
____ A generic name for a call to a method in a class.
____ When a variable is defined using the new operator, memory for that variable is taken from here.
____ Every time a function or method is called, memory for its activation record that holds (among other things) local variables for that invocation of the function is taken from here.
____ Describes the worstTime(n) for a function whose smallest upper bound is O(1).
____ Describes the worstTime(n) for a function whose smallest upper bound is O(log n).
____ Describes the worstTime(n) for a function whose smallest upper bound is O(n).
____ Describes the worstTime(n) for a function whose smallest upper bound is O(n2).
____ The O(log n) method of finding an item in a sorted array.
____ The O(n) method for finding an item in an array (sorted or unsorted).
____ A FIFO data structure.
____ A LIFO data structure.
2. 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 |
|
|
|
pop_back |
|
|
||
|
insert |
|
|
||
|
begin |
|
|
||
|
operator [ ] |
|
|
||
|
list |
doubly linked list with a dummy header node, node (a pointer to the dummy node), and length |
insert |
|
|
|
pop_front |
|
|
||
|
pop_back |
|
|
||
|
empty |
|
|
||
|
deque |
dynamically allocated blocks (array-based) with a map array, start, and finish |
push_front |
|
|
|
push_back |
|
|
||
|
operator [ ] |
|
|
||
|
insert |
|
|
||
|
erase |
|
|
SHORT ANSWER:
3.
Enter the elements in the box into the hierarchy of order so as to make the
following statement true. (10 points)
______ Ì ______ Ì
______ Ì ______ Ì______ Ì______ Ì______ Ì______ Ì______
Ì______
4. There is only one method of the stack class (which is implemented as a deque) whose worstTime(n) is O(n). Which one is it (of push, pop, top, size, or empty) ? (2 points)
5. Explain how push_back works for the vector class and why the averageTime(n) and worseTime(n) are as you stated in question 2. (4 points)
6. Explain how pop_front works for the list class and why the averageTime(n) and worseTime(n) are as you stated in question 2. (4 points)
7. Let’s compare arrays to the vector and list classes.
a. What is the main disadvantage of arrays that is not a problem with vectors and lists? (2 points)
b. What is the operation that arrays and vectors have that lists do not, thereby making them attractive data structure for some applications? Why doesn’t the list class have that operation? (3 points)
8.
We
used recursion to solve problems that required backtracking, such as finding our
way off of a sinking ship and figuring out how to move the pegs in the dreaded
Triangle problem. Explain how recursion was used to solve problems requiring
backtracking. I’m not looking
for code here but rather an explanation of how recursion and The Stack
work and how they are used for backtracking.
If drawing diagrams helps, feel free to do so. (5 points)
9.
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 …
10. 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. (5 points each)
a.
b. 
11. Determine the worstTime(n) in Big-O notation for each of the following snippets
of code. (3 points each)
a.
for
(int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << setw(4) << i *
j << “ “;
}
cout << endl;
}
b. (value is an array with n elements)
int
total = 0;
for
(int i = 0; i < n; i++)
cin >> value[i];
cout
<< “The array contains:” << endl;
for
(int i = 0; i < n; i++)
{
cout
<< value[i] << endl;
total
= total + value[i];
}
cout
<< endl << “Total: ” << total << endl;;
c.
int
computedValue = 1;
for
(int i = (n * n * n); i >= 1; i--)
computedValue *= i;
12. 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. Towers
of