CS 503 Quiz 7

CS 503, Advanced Programming I

Quiz 7, 27 April 2006

A colleague of yours, disappointed that squares weren't polymorphic children of rectangles, tries to patch things up by suggesting that rectangles are a polymorphic children of squares. Evaluate your colleague's suggestion with respect to the Liskov-Wing Substitution Principle.
For a rectangle to be a child of squares under the Liskov-Wing Substitution Principle a rectangle instance would have to behave as a square instance would in any context requiring a square instance.
The function
```
test(square & sq) 
  sq.set_width(3)
  assert(9 == sq.area())
  sq.set_height(4)
  assert(16 == sq.area())
```
is an example of a context in which a square instance behaves one way and a rectangle instance behaves another: the second assertion fails if cd(sq) refers to a rectangle instance because sq.area() returns 12 ≠ 16. (The first assertion may also fail, depending on the value of sq.height.)
In Design by Contract terms, having rectangles be children of squares leads to rectangle::set_width() providing less benefit than does square::set_width(): square::set_width() sets both height and width to the given value while rectangle::set_width() sets only the width (you can make a similar argument for set_height()). In other words, rectangle::set_width()'s postcondition is weaker than square::set_width()'s postcondition, which violates the Design by Contract requirement that a child's postcondition be no weaker than the parent's corresponding postcondition.
During the lecture on Design by Contract I pointed out that the postcondition
```
for all i, j such that 0 ≤ i < j < N : a[i] ≤ a[j]
```
was not a good postcondition for the sort procedure
```
void sort(T a[], unsigned N)
```
Explain why. Hint: the postcondition's too weak.
The problem with the given postcondition is that the following procedure satisfies it:
```
void sort(T a[], unsigned n)
  for (i = 0; i < n; i++)
    a[i] = T()
```
but can hardly be considered a successful sort procedure. As we discussed in the Sorting Section, a sort is a permutation having the property given in the postcondition. The given postcondition should be strengthened to include the requirement that a is a permutation:
```
for all i, j such that 0 ≤ i < j < N : a[i] ≤ a[j]
∧ new a = permutation(old a)
```
Explain the object-oriented features that are particularly useful when designing and implementing heterogeneous data structures.
See Nyhoff Section 14.6.
The graph G has an order distance of 0. What is the maximum number of edges G can contain?
An 0 order distance for a graph means that there exists a linear ordering of the vertices such that every vertex is immediately adjacent to its neighbor in the graph, which means that edges can only connect adjacent vertices. If there are V vertices, there can be at most V - 1 edges.

This page last modified on 1 May 2006.