CS 509 Test 6

CS 509, Advanced Programming II

Fall 2002 - Test 6

Class A has pointers as instance variables, and so obeys the Rule of Three. Suppose class B itself contains no pointer instance variables, but does contain instances variables of type class A. Does class B have to obey the Rule of Three? Explain.
Class B does not have to follow the Rule of Three. The compiler will generate code to call the assignment, copy constructor, and destructor for the instances of A from within the generated assignment, copy constructor, and destructor created for B.
Many people confused inheritance with inclusion, arguing that B was a child of, and inherited from, A. This is wrong, but close to the truth, although inheritance has nothing to do with it.
Can you make a class's copy constructor explicit? If so, explain what other changes you would have to make to the code using the class if you made its copy constructor explicit. If you can't make the copy constructor explicit, explain why not.
Because the copy constructor is a single-parameter constructor, it is a cast constructor and can be declared explicit. If you made the copy constructor explicit, you would have to change your code by replacing all implicit calls to the copy constructor by explicit ones, as in changing
```
Box b1;
Box b2 = b1;
```
to
```
Box b1;
Box b2 = Box(b1);
```
You would also have to remove all class instances used as function parameters and return values because the compiler needs to make implicit copies of the instances to pass them into or out of functions, which it cannot do when the copy constructor is explicit.
The answers were split evenly between the yesses and the nos, but most people who correctly argued yes didn't understand the consiquence of making the copy constructor explicit.
Provide a worst-case run-time asymptotic estimate of the code
```
mult(n, y)

  z = 0

  while n > 1
    if odd(n)
      z = z + y
    n = n/2
    y = 2*y

  return y + z
```
in terms of the value stored in n. Carefully describe your analysis steps. For full credit your analysis should be tight with respect to the usual family of estimate curves; that is, for full credit, your analysis should give the curve from the usual family of curves that is as close to the actual run-time behavior as possible.
All basic statements can reasonably be assumed have constant running time, leading to
```
mult(n, y)

  O(1)

  while n > 1
    if odd(n)
      O(1)
    O(1)
    O(1)

  O(1)
```
An application of the sequence rule gives
```
mult(n, y)

  O(1)

  while n > 1
    if odd(n)
      O(1)
    O(1) + O(1) = O(1)

  O(1)
```
Testing if n is odd can be done either by (n % 2) == 1 or by (n & 1) == 1, both of which take constant time. The if rule (with a missing else) gives
```
mult(n, y)

  O(1)

  while n > 1
    O(1) + O(1) = O(1)
    O(1)

  O(1)
```
Another application of the sequence rule.
```
mult(n, y)

  O(1)

  while n > 1
    O(1) + O(1) = O(1)

  O(1)
```
The while guard executes in constant time, but the number of loops is not bounded by a constant. The loop iterates as long as n is larger than 1, and each iteration of the loop reduces n by half. This means the bounds on the loop iterations is given by j, where j is the smallest value such that n/2^j <= 1 (or n <= 2^j). Taking the log of each side give j = log n, and the loop iterations are bounded from above by log n. The while rule gives
```
mult(n, y)

  O(1)

  O(log n)*(O(1) + O(1)) = O(log n)

  O(1)
```
A final application of the sequence rule gives
```
mult(n, y)

  O(1) + O(log n) + O(1) = O(log n)
```
mult() runs in time O(log n), and because the usual curve family has no curves between log n and constant, this is a tight bound.
Many people came up with an O(n) bound, which was not tight. For some reason, some people derived an O(n²) bound by assigning the if statement an O(n), which is perhaps confusing the number of times the if is executed with the time it takes to execute the if once.
The example tangram puzzle given in the assignment is a square with sides of length i for some integer i (4 in the assignment). A colleague of yours, observing this, believes that the tangram solver should compute the area of the outline input and reject as impossible any outline not occupying i² square units. Any outline not rejected then has a solution, which the solver goes on to find.
Unfortunately, your colleague's reasoning is flawed. Give a test case that demonstrates the problem with your colleague's solver. Not only should you describe the input outline, but you should also describe the flaw in your colleague's reasoning and how your test case exploits the flaw.
The flaw crept in when your colleague failed to observe that the square puzzle required a tan (the large triangle) with a sides of length no smaller than i/root(2) (2*root(2) in the assignment). For any i greater than 1, the input
0 0 0 i² 1 i² 1 0
has the proper area but cannot possibly contain a large triangle tan.
Some people worked this argument in the other direction, arguing that an outline with too big an area couldn't be covered with the tiles. This is a less satisfactory answer because it ignores scaling, but the idea is going in the right direction.

This page last modified on 5 December 2002.