sort() function?
The predicate defines a less-than comparison for types for which the usual
less-than operator < isn't defined. Providing an explicit predicate to
sort() as a comparison operator allows sort() work with containers
containing values of arbitrary type, as long as a less-than comparison can be
defined for the type.
This was a straightforward question - either you read it and understood it or you didn't. A number or people managed to answer without once mentioning "predicate"; they didn't do well on this question.
int x, count, sum;
// ???
while (cin >> x) {
++count;
sum += x;
}
// ???
and use your invariant to document the code at the ??? locations. Don't
forget to initialize the local variables properly so the invariant is initially
true.
The purpose of an invariant is to describe the essence of what a loop does without becoming involved in a lot of the details. After looking at the given loop for a few minutes, it seems that
sum contains the sum of the first count elements in cin.
describes the loop's function well. Initially, setting count and sum
to zero makes the invariant true (because x isn't mentioned in the
invariant, it doesn't need an initial value). One iteration through the loop
preserves the invariant because it removes an integer from cin, adds it to
sum and increases count by one. At loop termination, the invariant is
still true and we have
sum contains the sum of the first count elements in cin and
cin is empty.
Notice that, as a bonus, count contains the number of elements that were
in cin before the loop began executing.
A good test for invariants is connectedness with the loop it documents. If you make a non-trivial change to the loop, you should also have to change the invariant too. If you can leave the invariant alone after changing the loop, then you probably don't have a good invaiant.
For example, a number of people gave "sum is an integer" or similar
as an invariant. While this is an invariant, it doesn't document the loop well
because I can reduce the loop to while (cin >> x) { } and the invariant
would still be true.
Write a set of test cases that determine in which direction an optimizer works on statement blocks. Your test cases should be able to distinguish between a correctly functioning but backwards optimizer and a broken optimizer.
Be sure to include the input statement blocks, the expected output statement blocks, and a description of how the test works.
This test can be done with a single test case. The input statement block is
C = 1 C = C * 3 C = 2
An optimizer that works forwards from the first to the last statement in a block will apply one instance of constant folding and one instance of compile-time expression evaluation to produce the output block
C = 1 C = 3 C = 2
An optimizer that works backwards from the last to the first statement in a block applies the same optimizations but produces the output block
C = 1 C = 6 C = 2
The test case
C = 1 C = C * 3
doesn't work as well as the previous test case because a broken but forward-moving optimizer could produce the same results as a correct but backward-moving optimizer.
A, B, and C are all related to one another. The
following code
int main() {
try { throw new A(); }
catch (A*) { cout << "caught an A*.\n"; }
catch (C*) { cout << "caught a C*.\n"; }
catch (B*) { cout << "caught a B*.\n"; }
try { throw new B(); }
catch (A*) { cout << "caught an A*.\n"; }
catch (C*) { cout << "caught a C*.\n"; }
catch (B*) { cout << "caught a B*.\n"; }
try { throw new C(); }
catch (A*) { cout << "caught an A*.\n"; }
catch (C*) { cout << "caught a C*.\n"; }
catch (B*) { cout << "caught a B*.\n"; }
cout << "\n";
try { throw new A(); }
catch (B*) { cout << "caught a B*.\n"; }
catch (C*) { cout << "caught a C*.\n"; }
catch (A*) { cout << "caught an A*.\n"; }
try { throw new B(); }
catch (B*) { cout << "caught a B*.\n"; }
catch (C*) { cout << "caught a C*.\n"; }
catch (A*) { cout << "caught an A*.\n"; }
try { throw new C(); }
catch (B*) { cout << "caught a B*.\n"; }
catch (C*) { cout << "caught a C*.\n"; }
catch (A*) { cout << "caught an A*.\n"; }
}
produces the following output
caught an A*. caught a C*. caught a C*. caught a C*. caught a B*. caught a C*.
What is the parent-child relation between the classes A, B, and
C? Explain.
The first try statement tells us nothing because it throws an A* which is
caught by the A* block.
The second try statement throws a B* which is caught by the C* block.
This tells us that B must be a child of C. However, we also now know
that A is not a parent of B because, if it were, then the B*
would have been caught by the A* block, which it wasn't.
The third try statement throws a C* which is caught by the C* block.
No new information here, except, again, that A can't be a parent of C
because it would have caught the C* if it were. (Actually, the second try
statement already told us this: C is a parent of B and A can't
be a parent of B. However, if A was a parent of C, then it
would also be a parent of B, which it can't be. So, A can't be a
parent of C either. At this point we can stop, because we know that all
three classes are related, and it must be that C is the parent of both
A and B with A and B being siblings.)
The fourth try statement throws an A*, which is caught by C* block:
A is a child of C. But also B is not a parent of A because
otherwise the B* block would have caught the thrown A*. At this
point we can stop again because the second try statement told us that A
can't be B's parent and this statement tells us that B can't be
A's parent. Because all three classes are related, it must be that A
and B have C as a parent and A and B are siblings.
The fifth try statement throws a B*, which is caught by the B*
block. Nothing new here.
The sixth try statement throws a C*, which is caught by the C* block,
confirming that except that B can't be a parent of C, which agrees
with our previous discovery
This page last modified on 21 February 2002.