1. Let A and B be classes, with A the parent of B; assume const char * class_name(void) is defined in each class and produces the appropriate output. Given the following correct code

   void ex(void) {
   
     A * a1p = new A;
     cout << a1p->class_name(); << "\n";
   
     A * a2p = new B;
     cout << a2p->class_name(); << "\n";
   
     delete a1p;
     delete a2p;
     }
   

   what output would ex() produce when called if A::class_name() is virtual? Explain. What output would ex() produce when called if A::class_name() is not virtual? Explain.

   ---

   If A::class_name() is virtual, C++ uses the dynamic type of a variable to start the search for a suitable member function. After the first assignment, a1p has dynamic type (pointer to) A, and A::class_name() would be called. After the second assignment, a2p has dynamic type (pointer to) B, and B::class_name() would be called. The output would be

   A
   B
   

   If A::class_name() is not virtual, C++ uses the static type of a variable to start the search for a suitable member function. Both a1p and a2p have static type (pointer to) A, so the search starts and ends with A, producing the output

   A
   A
   

   Most people got this one right, but a number of people made a fairly serious mistake regarding member functions look-up. In C++, and in many other object-oriented languages, the search for member functions always goes up the inheritance hierarchy towards the ancestors; it never goes down towards the descendents.

   ---

2. Kernighan and Pike distinguish between the two predicate names is_octal() and check_octal(), saying one is better than the other. Which name do they prefer? Explain their reasoning for preferring one name over the other.

   ---

   K&P prefer is_octal() over check_octal() because is_octal() gives an unambiguous interpretation to the boolean values returned. See page 4 for details.

   ---

3. A colleague of yours was looking at the code you wrote for the first assignment and recommended that you could greatly improve your code by using the routines provided in the standard string library string.h. What do you think of your colleague's suggestion? Explain.

   ---

   Your colleague's suggestion has a serious problem: the strings passed into the disable_font() routine are not the standard, null-delimited strings that C and C++ expects, and so won't work with the standard sting routines. If you wanted to take your colleague's suggestion, you would have to do something expensive like copy the input string to a buffer where you could append a null byte (and then copy it back again), or do something tricky, like replace the last character in the input string with a null byte (and remember to both replace the last character and process it as part of the input).

   Your colleague's suggestion also has some other, less serious problems, such as the wisdom of using string-oriented routines to perform what is essentially character-oriented operations.

   Most people got this one wrong. The point here is to make sure you pick the right tool for the job. A string library may be efficient and descriptive and standard and wonderful, but if you're not dealing with strings, it may not be the right tool for the job.

   ---

4. A colleague of yours claims to have written an algorithm that fills and manipulates a 2D matrix of items, but yet only uses O(n) time, where n is the number of items manipulated. Explain how this can be.

   ---

   Any algorithm manipulating a p X q matrix must take at least O(pq) time and space because the matrix contains pq elements. To square your colleague's claim with this fact, it would have to be that

   pq = n

   This holds whenever p and q are factors of n (in the trivial case, p = 1 and q = n, that is, the matrix is actually a vector). Alternatively, and less trivially, your colleague could have set the dimensions of the matrix to be

   p = q = n^1/2

   where n^1/2 is the square root of n.

   A number of people tried to outrun this problem by pointing out that matrices are stored linearly in storage, and therefore take O(n) space. It is true that matrices are stored linearly, but a p by q matrix has pq elements and takes pq, or O(n²), space.

   ---

This page last modified on 3 February 2001.