COMPSCI_2ME3 -  Midterm Examination - Solved

For taking tests remotely: • Turn off all unnecessary programs, especially Netflix, YouTube, games like Xbox or PS4, anything that might be downloading or streaming.

•    If your house is shared, ask others to refrain from doing those activities during the test.

•    If you can, connect to the internet via a wired connection.

•    Move close to the Wi-Fi hub in your house.

•    Restart your computer, 1-2 hours before the exam. A restart can be very helpful for several computer hiccups.

•    Commit and push your tex file, compiled pdf file, and code files frequently.

•    Ensure that you push your solution (tex file, pdf file and code files) before time expires on the test. The solution that is in the repo at the deadline is the solution that will be graded.

2.    It is your responsibility to ensure that the answer sheet is properly completed. Your examination result depends upon proper attention to the instructions.

3.    All physical external resources are permitted, including textbooks, calculators, computers, compilers, and the internet.

4.    The work has to be completed individually. Discussion with others is strictly prohibited.

5.    Read each question carefully.

6.    Try to allocate your time sensibly and divide it appropriately between the questions.

7.    The set N is assumed to include 0.


Question 1 [6 marks] Parnas advocates faking a rational design process as depicted in the figure below. The faked documentation follows these steps: Requirements (SRS) → Design (MG and MIS) → Application Implementation (code) → Verification and Validation (Unit Testing, Integration Testing, Review). How are the principles of a) abstraction and b) separation of concerns applied in a rational design process? In your answer you can refer to any aspects of the process, documentation, and/or Parnas’s principles.

 

[Fill in your answer below —SS]

a)    Abstraction • The process of faking a rational design process is itself an abstraction. The abstraction, (information hiding), increases through application, S. Design Doc, Req. Doc. The Req. Doc is the most abstract document because it does not specify any implementation instruction, but only the requirement. The S. Design Doc (MIS, MG) is the second most abstract stage. Because in the level, some more instructions like the concept and the sytax and semantics are provided to programmer. The application is the the least abstract one, because it need to contain all code for the program to work.

•    The MG also illustrates Abstraction. In an MG, there are some typical information hiding such as Hardware Hiding, Software Hiding, and Behave hiding. And also we hide secrets in our modules. All of these show the concept of abstraction, which is achieved by information hiding. • MIS is also an abstraction case. In a MIS, we do not need to show the specific implementation of the module, instead we only provide sytax, semantics, and other specification to the programmer. The process and this document is actually an abstraction because it omits unnecessary implementation details.

b)    Separation of Concerns • MG illustrates Separation of Concerns, by writing MG, we decompose the whole system to different module, which provides service and secret.

•    The test process also illustrates Separation of Concerns, because instead of doing integration testing first, we use unit tests to verify the reliability of each method in a module. By doing this, we can find the flaw in a specific area.

•    Abstraction is a special case of separation of concerns. Many different models of the same entity can be produced by abstraction

Consider the specification for two modules: SeqServices and SetOfInt.

Sequence Services Library
Module

SeqServicesLibrary

Uses

None

Syntax
Exported Constants

None

Exported Types

None

Exported Access Programs

Routine name
In
Out
Exceptions
max val
seq of Z
N
ValueError
count
Z, seq of Z
N
ValueError
spices
seq of Z
seq of string
ValueError
new max val
seq of Z, Z → B
N
ValueError
Semantics
State Variables

None

State Invariant

None

Assumptions

•                    All access programs will have inputs provided that match the types given in the specification.

Access Routine Semantics max val(s)

•                    output: out := |m| : N such that (m ∈ s) ∧ ∀(x : Z|x ∈ s : |m| ≥ |x|)

•                    exception: (|s| = 0 ⇒ ValueError)

count(t,s)

•                    output: out := +(x : Z|x ∈ s ∧ x = t : 1)

•                    exception: (|s| = 0 ⇒ ValueError)

spices(s)

•                    output: out := hx : Z|x ∈ s : (x ≤ 0 ⇒ “nutmeg”|True ⇒ “ginger”)i

•                    exception: (|s| = 0 ⇒ ValueError) new max val(s, f)

•                    output: out := max val(hx : Z|x ∈ s ∧ f(x) : xi)

•                    exception: (|s| = 0 ⇒ ValueError)


Set of Integers Abstract Data Type
Template Module

SetOfInt

Uses

None

Syntax
Exported Types SetOfInt = ?

Exported Constants

None

Exported Access Programs

