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
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.
Prove that your specification is sufficiently complete. (Reuse the corresponding proof for stacks, given in class, as much as possible.)
(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).