CS 509 Test 7

CS 509, Advanced Programming II

Fall 2002 - Test 7

Describe some constant-time testing code that determines if an implementation of mau() returned additive upsequences that were too big; that is, returned additive upsequences that contained too many numbers.
Your testing code does not have to determine if the size of the returned additive upsequence is too small, and it doesn't have to determine if the size of the returned upsequence is the correct. Your testing code just has to determine if the size of the returned upsequence is too big.
Your testing code may be asymptotic in the sense that it only has to work reliably when the input parameter n is "big enough"; make sure you specify in your answer what "big enough" means. Because your testing code must run in constant time, it does not include the cost of calling mau() to generate the additive upsequence.
You can construct an additive upsequence for n by repeatedly halving n and adding the halves to the upsequence. If n is even, halving it adds one new number to the upsequence. If n is odd, it adds two new numbers to the upsequence, one of which - n/2 + 1 - can be formed from the other (n/2) by adding 1. In the worst case, every halving of n is odd (n = 15, for example), which means that, for a given n, the largest possible upsequence formed from n will have at most 2*(ceiling(log₂(n)) + 1) numbers (adding one takes care of accounting for both 1 and n in the upsequence). This is an over-estimate, because it assumes that all halvings will be odd, and so is valid for any n > 1.
With this bound, the test follows:
```
const unsigned 
  mau_size = mau(n).size()
  max_size = 2*ceiling(log₂(n))

if max_size < mau_size
  // bad size
```
With the exception of finding the minimal additive upsequence for n, all these operations take constant time.
Many people offered up n - 1 as an upper bound, which is correct - any upsequence with more than n - 1 numbers is clearly wrong - but fails to catch upsequences with a size between the log and linear bound.
Provide a worst-case asymptotic analysis for the following code
```
for i = intvec.end() - 1; i != intvec.begin(); --i
  j = i - 1;

  do found = find(intvec.begin(), j + 1, *i - *j) != (j + 1);
  while (!found and (j-- != intvec.begin()));
```
You may not assume anything about the order of the integers stored in intvec; otherwise, make sure you clearly state the assumptions you used in your analysis.
Start by replacing all basic executions with their asymptotic estimates, which, in this case, are all constant:
```
for i = O(1); O(1); O(1)
  O(1)

  do found = find(O(1), O(1), O(1)) != O(1);
  while O(1)
```
In the worst case, when *i - *j isn't in intvec, find() does O(n) work, where intvec contains n elements. This gives
```
for i = O(1); O(1); O(1)
  O(1)

  do O(n) + O(1) = O(n)
  while O(1)
```
The do-while iterates O(n) times, leading to
```
for i = O(1); O(1); O(1)
  O(1)
  O(n)*(O(1) + O(n)) = O(n)*O(n) = O(n²)
```
The sequence rule gives
```
for i = O(1); O(1); O(1)
  O(1) + O(n²) = O(n²)
```
The outer loop iterates O(n) times, giving a final estimate of
```
O(n)*(O(1) + O(1) + O(1) + O(n²)) = O(n)*O(n²) = O(n³)
```
Most people either knew how to analyze this code or they didn't.
A colleague of yours is implementing a drawing program using subtype polymorphism:
```
struct shape {
  virtual void draw(void) const { 
    std::cerr << "shape can't draw!\n";
    }
  // whatever
  };

struct square : shape {
  void draw(void) const {
    // draw a square.
    }
  // whatever.
  };
```
Cleverly exploiting subtype polymorphism, your colleague represents a drawing as a list of figures
```
typedef std::list<shape>   Drawing;
typedef Drawing::iterator drawing_iter;
```
and draws a figure by iterating down the list, drawing each element:
```
void show_drawing(const Drawing & drawing) {
  for (drawing_iter i = drawing.begin(); i != drawing.end(); i++)
    i->draw();
  }
```
Unfortunately, the only thing that appears when your colleague's code shows a drawing is shape can't draw!" on std-err. What is wrong with your colleague's code and how would you recommend your colleague properly use subtype polymorphism?
See Section 13.6.1 (page 249) in Koenig and Moo.
Very few people got this correct, with many people getting hung up on iterators, which had nothing to do with the answer.

Given the structs

struct red {
  void f(void) { ... }
  void g(void) { ... }
  };

struct white : red {
  void f(void) { ... }
  void g(void) { ... }
  };

struct blue : white {
  void f(void) { ... }
  void g(void) { ... }
  };

and the declarations

blue b;
white & w = b;
red & r = b;

describe the smallest set of member functions that have to be declared virtual to produce the following execution-time behavior:

r.f(); // calls red::f().
r.g(); // calls red::g().

w.f(); // calls white::f().
w.g(); // calls blue::f().

b.f(); // calls blue::f().
b.g(); // calls blue::g().

b's static and dynamic types are the same, which means we can't distinguish virtual from non-virtual member function calls with b. w's static (white) and dynamic (blue) types of are different. From the comments, w::f() maps to the static type and w::g() maps to the dynamic type. Finally, r's static (red) and dynamic (blue) types are different too, but both member-function calls map to the static type.

From the previous analysis, both red::f() and red::g() are non-virtual; white::g() is virtual and white::f() is non-virtual; and blue::f() can be either virtual or non-virtual. However, because the question asked for the minimal set of virtual functions, blue::f() should be non-virtual.

Many people got this wrong by forgetting the virtual flip-flop and making blue's member functions virtual, which isn't helpful because it's a variable's static type that determines whether or not a member function is virtual.

This page last modified on 18 December 2002.