Routine name
In
Out
Exceptions
new SetOfInt
seq of Z
SetOfInt
 
is member
Z
B
 
to seq
 
seq of Z
 
union
SetOfInt
SetOfInt
 
diff
SetOfInt
SetOfInt
 
 
 
 
 
equals
SetOfInt
B
 
Semantics
State Variables s: set of Z

State Invariant

None

Assumptions • The SetOfInt constructor is called for each object instance before any other access routine is called for that object. The constructor can only be called once. All access programs will have inputs provided that match the types given in the specification.

Access Routine Semantics

new SetOfInt(xs):

•                    transition: s := ∪(x : Z|x ∈ xs : {x})

•                    output: out := self

•                    exception: none is member(x):

•                    output: x ∈ s

•                    exception: none to seq():

•                    output: out := set to seq(s)

•                    exception: none

union(t):

•                    output: SetOfInt(set to  seq(s)||t.to seq())

 # in case it is clearer, an alternate version of output is: SetOfInt(set to seq(s ∪ {x : Z|x ∈ t.to seq() : x}))

•                    exception: none

diff(t):

•                    output: SetOfInt(set to  seq(s ∩ complement(t.to seq())))

•                    exception: none

size():

•                    output: |s|

•                    exception: none empty():

•                    output: s = ∅

•                    exception: none

equals(t):

•                    output: ∀(x : Z|x ∈ Z : x ∈ t.to  seq() ↔ x ∈ s) # this means: t.to seq() = s

•                    exception: none

Local Functions
set to seq : set of Z → seq of Z

set to seq(s) ≡ hx : Z|x ∈ s : xi # Return a seq of all of the elems in the set s, order does not matter

complement : seq of Z → set of Z complement(A) ≡ {x : Z|x 6∈ A : x}


Question 2 [15 marks]

[Complete Python code to match the above specification. —SS] The files you need to complete are: SeqServicesLibrary.py and SetOfInt.py. Two testing files are also provided: expt.py and test driver.py. The file expt.py is pre-populated with some simple experiments to help you see the interface in use, and do some initial test. You are free to add to this file to experiment with your work, but the file itself isn’t graded. The test driver.py is also not graded. However, you may want to create test cases to improve your confidence in your solution. The stubs of the necessary files are already available in your src folder. The code will automatically be imported into this document when the tex file is compiled. You should use the provided Makefile to test your code. You will NOT need to modify the Makefile. The given Makefile will work for make test, without errors, from the initial state of your repo. The make expt rule will also work, because all lines of code have been commented out. Uncomment lines as you complete work on each part of the modules relevant to those lines in expt.py file. The required imports are already given in the code. You should not make any modifications in the provided import statements. You should not delete the ones that are already there. Although you can solve the problem without adding any imports, if your solution requires additional imports, you can add them. As usual, the final test is whether the code runs on mills.

Any exceptions in the specification have names identical to the expected Python exceptions; your code should use exactly the exception names as given in the spec.

You do not need to worry about doxygen comments. However, you should include regular comments in the code where it would benefit from an explanation.


Remember, your code needs to implement the given specification so that the interface behaves as specified. This does NOT mean that the local functions need to all be implemented, or that the types used internally to the spec need to be implemented exactly as given. If you do implement any local functions, please make them private by preceding the name with double underscores.

Code for SeqServicesLibrary.py
## @file SeqServicesLibrary.py

# @author Mingzhe Wang

# @brief Library module that provides functions for working with sequences

# @details This library assumes that all functions will be provided with arguments of the expected types



def max_val(s):

if len(s) == 0: raise ValueError

mval = abs(s[0]) for x in s:

if abs(x) > mval:

mval = abs(x)

return mval

def count(t, s):

if len(s) == 0:

raise ValueError

return reduce(lambda x, y: x + y, [1 for x in s if x == t], 0)

def spices(s):

if len(s) == 0:

raise ValueError

return ["nutmeg" if x <= 0 else "ginger" for x in s]

def new_max_val(s, f): if len(s) == 0:

raise ValueError return max_val([x for x in s if f(x)])

Code for SetOfInt.py
## @file SetOfInt.py

# @author Mingzhe Wang

# @brief Set of integers # @date 03/04/2021 class SetOfInt:

def __init__(self, xs):

self.s = set(xs)

def is_member(self, x):

return x in self.s

def to_seq(self): return list(self.s)

def union(self, t): s = self.s.copy() for x in list(t.__gets()):

s.add(x)

return SetOfInt(list(s))

