2ME3 – Assignment 2

联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

2ME3 – Assignment 2

Please read this document very carefully. Follow instructions exactly. If you have any questions please post them to MS Teams or ask during o ce hours.

This assignment is due Nov 10th, by 11:59pm

I have created an Assignment 2 channel in Teams. If you have questions about the assignment, please post them there. Thank you.

Unless speci cally stated, assume you are not allowed to import external libraries.

Purpose

The primary objective of this assignment is to assess your ability to interpret a mathematical spec- i cation. The main di culty of this assignment is not intended to come from the coding of your classes, but rather, deciphering exactly what the speci cation is saying.

Note:

I have made the speci cations intentionally unintuitive at times. That is, I have given functions

and variables generic names, and may have stated some things in way which are less elegant than they could have been stated.

Myself and the TAs are happy to answer questions regarding notation, but questions such as

“should f4 return true if there are… ” will most likely be answered with: ”Please read the speci cation.”

Overview

There are no other les associated with this document. You are responsible for submitting three les:

1. A2.pdf, .txt, .docx (as long as we can read it)

2. Mystery1.java

3. Mystery2.java

See below for details on what you are responsible for completing.

Your Tasks

At the end of this document are two separate MIS’s. You are responsible for implementing these two speci cations. Mystery1 and Mystery2 are not associated with each other in any way. Think of them as two separate questions. Submit these implementations as Mystery1.java and Mystery2.java respectively. You may import/use ArrayLists if you wish.

You are also responsible for giving a plain English explanation of the following access routines:

f4() from Mystery1.java

f2() from Mystery2.java

These explanations need not be long (no longer than a half page, and potentially much shorter than that). They should explain the nature of what these access routines are actually doing. To aid in your explanation, think of an practical application of both modules.

Submitting and Grading

This assignment will be submitted electronically via Avenue. Part of your assignment will be auto graded, part will be done manually. A rough breakdown is given below.

Mystery1.java: 40%

Mystery2.java: 40%

A2.pdf methods: 20%

Code which does not compile will be heavily penalized. Good luck!

Academic Dishonesty Disclaimer

All of the work you submit must be done by you, and your work must not be submitted by someone else. Plagiarism is academic fraud and is taken very seriously. The department uses software that compares programs for evidence of similar code.

Please don’t copy. The TAs and I want you to succeed and are here to help. Here are a couple of general guidelines to help you avoid plagiarism:

Never look at another assignment solution, whether it is on paper or on the computer screen. Never show another student your assignment solution. This applies to all drafts of a solution and to incomplete solutions. If you nd code on the web that solves part or all of an assignment, do not use or submit any part of it! A large percentage of the academic o enses in involve students who have never met, and who just happened to nd the same solution online. If you nd a solution, someone else will too.

Mystery1 Module Interface

Uses

None

Syntax

Exported Types

Mystery1 =

Exported Access Routine

Routine Name

In

Out

Exceptions

new Mystery1

Mystery1

None

f1

N

None

f2

String

None

f3

String, String

None

f4

String, String

B

None

Semantic

Local Types

String = char[]

X = tuple(x:String, y:String)

State Variables

S1 : String{ }

S2 : X{ }

Assumptions

All inputs are of the proper type.

The notation X(s1 , s2 ) is shorthand for saying (s1 , s2 ) is a tuple of type X, where x = s1 and

y = s2 .

Access Routine Semantics

Mystery1():

transition: S1 , S2 = { }, { }

output: out := this

f1():

output: out := 1S1 1

f2(s):

transition: S1 := S1 U {s}

f3(s1 ,s2 ):

transition: S2 := S2 U {X(s1 , s2 )}

f4(s1 ,s2 ):

output: out := s2 e U(s : String 1s e g(s1 ) : g(s)) A s2 g(s1 )

Local Functions

g(s) : String → String{ }

g(s) = {s/ : X(s, s/ ) e S2 }

Mystery2(T) Generic Module

Uses

None

Syntax

Exported Types

Mystery2 =

Exported Access Routine

Routine Name

In

Out

Exceptions

new Mystery2

Mystery2

None

f1

T, T

Exception

f2

T

Exception

Semantic

Local Types

X = tuple(x1 :T, x2 :TU{k}, x3 :N)

Local Constants

k = -1

State Variables

S = X{ }

Assumptions

All inputs are of the proper type.

k T

The notation X(a, b, c) is shorthand for saying (a, b, c) is a tuple of type X, where x1 = a,

x2 = b and x3 = c.

Access Routine Semantics

Mystery2():

transition: S = { }

output: out := this

f1(t1 , t2 ):

transition: S1 := S1 U {X(t1 , t, n)}, where the following all hold:

1. V(x : X1x e S : x.x3 < n) 2. 3(x : X1x e S : x.x1 = t2 ) ÷ t = t2 3. -3(x : X1x e S : x.x1 = t2 ) ÷ t = k exception: 3(x : X1x e S : x.x2 = t1 ) ÷ Exception f2(): transition: S := g2(x.x1 ) Ug3(x.x1 )-{x}, where: x e g1 ()AV(x/ : X1x/ e g1 () : x/ .x3 < x.x3 ) output: out := x.x1 where, x e g1 () A V(x/ : X1x/ e g1 () : x/ .x3 < x.x3 ) exception: S = {} ÷ Exception Local Functions g1() :None → X{ } g1() = {x : x e S A x.x2 = k} g2(t) : T → X{ } g2(t) = {X(x1 , k, x3 ) : X(x1 , t, x3 ) e S} g3(t) : T → X{ } g3(t) = {X(x1 , x2 , x3 ) : X(x1 , x2 , x3 ) e S A x2 t} Considerations It is assumed that t1 = t2 , where t1 , t2 : T, would be implemented using the .equals method in Java. That is, t1 = t2 would be equivalent to t1.equals(t2).