no_negatives(vector& ivec) i = ivec.begin() while (i = find_if(i, ivec.end(), negative)) != ivec.end() *i = -*i no_negatives(list & ilst) while (i = find_if(ilst.begin(), ilst.end(), negative)) != ilst.end() *i = -*i
negative() is a predicate that returns true if and only if its input
argument is negative. Make sure you clearly state your realistic assumptions.
For a, iterator access and assignment and negation take constant time; the loop
body is O(1). begin() and end() are constant-time operations,
as is negative() under completely reasonable assumptions.
The tricky part about a is determining the estimate for find_if(). The
problem is find_if() starts at a different place in the vector each time
it's called, which makes deriving an estimate difficult. In addition, the
number of iterations depends on the value returned by find_if().
The analysis is difficult, but not impossible. The key is to remember that the
estimate is an upper bound on the amount of work that could be done. The most
amount of work is done when the vector contains only negative numbers. In that
case each call to find_if() takes constant time (move to the next
element), giving the estimate
while O(1) O(1)
and the number of iterations is O(n), giving the estimate
O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n)
For b, the loop body is still O(1), as are begin(), end(), and
negative(). Now, however, because find_if() starts from the same
place each time, it can be assigned an O(n) asymptotic estimate:
while O(n) O(1)
The iteration count worst-case bounded by O(n), giving a final estimate of
O(n)*(O(n) + O(1)) = O(n)*O(n) = O(n2)
In this case, because it is used more intelligently, the vector in a is asymptotically faster than the list in b.
A number of people didn't do well on this question because they just guessed and didn't provide an asymptotic estimate. A few other people threw around some asymptotic estimates, but didn't do so convincingly because they assumed that manipulating lists were naturally more efficient than manipulating vectors.
Yes. A const member function may not to change the called instance; a
non-const instance may be changed by member function calls. There is no
logical or actual problem with the combination of a const member function
and a non-const called instance.
A number of people tried to answer this by talking about the return value from
the const member function. But a member function isn't obligated to
provide a return value, and a const member function may return a non-const
value. A number of people tried to make a similar argument with parameters,
but again, a member function isn't obligated to have parameters (except the
implicit this parameter) and any parameters it may need not be const.
If the program has implemented intersection and difference correctly the test
r1 = rectangle 1 1 10 10 r2 = difference r1 r1 output r2 r3 = intersection r1 r1 output r3
should result in output equivalent to nothing for the first case and output
equivalent to to r1 in the second case.
There were a lot of strange answers to this question. The most common problem was giving a test with only one output statement. If you want to check that two different commands are implemented correctly, you probably are going to need two different output statements. Some people confused difference and intersection, and some people just got them wrong.
X point {
point(int x, int y) { ... }
};
int main() {
point p1(1, 3);
}
What is X? Explain.
See Section 9.3 in Koenig and Moo.
An unpleasantly large number of people got this question wrong. The most unfortunate answer, which was given a number of times, was "X is either class or struct."
This page last modified on 27 March 2002.