def diff(self, t): return SetOfInt(list(self.s - t.__gets()))

def size(self): return len(self.s)

def empty(self): return len(self.s) == 0

def equals(self, t): return self.s == t.__gets()

def __gets(self): return self.s

Code for expt.py
## @file expt.py

# @author Spencer Smith

# @brief This file is intended to help test that your interface matches the specified interface


from SeqServicesLibrary import * from SetOfInt import *

# Exercising Sequence Services Library print() print("SeqServicesLibrary, max_val expt:", max_val([1, 2, -3])) print("SeqServicesLibrary, count expt:", count(1, [1, 1, 1, 1])) print("SeqServicesLibrary, spices expt:", spices([-5, 0, 23, -.01])) print("SeqServicesLibrary, new_max_val expt:", new_max_val([-5, 0, 23,

10], lambda x: x == 10))

print()

# Exercising Set of Integers xs = [-9, 6, 23, 21, -5] ys = list(xs) ys.append(99)

S = SetOfInt(xs) print("SetOfInt, is_member expt:", S.is_member(21)) print("SetOfInt, to_seq expt:", S.to_seq())

S2 = SetOfInt(ys) S3 = S.union(S2)

print("SetOfInt, union expt:", S3.to_seq()) S4 = S2.diff(S)

print("SetOfInt, diff expt:", S4.to_seq()) print("SetOfInt, size expt:", S4.size()) print("SetOfInt, size expt:", S4.empty()) S5 = SetOfInt([-9, 6, 23, -5, 21]) print("SetOfInt, equals expt:", S.equals(S5)) print()

S1 = SetOfInt([1,9,3,200,81,21,99,12])

S2 = SetOfInt([3,1,9,10])

S3 = S1.diff(S2)

S5 = SetOfInt([21,81,200])

print("SetOfInt, union expt:", S3.to_seq())

print("SetOfInt, size expt:", S3.size()) print("SetOfInt, size expt:", S3.empty()) print("SetOfInt, equals expt:", S3.equals(S5)) print(type(S2))


Code for test driver.py
## @file test_driver.py

# @author Your Name

# @brief Tests implementation of SeqServicesLibrary and SetOfInt ADT


from SeqServicesLibrary import * from SetOfInt import * from pytest import *

## @brief Tests functions from SeqServicesLibrary.py class TestSeqServices:

# Sample test def test_sample_test1(self):

assert True

## @brief Tests functions from SetOfInt.py class TestSetOfInt:

# Sample test def test_sample_test2(self):

assert True

Question 3 [5 marks]

Critique the design of the interface for the SetOfInt module. Specifically, review the interface with respect to its consistency, essentiality, generality and minimality. Please be specific in your answer.

[Put your answer for each quality below. —SS]

•    consistency: The design seems not consistent because of its name conventions. For example. the empty should be renamed to is_empty to be consistent with is_member. In addition, the to_seq should be renamed to get_seq because it is not a mutator.

•    essentiality: The design is not essential because some services provided a method can be provided by the combination of other method’s services. For example, the service of empty can be gained by using size.

•    generality: The design is also not general. Because we don’t know how the module will be used in the future. It is better for us to change the design of set to work for all types instead of just integers.

•    minimality: The design is in general minimal because every methods only provides one service. The only behavior seems not too minimal is that the union and diff actually return a new SetOfInt object.


Question 4 [4 marks]

The module SetOfInt is for a set of integers. Please answer the following questions related to making that module generic.

a.     How would you change the specification to make it generic? (Specifically what changes would you make to the given specification. You don’t need to redo the spec, just summarize what changes you would need to make.)

b.     What changes would you need to make to the Python implementation to make it generic for type T? (Again, you can describe and characterize the changes; you don’t actually have to make them.)

c.      What relational operator needs to be defined for type T to be a valid choice?

d.     BONUS (1 mark) How would you specify (in the MIS) the relational operator constraint (from the previous question) on the generic type T?

[Put your answer below. —SS]

a.     Change the header to Generic T Abstract Data Type. Change the Template Module name to Set(T).

Change the Exported Types name to Set(T) = ?.

Add Generic before Template Module.

Replace all the type name Z in the sytax and semantic field to T.

b.     Nothing. The implementation in Python is already generic by dynamic typing. (duck typing)

c.      The equal() relational operator should be defined.

d.     (BONUS) Define an interface that specifies the equal() relational operator of Type T, that is Set(T with Equality(T)) in the header, where Equality(T) is the generic interface.

THE END.