Problem Set 1

Object Oriented Software Construction, Spring Semester, 1998—Problem Set #1

Object Oriented Software Construction
Spring Semester, 1998

Problem Set 1

Issued: March 23, 1998

Due date: April 6, 1998
Note: In the following questions, by “abstract data type (ADT) specification”, we mean the functions applicable to an instance of the ADT, axioms which define the properties of the function’s values, and, if required, the preconditions on any partial functions.
Exercise 1.1

1. 
   Write an abstract data type (ADT) specification for QUEUE[G]. Your specification should be sufficiently complete (according to the definition given in class). Reminder: a queue is a first-in, first-out data structure.
   
2. 
   Complete the missing parts in the following sequence; prove your answer by the axioms you gave in part (a).
   

Q1 = new

Q2 = put(Q1, 1)

Q3 = put(Q2, 2)

Q4 = put(Q3, 3)

E1 = item(Q4) = ???

Q5 = remove(Q4)

E2 = item(Q5) = ???

E3 = empty(Q5) = ???

3. 
   Prove that your specification is sufficiently complete. (Reuse the corresponding proof for stacks, given in class, as much as possible.)
   

Exercise 1.2

(Don’t do this exercise yet, but you should be prepared to discuss this problem in class next week.)

Members of the Israeli Domino Cooperative, a competitive league, regularly compete in games to determine their relative strength. A game involves two players; it either results in a winner and a loser or is declared a tie. If not a tie, the result of a game is used to update the rankings of players in the league: the winner is declared better than the loser and than any player p such that the loser was previously better than p. Other comparative rankings are left unchanged.

Specify this problem as a set of abstract data types: IDC_LEAGUE, PLAYER, GAME. (Hint: do not introduce the notion of “ranking” explicitly, but model it by a function better expressing whether a player is better than another in the league).

Create an IDC league with three players, play a game between two of them, and demonstrate the resulting ranking by your axioms.