CS 509 Test 1

CS 509, Advanced Programming II

Spring 2002 - Test 1

Which of the following code fragments can benefit from collapsing tests? For those that can, show how; for those that can't explain why.

a) if (a < b) {
     min_val = a;
     min = 'a';
     }
   else if (min == 'b') {
     min_val = b;
     min = 'b';
     }
   else if (a >= b) {
     min_val = 0;
     min = 'a'
     }

b) if (!isalpha(ch) && !isdigit(ch)) {
     ch = '\t';
     spaces++;
     }
   else if (isalpha(ch)) {
     ch = '!';
     chars++
     }
   else if (isdigit(ch)) {
     ch = '!';
     digits++;
     }

c) if (i % 3 == 0) {
     threes++;
     total = ones + twos + threes;
     i--;
     }
   else if (i % 3 == 1) {
     ones++;
     total = ones + twos + threes;
     cout << "total = " << total << "\n";
     }
   else if (i % 3 == 2) {
     twos++;
     i += twos;
     cout << "done\n";
     }

There are two benefits to collapsing tests: you get to eliminate a redundant test, and you get to factor out common code. Code fragment a can benefit:

if (min == 'b') {
  min_val = b;
  min = 'b';
  }
else {
  if (a < b)
    min_val = a;
  else 
    min_val = 0;
  min = 'a';
  }

Code fragment b can also benefit from collapsing tests:

if (!isalpha(ch) && !isdigit(ch)) {
  ch = '\t';
  spaces++;
  }
else {
  ch = '!';
  if (isalpha(ch))
    chars++;
  else 
    digits++;
  }

Code fragment c, however, can't benefit. Although one of the three tests can be eliminated (anything mod 3 is either 0, 1, or 2) the common code in the first and second branches can't be factored out because either other code depends on it (the second branch), or it depends on other code (the first branch).

This is Section 2.5.3 from the Koenig and Moo. I warned you the first day of class that I discovered the 509 students last semester didn't do too well on these kinds of questions, which ensures they'll re-appear on tests this semester.

The description of collapsing tests is not that easy to understand, but all I was looking for was something even remotely indicative of having read this section; seemingly random observations about this assignment or that test didn't cut it.

Koenig and Moo show how to implement a for loop using a while loop. Show how to implement a for loop by using a do-while loop.
The tricky thing about the do-while loop is that it always executes its body at least once. Because a for loop need not execute its body at all, the do-while has to be protected by an if. The code
```
for ( init ; check ; change )
  body
```
is equivalent to
```
init
if ( check ) {
  do {
    body
    change
    }
  while ( check )
  }
```
I though this one was a gimme, but it turned out to be a gotcha. Almost everybody that came reasonably close forgot about the always-loop-once problem; a couple of people gave me the wrong answer and then correctly described while the answer was wrong.
A colleague of yours is watching your portfolio program in operation and observes that the portfolio managed by Strategy C starts out matching the ideal 50-30-20 value percentages exactly, but eventually the Strategy C portfolio percentages begin to differ from the ideal percentages, and the more months the program processes, the larger the difference becomes.
Given the increasing difference between actual and ideal portfolio percentages, your colleague concludes that your implementation of Strategy C is incorrect. Do you believe your colleague's conclusion is justified? Explain.
Without specific knowledge of the input data, your colleague is jumping to conclusions. The longer the portfolio program runs, the more stock gets added to the portfolio, or alternatively, the larger the total value of each stock becomes (in general; this depends on share price too). Eventually, the total value of each stock grows so large that even 1% of its value is larger than the monthly amount to spend; this is particularly the case with X, which should make up 50% of the total portfolio value. Once the monthly amount can't cover the difference in the actual-ideal value percentages, the differences can only grow (again, subject to particular share prices). This is why Strategy C started off so well: the differences between the actual-ideal value percentages could be covered by the monthly amount.
This was actually a question I asked myself while I was testing my solution for the first assignment: Was it reasonable that Portfolio C was always so off the ideal percentages? After poking around a bit I concluded it was for the reason given above.
Develop a loop invariant for the code
```
void f(int a[], int n) {
  int i, j;

  j = 0
  i = 1;

  // ???

  while (i < n) {
    if (odd(a[i])) {
      int t = a[j];
      a[j++] = a[i];
      a[i] = t;
      }
    i++
    }

  // ???
  }
```
and use the invariant to document the code at the two locations indicated by ???.
i scans through the entire array, so it's not too hard to figure out what i is used for. j is a bit more tricky. Initially, j points to the first element of the array, and is advanced when the element it indexes is swapped with an odd number. It's tempting to say that the array segment a[0..j] are odd numbers from a. Unfortunately, that isn't initially true, because there's no test to see if a[0] is odd. However, a slight adjustment is true: the array segment a[0..j-1] are odd numbers from a, assuming a right index to the left of the left index implies the empty sequence, which it usually does.
A number of people managed to get "odd" into an invariant, but then didn't bother to relate it to the array. Other people gave invariants such as "n doesn't change" or "i <= n," which are also correct, but even further off the mark than the previous invariant. Remember: an invariant should capture exactly the behavior of the loop it is describing.

This page last modified on 7 February 2002.