CS 509 Test 1

CS 509, Advanced Programming II

Spring 2002 - Test 1

While running your portfolio management program with a particular three-year sequence of stock prices as input, you notice that the final portfolio managed by Strategy C has the ideal 50-30-20 value percentages while the final portfolio managed by Strategy S has value percentages that are different from the ideal. What can you conclude about the particular three-year stock-price sequence used as input?
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. Eventually, you would expect 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 (subject to particular share prices).
Even though you observe the no differences in actual-ideal value percentages for portfolio C, the number of shares in the portfolio is growing. Because the differences are always covered, it must be that the stock prices are not changing at all, or are changing in small amounts (relative to total share price) from month to month. If the stock prices weren't changing, then portfolio S would also be correct, so the most likely conclusion is the the month-to-month change in share prices is small.
A lot of people tried to answer this question by speculating about the differences in actual-ideal value percentages, but the question clearly asks you to characterize the stock prices used as input.
Develop a loop invariant for the code
```
void f(char a[], int n) {

  int i;

  i = 0;

  // ???

  while (i < n) {
    if (vowel(a[i])) a[i] = ' ';
    i++;
    }

  // ???
  }
```
and use the invariant to document the code at the two locations indicated by ???.
This question was messed up on the original test, so I'll answer the corrected question shown above and then adjust the answer for the one on the original test.
i scans through the entire array, so it's not too hard to figure out what i is used for. Each element is compared to the vowels and, if it's a vowel, is changed to a blank. When the loop terminates, then i equals n.
The initial invariant would be
all vowels in a[0..i-1] have been turned into blanks.
After the loop ends, the invariant is still true, and also i equals n, or
all vowels in a have been turned into blanks.

The problem with the original question was that i was initialized to 1, not 0. This changes the invariants to
all vowels in a[1..i-1] have been turned into blanks.
and
all vowels in a except possibly the one in a[0] have been turned into blanks.
A number of people got close to the correct answer by providing an invariant along the lines of "some portion of a doesn't contain vowels," which is correct, but doesn't quite capture what the loop's doing. A number of 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.
Explain the benefits of collapsing tests.
There are two benefits of collapsing tests. The first is that a set of mutually exclusive, exhaustive tests can be reduced by one, because if none of other tests are true, then the missing one must be true. This is particularly useful when there two tests involved, as there are when true-false decisions are required.
The other benefit of collapsing tests is the ability to extract out common code from both branches of the decisions that have been collapsed.
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. I needed to see something even remotely indicative of having read this section; generic observations about making code debuggable or understandable didn't cut it.
Koenig and Moo show how to implement a for loop using a while loop. Show how to implement a while loop by using a for loop.
The code
```
while ( test ) 
  body
```
can be implemented as
```
for ( ; test ; ) 
  body
```
This one I though was a gimme, but it turned out to be a gotcha. A lot of people answered this question with the following reasoning:
Humm, I can implement the for loop
```
for ( init ; test ; change )
  body
```
using the while loop
```
init
while ( test ) {
  body
  change
  }
```
so clearly I can implement the while loop
```
init
while ( test ) {
  body
  change
  }
```
using the for loop
```
for ( init ; test ; change )
  body
```
QED.
The problem with this reasoning is that a while loop doesn't look like this:
```
init
while ( test ) {
  body
  change
  }
```
it looks like this:
```
while ( test )
  body
```

This page last modified on 7 February 2002.