1.1
a) false
b) true
c) true
d) false
e) false
f) true

1.2
a) false
b) true
c) false
d) true
e) true

1.3
a) 4
b) 4
c) 2
d) 4
e) 4
f) 2
g) 2

# Abstract Data Types and Design by Contract (20 points)

2.1 Incompleteness in contracts (3 Points)
The creation procedure does not ensure that ensure that all fields of the 3x3 board are initially empty. The commands put_cross(x,y) and put_circle(x,y) do not ensure that only the field (x,y) was changed accordingly.

Examples:

• With this code one could start a new game where no fields are empty.
• The feature put_cross(x,y) could put all fields of the board to cross.

TYPES

GAME

FUNCTIONS

make: GAME

next_turn: GAME ----> INTEGER

item: GAME x INTEGER x INTEGER --|--> INTEGER

put_cross: GAME x INTEGER x INTEGER --|--> GAME

put_circle: GAME x INTEGER x INTEGER --|--> GAME

empty: INTEGER

cross: INTEGER

circle: INTEGER

PRECONDITIONS (where g:GAME; i,j : INTEGER)

P1 item(g,i,j) require 1<=i,j <=3

P2 put_cross(g,i,j) require 1<=i,j <=3 and item(g,i,j) = emtpy and next_turn(g) = Cross

P3 put_circle(g,i,j) require 1<=i,j <=3 and item(g,i,j) = emtpy and next_turn(g) = Circle

AXIOMS

A1 next_turn(make) = cross

A2 next_turn(put_cross(g,i,j)) = circle

A3 next_turn(put_circle(g,i,j)) = cross

A4 item(make,i,j) = empty

A5 item(put_cross(g,i,j),i,j) = cross

A6 item(put_circle(g,i,j),i,j) = circle

A7 item(put_cross(g,i,j),a,b) = item(g,a,b) if ($i\neq a\lor j\neq b$)

A8 item(put_circle(g,i,j),a,b) = item(g,a,b) if ($i\neq a\lor j\neq b$)

A9 empty = 0

A10 cross = 1

A11 circle = 2

2.3 Proof of sufficient completeness (7 Points)

Base The rules applied appear in parentheses next to the equation in the order they were applied. We assume 1<=i,j<=3.

item(make,i,j) = empty = 0 (A4, A9) next_turn(make) = cross = 1 (A1, A10)

Step Let g: GAME, and let the ADT specification be sufficiently complete for g. (IH)

We assume 1<=i,j,a,b<=3.

Let G = put_cross(g,i,j).

next_turn(G) = circle = 2 (A2, A11)

assume a=i, b=j.

then: item(G,a,b) = cross = 1 (A5, A10)

assume a/=i or b/=j.

then: item(G,a,b) = item(g) (A7, sufficiently complete for item(g) by IH)

For G = put_circle(g,i,j), the proof is completely analogous.

q.e.d.

# Design Patterns I (22 points)

Question 1: Composite

```class
POST

process (v: VISITOR)
-- Process "Current" with visitor "v".
do
v.visit_post(Current)
end

end
```
```class

process (v: VISITOR)
-- Process "Current" with visitor "v".
do
end

end
```

Question 2:

```deferred class
VISITOR

visit_post(v: POST)
-- Visit a post.
require
v_exists: v/= void
deferred
end

require
v_exists: v/= void
deferred
end

end
```
```class

visit_post(p: POST)
do
if not p.is_private or has_private_access then
last_output := last_output + p.output
end
end

do
if not t.is_private or has_private_access then
from
t.content.start
until
t.content.off
loop
t.content.item.process(Current)
t.content.forth
end
end
end

end
```

Question 3: State pattern

(draw state pattern :-))

# Design Patterns II (16 points)

```class

perform
do
furniture_list.force([piece_number, furniture_piece])
end

end
```
```class
REMOVE_ACTION

unperform
do
if not furniture_piece = void then
furniture_list.force([piece_number, furniture_piece])
end
end

end
```
```class
ROOM

local
chair: CHAIR

do
furniture_factory.make_chair (c)

redoable_action_stack.wipe_out
end

remove_chair(n:INTEGER)
local
remove_action: REMOVE_ACTION

do
create remove_action.make(n, furniture_list)
remove_action.perform
undoable_action_stack.put(remove_action)
redoable_action_stack.wipe_out
end

undo
local
action: ACTION

do
if not undoable_action_stack.is_empty then
action:= undoable_action_stack.item
undoable_action_stack.remove
action.unperform
redoable_action_stack.put(action)
end
end

end
```