CS 509 Test 2

CS 509, Advanced Programming II

Fall 2003 - Test 2

Koenig and Moo use an exception to indicate an error condition in their median-finding procedure. Describe two alternate ways they could achieve the same effect without using exceptions.
Koenig and Moo's median() code (Section 4.1.1, page 53) throws an exception if the vector of grades is empty. On alternative to an exception is to return an error indication and pass the median as a reference parameter:
```
bool median(std::vector grades, double & mdn);
```
(you could also return the median and pass the error indication as a reference).
Other alternatives are to use a global return value (much as Unix does with the errno global), and to pass in an error function to be called in case of error.
Most people got this right. The interesting cases where those answers that print an error message, which didn't have the effect of Koenig and Moo's routine at all, and the couple of answers that involved assertions about the number of grades. This is, in my opinion, a fine answer, but not really equivalent to the effect of Koenig and Moo's procedure.
Explain, for each of the following vector operations, whether or not they could cause iterator invalidation:
1. v.size()
2. v.resize()
3. v.capacity()
4. v.reserve()
v.size() returns the number of elements in v and makes no changes to v itself; it doesn't invalidate any iterators.
v.resize(n) make sure that v has n elements. If this requires removing elements from v then any iterators to the elements removed will be invalidated. If this requires adding elements to v, then v may need to be re-allocated, which would invalidate all iterators into v.
v.capacity() returns the total number of elements that can be stored in v without reallocation. v.capacity() makes no changes to v, and so invalidates no iterators into v.
v.reserve(n) makes sure that v is capable of holding at least n elements without needing to be resized. Because v.reserve() itself may cause a reallocation in v, it may invalidate all iterators into v.
Nobody got this completely wrong; the biggest problem was confusing size() and resize() (oddly enough, most people kept capacity() and reserve() straight).
Develop a test case for your second programming assignment in which the given path does not have a unique minimal compressed path. Your test case should consists of a graph and a path; you may draw both, there is no need to use the input format required by the assignment.
This question was my free gift to you: it's taken directly from the assignment page (I put it in there as a place holder and forgot to change it).
However, a number of people got this question wrong, mostly because they became confused about unique minimal compressed paths and minimal compressed paths. Given any path, there always exists a minimal path: the path itself.
Place the following three words in (increasing) lexicographic order: "cats", " cat", and "cat ". In all cases the space character is a space, not a tab, newline, or any other space character.
Make sure you explain why you placed the words in the order you did (that is, describe the rules you used).
" cat" is less than "cats" because the space character ' ' is less than the character 'c'. For similar reasons, " cat" is less than "cat ".
"cat ". is less than "cats" because the space character ' ' is less than the character 's', and all prior characters both words are the same.
The final lexicographic order is " cat", "cat ", and "cats".
Another gimme. Where points were lost, they were lost due to lack of explanation. A number of people were unsure if a space is ordered before or after letters, but as long as an understanding of lexicographic ordering came through, the actual order didn't matter.

This page last modified on 19 October 2003.