CSE 331: ADTs practice

Question 1: Representation Invariants and Abstraction Functions

Here is a class Tally, with its specification in Javadoc comments. You may assume no arithmetic here ever overflows.

/**
 * A tally of the votes on a yes-or-no question:
 * how many yes votes and how many no votes have been cast.
 */
class Tally {
    private int total;   // RI: ...
    private int lead;    // AF(this) = ...

    /** @effects makes a tally with no votes cast */
    Tally() { total = 0; lead = 0; }

    /**
     * @modifies this
     * @effects records one yes vote
     */
    void yes() { total = total + 1; lead = lead + 1; }

    /**
     * @modifies this
     * @effects records one no vote
     */
    void no() { total = total + 1; lead = lead - 1; }

    /** @return the number of yes votes minus the number of no votes */
    int margin() { return lead; }

    /** @return the number of votes cast */
    int total() { return total; }
}

Part 1

For each claim, write in its box:

T if it is true of every Tally whenever no method of the class is running
F if not

	Answer
a. `0 <= total`
b. `-total <= lead and lead <= total`
c. `0 <= lead`
d. `total + lead` is even
e. `lead < total`
f. `total` is even

a. 0 <= total

Answer

Answer
T

True: the constructor makes it true, and each method keeps it true.

The constructor makes it true.

It sets total to 0, and 0 <= 0.

Each method keeps it true.

yes() and no() each add 1 to total, so it stays at least 0.
margin() and total() change no field.

The definition: Lecture 11's Representation invariants.

b. -total <= lead and lead <= total

Answer

Answer
T

True: the constructor makes it true, and each method keeps it true.

The constructor makes it true.

It sets total and lead to 0, so both halves read 0 <= 0.

Each method keeps it true.

yes() and no() each add 1 to total, so the range from -total to total grows by 1 at each end.
Each moves lead by 1, up or down, so lead stays in that range.
margin() and total() change no field.

The definition: Lecture 11's Representation invariants.

c. 0 <= lead

Answer

Answer
F

False: one call to no() on a new Tally breaks it.

A counterexample:

new Tally() sets total and lead to 0.
no() then makes total 1 and lead -1.
No method is running, and 0 <= -1 is false.

The definition: Lecture 11's Representation invariants.

d. total + lead is even

Answer

Answer
T

True: the constructor makes it true, and each method keeps it true.

The constructor makes it true.

It sets total and lead to 0, and 0 is even.

Each method keeps it true.

yes() adds 1 to each field, so total + lead grows by 2 and stays even.
no() adds 1 to total and takes 1 from lead, so total + lead stays the same.
margin() and total() change no field.

The definition: Lecture 11's Representation invariants.

e. lead < total

Answer

Answer
F

False: a new Tally breaks it.

A counterexample:

new Tally() sets total and lead to 0.
No method is running, and 0 < 0 is false.

The definition: Lecture 11's Representation invariants.

f. total is even

Answer

Answer
F

False: one vote breaks it.

A counterexample:

new Tally() sets total to 0.
yes() then makes total 1.
No method is running, and 1 is odd.

The definition: Lecture 11's Representation invariants.

Part 2

Which is the abstraction function? Write its letter in the box.

A. total yes votes and lead no votes
B. (total + lead) / 2 yes votes and (total - lead) / 2 no votes
C. lead yes votes and total - lead no votes
D. total / 2 yes votes and total / 2 no votes

	Answer
g. `AF(this) =`

g. AF(this) =

Answer

Answer
B

B: whatever votes were cast, it gives how many were yes and how many were no.

What the fields hold after y yes votes and n no votes:

total is y + n, since each vote adds 1 to it.
lead is y - n, since yes() adds 1 to it and no() takes 1 away.

Solve for the votes:

Adding the two, total + lead is 2 * y, so y = (total + lead) / 2.
Subtracting, total - lead is 2 * n, so n = (total - lead) / 2.
That is B.

One vote tells them apart:

After one no() on a new Tally, total is 1 and lead is -1: 0 yes votes and 1 no vote.
- A gives 1 yes vote and -1 no votes.
- B gives 0 yes votes and 1 no vote.
- C gives -1 yes votes and 2 no votes.
- D gives 0 yes votes and 0 no votes.

The definition: Lecture 11's Abstraction functions.

Question 2: A Set Represented by Booleans

Here is a class IntSet, with its specification in Javadoc comments. A new boolean array has every entry set to false. You may assume no arithmetic here ever overflows.

/** A set of integers from 0 (inclusive) to a fixed bound (exclusive). */
class IntSet {
    private boolean[] a;  // RI: ... AF(this) = ...
    private int size;

