Last name: _____________________
Given name: ____________________
CSE373 Winter 2005
Miniquiz #1 with answers and notes
January 14, 2005

1. The property "lives within 10 miles of" gives rise to a relation (call it "L10") on the set of all people P.  I.e., (a,b) is in L10 iff a lives within 10 miles of b.   Which properties does R have?  Write "yes" or "no" beside each one.

_yes___ reflexive

_yes__ symmetric

_no___ transitive


2.  One Java class D directly extends another class B if D's definition includes the phrase "extends B".  "Directly extends" defines a relation R1, the set of ordered pairs (d, b) where d extends b.  Write "yes" or "no" beside each property of R1.

_no___ reflexive

_no___ symmetric

_no___ transitive

The "trick" here is that the relation under discussion is not inherits-from or is-a-subclass-of or anything conceptual like that.  For a pair (D,B) to be in the relation, the definition of D must include the actual text "extends B".  


3. Is R1 a function? (yes or no)  yes


4. Let R2 be the reverse relation between classes, that is, (x, y) is in R2 iff y extends x.  Is R2 a function?  no


5-6.  Given a string and a dictionary, the method FA produces a list of all anagrams of that string which are in the dictionary.   Is this a function?  If not, explain why not.  If so, give the domain and range.

Given a dictionary and a word, there is a fixed subset of the words of that dictionary which are anagrams of the word (whatever the definition of anagram is).  Methods are alway assumed to be deterministic, so although a set of words implies no particular order, and a list does have an order, FA would return the same list every time it is called for a particular word.

domain: ___the set of words___________
range: ____the set of all lists of words____________


7-9. Which of the following sets (if any) is equal to the set {a, (b,c)}?  Write yes or no by each one.
(Scoring: -1 for each error, up to max -2)

{a, (c, b)}
{a, b, c}
{(a, b), c}
{(b, c), a}  equal -- all other are unequal
{(c,b), a}

In a set {}, the order does not matter in determining equality.  In an ordered pair ( , ) order does matter.

9-10.  Suppose you see this line of code in a correct Java program:
Picture  p =  new  Painting( );
For each statement, put an 'X' in the correct box to the right of it.
(Scoring: -1 for each error, up to max -2)
statement
 must be true
 might be true
 cannot be true
Picture is an interface
X
Picture is an abstract class
X
Picture is a concrete class
X
Painting is an interface

X
Painting ia an abstract class

X
Painting is a concrete class X

Picture is a subclass of Painting

X
Painting is a subclass of Picture (see note)
 X (see note)

Note on the last line: Painting is strictly speaking a "subclass of Picture" only if Picture is a class (either abstract or concrete).  Some programmers might loosely refer to Painting as a subclass if Picture is an interface, too (which would make the answer "must be true") but this terminology is not good.  It is better to say "Painting is an implementation of Picture."

12-13. Recall this definition of a pop operation on a stack, using function and set notation:

pop: [e0, e1, ..., en-1] -> (en-1, [e0, e1, ..., en-2])

Using this style of notation, define the push operation.

push: (en, [e0, e1, ..., en-1]) -> [e0, e1, ..., en-1, en]