As some of you tried to point out to me during the test, and others pointed out to me in your answers, this question, as stated, can't be answered. I figured this out too while I was writing out the answer, but rather than change the question right then and there, I decided to finish the answer first. And then promptly forgot to go back and change the question.
Because this question's duff, I'm removing it from the test, so that - this time - your test only has three questions. I'll leave my original answer if you want to play Jeopardy and figure out what the correct question is.
A witness-criminal can't be placed in a town if the town's already got a witness-criminal living there, or if the town's has a direct road to a town in which a witness-criminal lives. The more interconnected the towns are, the more difficult it will be to place witness-criminals. The worst case occurs when every town is connected to every other town (in which case the map is known as a complete graph).
It's always possible to place one witness-criminal, because there's no other witness-criminal anywhere to interfere. If the map's a complete graph, then every other town is adjacent to the town containing the witness-criminal and no other towns can accept witness-criminals. Finally, because every town is adjacent to every other town, the only witness-criminal can be placed in any town.
The input should be any complete graph, such as the three node graph
0: 1 2 1: 0 2 2: 0 1
and the output can be any one of the input towns.
bool has_duplicate1(v)
std::sort(v.begin(), v.end())
return std::find_adjacent(v.begin(), v.end()) != v.end()
bool has_duplicate2(v)
for (i = 0; i < v.size() - 1; i++)
for (j = i + 1; j < v.size(); j++)
if (v[i] == v[j])
return true
return false
both return true if and only if the input vector has a duplicate element value. Determine which, if any, is the asymptotically faster than the other. Make sure you clearly state your assumptions.
std::find_adjacent(b, e) returns an iterator to the left-most value in the
sequence delimited by (b, e) such that *b == *(b+1); if there is no
such element, it returns e. Iterators b and e are forward
iterators.
The function calls begin() and end() both take constant time;
replacing them in has_duplicate1() produces
std::sort(O(1), O(1)) return std::find_adjacent(O(1), O(1)) != O(1)
The worst-case behavior for std::sort() is O(n2), where n is the
number of elements in the given iterator range; O(n log n) is also an acceptable
estimate. Comparing two iterators takes constant time. The refined estimate
for has_duplicate1() is
O(n2) return std::find_adjacent(O(1), O(1))
The worst-case behavior for std::find_adjacent() would be input with no
duplicate values, which forces it to scan the whole sequence, for a
O(n) estimate. Returning a function value takes constant time; the new
estimate for has_duplicate1() is
O(n2) O(n)
A final application of the sequence rule give
O(n^2) + O(n) = O(max(n^2, n)) = O(n^2)
As for has_duplicate2(), assuming v is a vector, the size and access
operators take constant time, and so does returning a value from a procedure.
for (i = 0; i < O(1) - 1; i++)
for (j = i + 1; j < O(1); j++)
if (O(1) == O(1))
O(1)
O(1)
Arithmetic and comparisons all take constant time.
for (O(1); O(1); O(1))
for (O(1); O(1); O(1))
if O(1)
O(1)
O(1)
The if rule collapses the inner for loop body.
for (O(1); O(1); O(1))
for (O(1); O(1); O(1))
max(O(1), O(1)) + O(1) = O(1)
O(1)
The number of iterations of the inner loop is bounded by n, the size of
the input vector v.
for (O(1); O(1); O(1)) O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n*1) = O(n) O(1)
Same thing for the outer loop:
O(n)*(O(n) + O(1)) = O(n)*O(n) = O(n^2) O(1)
The sequence rule produces a final estimate of O(n2) for has_duplicate2().
According to this analysis, both cdr(has_duplicate1()) and
has_duplicate2() have O(n2) behavior, and so have similar performance.
Most people were sloppy when they answered this question, giving a few brief sentences about each function, usually with incomprehensible estimates. This time I gave those people some credit this time; the next test I won't. I expect all future answers to look like the answer given above, and if they don't, you're not going to get any credit at all.
Although I won't generally take off points for a mis-estimate, there were some
mis-estimates that betrayed a lack of understanding for both asymptotic
estimates and the way code works. Many people wrote that, for example,
std::find_adjacent() took O(1) time. A constant-time upper bound
(which O(1)) is) means the behavior being estimated can be bounded above
by a constant value; that is, the behavior being estimated is independent of
the size of the input. It is not possible (on standard hardware) to implement
std::find_adjacent() in constant time; in the worst case (no adjacent
equalities) the code has to look at every element in the sequence, which takes
O(n).
ip is a pointer to an integer, explain which of the following
code fragments is valid:
| a) | *ip = 0; ip = 0; |
Part a assigns zero to the integer variable pointed to by ip and then sets
ip to zero; Part a is valid. Part b does the same thing as Part a, except
in reverse order. In Part b the assumption that ip contains the address
of an integer variable is false; as Koenig and Moo point out on page 170, zero
represents a pointer value that points to no possible object (integer variable,
in this case). An assignment through the zero pointer can't possibly be
valid.
Wow. One person got this question right, which is terrible because you should have known this walking into 509, and because it was part of your readings for the test.
As Koenig and Moo point out on page 164, default initialization is equivalent to no initialization at all. Value initialization, on the other hand, makes sure that a variable has a particular value, which requires assigning the value to the variable. Because default initialization does nothing and value initialization does something, default initialization is faster than is value initialization.
Three people got this one right. This question was not as straightforward as question three, but still.
This page last modified on 21 March 2003.