    /**
     * @requires 0 <= bound
     * @effects makes an empty set with the given bound
     */
    IntSet(int bound) { a = new boolean[bound]; size = 0; }

    /**
     * @requires 0 <= n and n < the bound
     * @modifies this
     * @effects adds n to the set, if absent
     */
    void add(int n) {
        if (!a[n]) { a[n] = true; size = size + 1; }
    }

    /**
     * @requires 0 <= n and n < the bound
     * @modifies this
     * @effects removes n from the set, if present
     */
    void remove(int n) {
        if (a[n]) { a[n] = false; size = size - 1; }
    }

    /** @return the number of integers in the set */
    int size() { return size; }
}

Part 1

Assume every call satisfies its precondition. For each claim, write in its box:

T if it is true of every IntSet whenever no method of the class is running
F if not

	Answer
a. `0 <= size <= a.length`
b. `size = a.length`
c. `size` is the number of indices `i` with `0 <= i < a.length` and `a[i] = true`
d. For every index `i` with `0 <= i < size`, `a[i] = true`
e. If `size = 0`, then `a.length = 0`
f. If `size = a.length`, then every entry of `a` is true

a. 0 <= size <= a.length

Answer

Answer
T

True: size counts the true entries, so it is between 0 and the number of entries.

The constructor makes every entry false and sets size to 0.
add increases size only when a false entry becomes true.
remove decreases size only when a true entry becomes false.
size() changes nothing.
An array has at least 0 and at most a.length true entries.

The definition: Lecture 11's Representation invariants.

b. size = a.length

Answer

Answer
F

False: the array's length is the bound, not the number of members.

A counterexample:

new IntSet(3) makes an empty set.
size is 0, but a.length is 3.
No method is running, and 0 = 3 is false.

The definition: Lecture 11's Representation invariants.

c. size is the number of indices i with 0 <= i < a.length and a[i] = true

Answer

Answer
T

True: every change to an entry has a matching change to size.

The constructor makes it true.

All entries are false and size is 0.

Each method keeps it true.

add(n) changes a false entry to true and increases size by 1. If the entry is already true, both stay the same.
remove(n) changes a true entry to false and decreases size by 1. If the entry is already false, both stay the same.
size() changes nothing.
Inside either mutator, the entry changes before size does. The claim is restored before the method returns.

The definition: Lecture 11's Representation invariants.

d. For every index i with 0 <= i < size, a[i] = true

Answer

Answer
F

False: members need not be the smallest integers below the bound.

A counterexample:

On new IntSet(3), call add(2).
The array is [false, false, true], and size is 1.
Index 0 satisfies 0 <= 0 < size, but a[0] is false.
The value of an integer determines its array index. The number of members does not determine their indices.

The definition: Lecture 11's Representation invariants.

e. If size = 0, then a.length = 0

Answer

Answer
F

False: an empty set can have a positive bound.

A counterexample:

On new IntSet(3), call add(2), then remove(2).
Every entry is false again, and size is 0.
Neither method replaces the array, so its length is still 3.

The definition: Lecture 11's Representation invariants.

f. If size = a.length, then every entry of a is true

Answer

Answer
T

True: if the number of true entries equals the length, no entry can be false.

size counts the true entries, as the constructor and mutators establish in row c.
A false entry would leave fewer than a.length true entries. That would contradict size = a.length.
When the length is 0, there are no entries that can be false, so the claim is true in that case too.

The definition: Lecture 11's Representation invariants.

Part 2

Which is the abstraction function? Write its letter in the box. In every option, the fixed bound is a.length and the members are:

A. All integers i with 0 <= i < a.length
B. All integers i with 0 <= i < a.length and a[i] = true
C. All integers i with 0 <= i < a.length and a[i] = false
D. All integers i with 0 <= i < size

	Answer
g. `AF(this) =`

g. AF(this) =

Answer

Answer
B

B: a true entry at index i means that i is a member.

Why the operations agree:

The constructor makes all entries false, representing no members.
add(n) makes a[n] true, so n is in the set afterward.
remove(n) makes a[n] false, so n is absent afterward.
Neither method changes membership for another integer.

One run tells the options apart:

On new IntSet(4), call add(1), then add(3).
The array is [false, true, false, true], and size is 2.
The specification gives the set {1, 3}, with bound 4.
- A gives {0, 1, 2, 3}.
- B gives {1, 3}.
- C gives {0, 2}.
- D gives {0, 1}.

The definition: Lecture 11's Abstraction functions.