Homework #3 Due: Friday May 8, in class

1. Augment the specifications for the Set object with the operations Cardinality and Difference. Cardinality gives the number of elements in a set. Difference returns the difference between two sets:

Difference(S1, S2) = {x: x Œ S1 and x œS2}.

2. Add a Reverse operation to the algebraic specification for strings, StringSpec ( pp. 220-221 in text). Reverse take a string as an input argument and returns the string in reverse order. For example, Reverse specifies an operation that would input a string " a b c" and return the string "c b a".

3. Add a Substring function to StringSpec (pp.220-221, text).

Substring(S, i, j) returns the substring defined by the ith through jth characters (inclusive) of the string S.

4. Suppose that you used 8 modules to simulate the behavior of a computer system, with the following names and functions:

Control_Unit, Main_Store, ALU (Arithmetic-Logic Unit),

Console_Input, Display, Disk_Controller, Disk_Unit,

Network_Driver

(a) How could you organize the modules in a hierarchy using the COMPRISES relation? Show the hierarchy as a graph with at least 3 levels, including the root.

(b) Select some subset, at least 3 modules, that can be structured in a USES hierarchy. Show the hierarchy as a graph and describe the meaning of the USES relation in this application.