CS 509 Test 3

CS 509, Advanced Programming II

Spring 2003 - Test 3

A colleague of yours defined a less-than operator over two cards as
```
bool card::operator < (const card & c) 
  return (rank < c.rank) or (suit < c.suit)
```
Is this definition of less-than a trichotomy? Explain. Assume the ranks are ordered as
```
A < 2 < ... < 9 < 10 < J < Q < K
```
and the suits are ordered as
```
club < diamond < heart < spade
```
This definition of less-than is a trichotomy if (and only if) exactly one of a < b, b < a or a == b is true for any cards a and b.
Consider the cards 2S and KC. Because A < K, your colleague's definition has 2S < KC. Also, because C < S, then KC < 2S. Because both 2S < KC and KC < 2S are true for the same pair of cards, your colleague's definition of less-than is not a trichotomy.
Most people forgot what a trichotomy was, and so didn't do too well with this question.
A colleague of yours believes it's impossible to determine whether a valid tableau is correct by comparing at a single card in the tableau with a single card in the hand. A valid tableau is one that contains all and only the cards in hand. Prove your colleague wrong by showing a test case containing an valid tableau that can be shown to be incorrect by comparing one card in the tableau to one card in the hand; be sure to explain the card comparison too.
You may use the small deck of cards 3S, 4S, 3H, 4H, 3D, 4D, 3C, 4C to build your test case. Don't forget to explain what the card comparison is.
Note that your colleague is claiming that there exists no valid, incorrect tableau that can be detected with one card comparison. You are to contradict your colleague by presenting such a valid, incorrect tableau and describing the card comparison.
If we could find an invariant about correct tableaus, we could prove your colleague wrong by making the card test be the invariant. A tableau for which the invariant fails cannot possibly be a correct tableau.
It seems hard to find an invariant when many possible cards in a tableau can be moving around in many possible ways. But all the possible cards and all their possible moves do have on thing in common: the cards all end up to the left of where they were before the move. And that's the key to the invariant: the leftmost card can't move at all, because there's no left to move to.
The invariant is "a correct pile always has the first card in the hand at the bottom of the first (leftmost) pile". The one-card check is then to compare the bottom card of the left-most pile against the top card of the hand; if they're different, the tableau can't possibly be correct.
Here's a test case:
```
3S, 4S, 3H, 4H, 3D, 4D, 3C, 4C
3S 4S
4H 3H
4D 3D
4C 3C
```
In this tableau the bottom card on the leftmost pile (4S) does not match the first card in the hand (3S) and so this tableau can't possibly be correct.
Notice the tableau isn't necessarily correct if the two cards match; the tableau could be messed up somewhere else. However, this has nothing to do with your colleague's claim, which is that it is impossible to dismiss any tableau with just one card comparison.
Many people either didn't submit a test case or submitted a test case without explaining which two cards should be compared. There was also some confusion with the previous question, with some people claiming that, for example, 3S and 3C were equal cards.
Explain why the std::remove() generic algorithm is more efficient than the std::stable_partition() generic algorithm when run over the same data with the same tests.
See Koenig and Moo, pages 118 and 119. Essentially, remove() makes half the data movements than does stable_partition().
Way too many people fell into the mutating algorithm trap on this question, claiming that one or the other of the functions changes the size of the container, which isn't true for any generic algorithm (unassisted by iterator adaptors).
A colleague of your notes that the std::fill() generic algorithm is described as
```
void std::fill(ForwardIterator b, ForwardIterator e, const T & v)
```
(std::fill() fills all values in the iterator range (b, e) with the value v). After thinking about a straightforward implementation of std::fill(), your colleague believes the description is incorrect: e should be an input iterator and not a forward iterator.
Do you agree with your colleague? If so, explain why your colleague is right. If not, explain why your colleague is wrong.
The easiest way to solve this question is to consider how std::fill() is implemented:
```
void fill(b, e, v)
  while (b != e)
    *b++ = v
```
Your colleague's reasoning could have been along these lines: The l-value star operator means that b must be in the output-iterator category. The inequality operator means that b and e must be in the input-iterator category. Because b needs both input- and output-iterator operations, it must be a forward iterator, the least powerful iterator with the required operations.
You colleague's reasoning is correct as far as it goes; it just doesn't go far enough. What your colleague forgot is that both iterators must come from the same container for the call to fill() to be valid. If b has to be a forward iterator, then so does e because it comes from the same container as does b.
Nobody got this right (including me, the first time I though of this question). Most often people argued that fill() writes a value into the container element referenced by e, which is not how iterator ranges work in generic algorithms.

This page last modified on 22 April 2003.