CS 509 Test 6

CS 509, Advanced Programming II

Spring 2003 - Test 6

Construct a test case to demonstrate that a unit calculator handles unit cancellation correctly.
The simplest test case is
```
a : m
a = 1m / 1m
```
which should output
```
a 1
```
The people who got this wrong did so by not providing an example of cancellation. People who got this right produced way complicated test cases.
Provide an asymptotic analysis of the following code:
```
i = 0
while i < n - 1
  j = i
  while j < n
    if a[i] < a[j]
      swap(a[i], a[j])
    j++
  i++
```
Replacing the basic statements, all of which are constant, gives:
```
O(1)
while i < n - 1
  O(1)
  while j < n
    if a[i] < a[j]
      O(1)
    O(1)
  O(1)
```
Thinking about how swap() could be implemented suggests that it's a constant-time operation.
The if guard is constant, and the if-rule reduces the if statement to a constant.
```
O(1)
while i < n - 1
  O(1)
  while j < n
    O(1) + O(1) = max(O(1), O(1)) = O(1)
    O(1)
  O(1)
```
The sequence rule reduces the inner-loop body to a constant estimate.
```
O(1)
while i < n - 1
  O(1)
  while j < n
    O(1) + O(1) = max(O(1), O(1)) = O(1)
  O(1)
```
The inner-loop guard has a constant estimate, and the iteration count is bounded by O(n). The loop-rule produces an O(n) estimate.
```
O(1)
while i < n - 1
  O(1)
  O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n)
  O(1)
```
Another application of the sequence rule, this one for the remaining loop body.
```
O(1)
while i < n - 1
  O(1) + O(n) + O(1) = max(O(1), O(n)) = O(n)
```
Another loop with a constant guard and an O(n) loop bound, but with an O(n) loop body.
```
O(1)
O(n)*(O(1) + O(n)) = O(n)*O(n) = O(n²)
```
One final application of the sequence rule gives the overall estimate.
```
O(1) + O(n²) = max(O(1), O(n²)) = O(n²)
```
Suppose a class defines no explicit constructors, but every instance of the class is properly initialized. Does the class need to follow the rule of three?
The rule of three is required when a class contains explicit pointers. The default initialization for a pointer variable is to do nothing. A pointer that is default initialized points to garbage (unless the variable just happens to contain zero), which is not properly initialized. Because every class instance is properly initialized under the defaults, the class must not contain any explicit pointers. Without explicit pointers, the class need not obey the rule of three.
The trick to this question was that it required two steps:
1. Correct instantiation -> no pointers.
2. No pointers -> no rule of three.
Most answers got the second part, but without providing the first part.
Suppose class C has a non-friend stream extraction operator that can successfully read instances of C from an input stream. What can you say about member fields of class C?
The member fields of the class C must be publicly accessible, either directly or by access member functions (another possibility, mentioned by one of you, is that C contains no member functions at all).
This question is straight out of Koenig and Moo (Section 12.3.2). A lot of people tried to answer using the rule of three, which has no relevance to the question.

This page last modified on 16 April 2003.