struct A {
// definition of f().
}
struct B : public A {
// definition of f().
}
struct C : public B {
// definition of f().
}
each define a member function f(). Given the specified behavior for the
following code
C c; B & b = c; A & a = b; a.f(); // Prints "in A::f()". b.f(); // Prints "in C::f()". c.f(); // Prints "in C::f()".
define the member function f() in each of the classes A, B, and
C.
a has static type A and dynamic type C. Because a.f()
ended up calling A::f(), A::f() must be non-virtual because otherwise
dynamic binding would have called C::f().
A similar argument in the other direction applies to b. b has static
type B and dynamic type C. Because b.f() ended up calling
C::f(), B::f() must be virtual because otherwise static binding would
have called B::f().
c the same static and dynamic type, which is C, and so C::f()
can be either virtual or not. But, because C is a child of B and
f() is virtual in B, then f() must also be virtual in C.
Most people got this one down the middle, which is not surprising because it's an example we went over in class.
Using inheritance to provide missing member functions can either use virtual functions or not. Explain whether it is better to use or not use virtual functions when providing missing member functions.
Let A be a class that is missing some member functions and complete-A
be the class the supplies the missing member functions.
Without using virtual functions, A would be complete-A's parent.
complete-A would implement the missing member functions and functions not
inherited (such as the constructors and destructor); inheritance (static
binding) would use A to supply the rest.
With virtual functions complete-A would be A's parent.
complete-A would define a complete interface, which includes the missing
member functions and all member functions implemented by A. The latter
would be virtual so that inheritance (dynamic binding) can use A to supply
them; the missing member functions are defined by complete-A.
Which is better depends on what you're looking for. The non-virtual case is
easier to specify because complete-A only needs to define the missing
functions; inheritance takes care of the rest. In addition, A doesn't
have to be changed. In contrast, the virtual case requires that complete-A
specifies all member functions and makes those belonging to A virtual, and
A has to be made to inherit from complete-A.
Most people lost big points on this because they essentially wrote "yes, virtual functions are good" with no further explanation.
Using the standard "run over rise" formulation of line slope, a line's slope is infinite when its y component is zero; that is, when the line is vertical.
The test case
0 0 0 1 0 2 1 0
Defines an L shape in which the vertical part contains three points. A
correct implementation of colinear return the set 0 0 0 1 0 2.
If you recognized that vertical lines have infinite slope, you got this one; otherwise, you didn't.
The following typedefs are in effect for both algorithms
typedef pair<int, int> int_pair typedef vec<int_pair> ip_vec typedef map<double, ip_vec> slope_map
You should not worry about whether or not each algorithm is correct; just determine an asymptotic estimate for each.
a) colinear(ip_vec pts)
ip_vec max_line
max_line.push_back(pts[0]);
max_line.push_back(pts[1]);
for i = 1 to n - 1
slope_map slopes
for j = i + 1 to n
slopes[(pts[i].x - pts[j].x)/(pts[i].y - pts[j].y)].push_back(pts[j])
max = slopes.begin()
for i = slopes.begin() + 1 to slopes.end()
if i->second.size() > max->second.size()
max = i
if max->second.size() > max_line.size
max_line = max->second.
return max_line
b) colinear(ip_vec pts)
ip_vec max_line
max_line.push_back(pts[0]);
max_line.push_back(pts[1]);
for i = 1 to n - 1
vector<ip_vec> slopes(10000)
for j = i + 1 to n
s = ((pts[i].x - pts[j].x)/(pts[i].y - pts[j].y)*1000000) % slopes.size();
slopes[s].push_back(pts[j])
max = 0
for j = 1 to slopes.size() - 1
if (slopes[max].size() < slopes[j].size())
max = j
if slopes[max].size() > max_line.size()
max_line = slopes[max]
return max_line
Point vector initialization can take either O(1) if the vector is unsized, or perhaps O(n) if the vector is presized. However, from Chapter 11 in Koenig and Moo, it is possible to initialize a vector in constant time even if it is presized, so an estimate of O(1) seems reasonable.
As for vector push-back, if the vector is presized, it takes constant time because there's no copying (assuming the presize is big enough). Otherwise, it can take worst case O(n) time to create a new, bigger vector and copy the elements from old to new. Because presizing costs the same as not presizing, it's reasonable to assume the vector is presized and that push-back takes constant time.
Vector assignment is O(n), no way around that (actually, there is by using sharing semantics, but it's shakey to assume the stl uses that for assignments). Return can be considered the same as an assignment.
O(1)
O(1)
O(1)
for i = 1 to n - 1
O(1)
for j = i + 1 to n
slopes[O(1)].push_back(O(1))
O(1)
for i = slopes.begin() + 1 to slopes.end()
if O(1)
O(1)
if O(1)
O(n)
O(n)
We can apply the pre-allocation argument to assign an O(1) estimate to the push-back. Map access is O(log n); this, along with the sequence and if rules, gives
O(1)
for i = 1 to n - 1
O(1)
for j = i + 1 to n
O(log n) + O(1) = O(log n)
O(1)
for i = slopes.begin() + 1 to slopes.end()
O(1)
O(1)
O(n)
Both inner loops have guards that execute in constant time. The upper loop has an iteration count bounded by n. The lower loop has the same bound, for roughly the same reason: the upper loop can generate at most n different slopes, which gives the map at most n different elements. The loop rule then gives
O(1) for i = 1 to n - 1 O(1) O(n)*(O(1) + O(log n)) = O(n)*O(log n) = O(n log n) O(1) O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n) O(1) O(n)
The remaining loop has constant guards and O(n) iterations. The sequence and loop rules combine to give a final O(n^2 log n) estimate for algorithm a.
Algorithm b offers no new surprises, but it does have a few tricks. In
particular, initializing slopes takes constant time, although the constant
may be big. Vector access is constant time, as is push-back assuming a
big-enough presize (fortunately, the analysis is for time and not space).
O(1)
O(1)
O(1)
for i = 1 to n - 1
O(1)
for j = i + 1 to n
O(1)
O(1)
O(1)
for j = 1 to slopes.size() - 1
if O(1)
O(1)
if O(1)
O(n)
O(n)
Repeated application of the sequence and if rules gives
O(1)
for i = 1 to n - 1
O(1)
for j = i + 1 to n
O(1)
O(1)
for j = 1 to slopes.size() - 1
O(1)
O(n)
O(n)
The first inner for has a constant-time guard and an upper bound of n in the number of iterations. The second inner for also has a constant-time guard but the number of iterations is bounded by a constant (a big one, true, but still constant). The loop rule provides
O(1)
for i = 1 to n - 1
O(1)
O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n)
O(1)
O(1)*(O(1) + O(1)) = O(1)*O(1) = O(1)
O(n)
O(n)
The remaining for has a constant-time guard and an O(n) upper bound on iterations, which, along with the sequence rule, gives
O(1) O(n)*(O(1) + O(1) + O(n) + O(1) + O(1) + O(n)) = O(n)*O(n) = O(n^2) O(n)
A final application of the sequence rule gives an O(n^2) running time for algorithm b, which is asymptotically faster than the O(n^2 log n) running time for algorithm a.
A lot of people lost points for silly mistakes, such as assigning sub-polynomial estimates to doubly nested loops. Some of the initial estimates were excessively wide of the mark, particularly with respect to the map.
This page last modified on 3 May 2002.