CS 509 Test 1

CS 509, Advanced Programming II

Fall 2003 - Test 1

A colleague of yours believes that a document can be unshredded by sorting the shreds according to the following algorithm:
1. Order each edge by increasing interval values.
2. Order each shred by the lowest interval value on either edge.
Describe a shred set that will demonstrate your colleague's algorithm is incorrect. Don't forget to describe how your colleague's algorithm fails on your test shred set.
The folly of our colleague's algorithm can be demonstrated in with three input shreds:
```
1 2
3 4

3 4
3 4

3 4
1 5
```
The ordering given is correct, but you're colleague's algorithm re-orders them into the incorrect sequence
```
1 2
3 4

3 4
1 5

3 4
3 4
```
Many people gave answers with silly mistakes. You can't show your colleague's algorithm is wrong using only one or two shreds, which, no matter how they're ordered, are always correct. Several people used invalid shreds, either with overlapping intervals or not making a document, for a test, which can't demonstrate your colleague's algorithm is wrong because you don't expect it to work for invalid shreds.
C++ has two kinds of comment delimiters, one of which is free form and the other of which isn't. Which is which? Explain your reasoning.
"Free format" refers to the ability to add extra space characters and not change the meaning of the program.
The two comment delimiters in C++ are // and (/* */). The /* */ comment delimiter is free formant: you can insert space characters, including new-lines anywhere, within the comment and nothing significant about the program changes.
The // comment delimiter is not free form because it ends at the first new-line; adding a new-line to the middle of a // comment changes the meaning of the program because now all the comment after the inserted new-line becomes part of the program text.
Many people failed to indicate whether or not each both comments were free form. Most commonly, they would indicate that /* */ comments are free form and then say nothing about // comments.
Given the declarations
```
std::string bang = "!";
std::string msg = "hello " + "world" + bang;
```
insert as many parentheses as necessary to eliminate any errors that may occur when the declarations are compiled. If you believe the declarations are correct as given, write "none". Explain your answer.
The expression "hello " + "world" causes a compilation error because the plus operator isn't defined when both operands are pointers. Adding parentheses around "world" + bang
```
std::string bang = "!";
std::string msg = "hello " + ("world" + bang);
```
The type of the value represented by the expression ("world" + bang) is a string, which can then be catenated to "hello ".
Way too many people got this wrong. It's based on Exercise 1.2 from Koenig and Moo. Several people confused parenthesis () with braces {}.
The code
```
for (int r = 0; r != rows; ++r)
  // write a row
```
relies on an important assumption to operate correctly. Explain the assumption and rewrite the code to include the assumption in the form of an assertion.
The given code fails to terminate if rows is less than zero: r will always be unequal to rows. rows must be assumed to be non-negative for this code to work properly. The required assertion is
```
assert(rows >= 0);

for (int r = 0; r != rows; ++r)
  // write a row
```
Most people got this right, although many people put the assertion in the body of the for
```
for (int r = 0; r != rows; ++r)
  assert(rows >= 0);
  // write a row
```
which is not wrong, but not completely right either.

This page last modified on 30 September 2003.