CS 509 Test 3

CS 509, Advanced Programming II

Spring 2004 - Test 3

A colleague of yours has a vector full of pointers to widgets, and wishes to remove all those widgets that have failed. Towards that end, you colleague has implemented the predicate
```
bool failed(widget * wp) {
  return wp->failed();
  }
```
and uses it in a call to std::remove_if():
```
std::remove_if(widgets.begin(), widgets.end(), failed);
```
(This is not all your colleague has done to remove failed widgets, but this is all we need to know for this question.) What do you think of your colleagues scheme? Explain your answer.
Your colleague's scheme is terrible, because it unrecoverable clobbers pointers, leading to garbage. As Koenig and Moo point out on page 118, remove() overwrites values rather than shuffling them around; partition() would have been a more appropriate choice for your colleague to make.
Most answers missed the important point that remove() would clobber pointers, creating garbage; otherwise the answers brought up correct, if not particularly relevant points.
Koenig and Moo use maps to implement both a cross-reference generator and a random sentence generator. In which (if either) of the two algorithms developed would it be easier to replace the map with a vector? Explain your answer. Your answer to this question need not deal with performance issues, but you may consider them if you like.
The index for a cross-reference generator can be easily inverted to a vector by treating the line-number as the index and the words as the elements (actually a vector of words). This is harder to do for the sentence generator problem because both sides (the index and element values) are strings.
This was a fuzzy question, answerable in many different ways. Some of the answers mentioned performance issues, which was fine although no specific (absolute) performance requirements were given.
A colleague of yours defined a less-than operator over two points as
```
bool point::operator < (const point & p)
  return (x < p.x) or (y < p.y)
```
Is this definition of less-than a trichotomy? Explain. Assume the coordinates are integers.
If your colleague's less-than predicate is a trichotomy, then given any two points p₁ and p₂, exactly one of p₁ < p₂, p₂ < p₁, or p₁ = p₂ must be true. However given p₁ = (1, 2) and p₂ = (2, 1), then both p₁ < p₂ and p₂ < p₁ are true, which means that your colleague's less-than predicate is not a trichomoty.
Most of the answers to this were correct, the ones that weren't were wrong.
Just as many people forget that every argument has two sides, so do people forget that every polygon edge has two sides. Describe a test case that determines if a solution to the third programming assignment can find the two polygons potentially associated with a polygon edge.
Your test case should require no more than six points; you don't have to include exact coordinates, a picture with an explanation will be enough.
The question pretty much answers itself: two triangles sharing an edge does the trick.
Most answers to this question were much more complicated than they needed to be, but where otherwise, more or less, correct.

This page last modified on 17 March 2004.