[SOLVED] COMPSCI_2ME3 Final Examination

Question 1  What are the problems with using “average lines of code written per day” as a metric for programmer productivity?

[Provide your reasons in the itemized list below. Add more items as required. —SS]

• The result based on this metric is partial because it does not consider the software qualities of the written programs like the reliability, performance, verifiability, maintainability etc.
• The ”fake the rational design process” is also meaningful for testing a programmer’s productivity.
• The average line of code indicator does not contain any information of the verification. What if

  this programmer has a high aver. line. of code while most of these codes have bugs?

• The program’s productivity should also consider the design and document writing behavior. Be- cause for a programmer, implementing code is only part of his work, while most of the work is to design a good project and writing the corresponding document (SRC, MG, MIS).
• ”Per day” is absolutely not right. Some people even work during the the weekend while still be low productive. We need a some common assumptions and criterion like working 5 hours in work day for this criterion to work.

Question 2  Critique the following requirements specification for a new cell phone ap- plication, called CellApp. Use the following criteria discussed in class for judging the quality of the specification: abstract, unambiguous, and validatable. How could you improve the requirements speci- fication?

“The user shall find CellApp easy to use.”

[Fill in the itemized list below with your answers. Leave the word in bold at the beginning of each item. —SS]

• Abstract – Not abstract. Because we do not need to name this application “CellApp”.
• Unambiguous – Ambiguous. Because it doesn’t define a typical user or the “esay to use” term. • Validatable – Not validatable. Because an ambiguous program cannot be validatable.

• How to improve – First, ask the client to provide some specific using scenario to help specify the typical user group. Second, measure the ”easy to use” indicator by designing surveys to avoid the subjective and ambiguous judgment by human. Third, we can just call this program “project xxx” before its releasing to the client to make it more abstract.

Question 3 The following module is proposed for the maze tracing robot we discussed in class (L20). This module is a leaf module in the decomposition by secrets hierarchy.

Module Name find path
Module Secret The data structure and algorithm for finding the shortest path in a graph.

[Fill in the answers to the questions below. For each item you should leave the bold question and write your answer directly after it. —SS]

A. Is this module Hardware Hiding, Software Decision Hiding or Behaviour Hiding? Why?

It is Software Decision Hiding, because it is both an application data type module (hides imple- mentation of certain variables) and software utility module (hides algorithms used in several other modules).

B. Is this a good secret? Why?
No. The principle is ”one module one secret”, however, this module combines data structure and

algorithm together.

C. Does the specification for maze tracing robot require environment variables? If so, which environment variables are needed?
Yes. For example, the file input, the physical button, and the start and end position.

Question 4 Answer the following questions assuming that you are in doing your final year capstone in a group of 5 students. Your project is to write a video game for playing chess, either over the network between two human opponents, or locally between a human and an Artificial Intelligence (AI) opponent.

[Fill in the answers to the questions below. For each item you should leave the bold question and write your answer directly after it. —SS]

1. You have 8 months to work on the project. Keeping in mind that we usually need to fake a rational design process, what major milestones and what timeline for achieving these milestones do you propose? You can indicate the time a milestone is reached by the number of months from the project’s start date.
   • Requirements (Problem Statement, Development Plan, and SRS) 2-month Note: should also design System VnV Plan during this time
   • Design (MG and MIS) 2-month
     Note: should also design Integration VnV Plan and UnitVnV Plan during this time
   • Implementation (Code) 1-month
   • Verification (V&V Report) 2-month
   • Delivery and Maintenance(prepare for final presentation and fix any errors discovered) 1- month
2. Everything in your process should be verified, including the verification. How might you verify your verification?

   By Mutation Testing.

   • Generate changes to the source code, called mutants, which become code faults
   • Mutants include changing an operation, modifying constants, changing the order of execution, etc.
   • The adequacy of a set of tests is established by running the tests on all generated mutants
   • The goal is to kill the mutants
3. How do you propose verifying the installability of your game?
   Using Virtual Machine to set up different environments or using tools like Docker.

Question 5 As for the previous question, assume you are doing a final year capstone project in a group of 5 students. As above, your project is to write a video game for playing chess, either over the network between two human opponents, or locally between a human and an Artificial Intelligence (AI) opponent. The questions below focus on verification and testing.

[Fill in the answers to the questions below. For each item you should leave the bold question and right your answer directly after it. —SS]

1. Assume you have 4 work weeks (a work week is 5 days) over the course of the project for verification activities. How many collective hours do you estimate that your team has available for verification related activities? Please justify your answer.

   Assuming average 2 hours per day and half of days will be consumed for other reasons, then maybe only 20 hours. Because different team members may have personal timelines during this time and the time consumed for the team communication to get everyone understood is also very long.

2. Given the estimated hours available for verification, what verification techniques do you recommend for your team? Please list the techniques, along with the number of hours your team will spend on each technique, and the reason for selecting this technique.
   • Continuous Integration Testing. Build a server that can perform regression tests each time the team member push their code. That process will automatically check the code while the code are being implemented, therefore only the initial design and the following maintainance takes time. – 10 hours.
   • Fault Testing. This technology can calculate the exception rate in a black-box way to save our time. – 2 hours.
   • Code Walkthrough. This could guarantee our code’s reliability by logic checking instead of only empirical testing – 8 hours (2 hours at the beginning, 2 in the middle, 4 for the final discussion).
3. Is the oracle problem a concern for implementing your game? Why or why not? If it is a concern, how do you recommend testing your software? Yes. Because for a chess game, there is not a winning strategy been discovered currently, and that makes most of the testing hard to validate. (Because you do not know if the AI is playing in the wisdom way). I suggest testing by strategy without an oracle. That is :
   • Parallel testing
   • By some special cases that can be easier to calculated. For example, the remaining board is proved to has a winning strategy by one player.

Question 6

for resonance when the integer input between 1

Consider the following natural language specification for a function that looks input matches an integer multiple of the wavelengths 5 and 7. Provided an

and 1000, the function returns a string as specified below:

• If the number is a
• If the number is a
• If the number is a
• Otherwise, the output is “no resonance”

multiple of 5, then the output is “resonance 5”
multiple of 7, then the output is “resonance 7”
multiple of both 5 and 7, then the output is “resonance 5 and 7”

You can assume that inputs outside of the range 1 to 1000 do not occur.

1. What are the sets Di that partition D (the input domain) into a reasonable set of equivalence classes?

   [answer here – you can answer in natural language, or using mathematical notation. —SS]

   • Set of the number which is a multiple of 5 but not a multiple of both 5 and 7. • Set of the number which is a multiple of 7 but not a multiple of both 5 and 7. • Set of the number which is a multiple of both 5 and 7.
   • Set of the number which is neither a a multiple of 5 nor a multiple of 7.

2. Given the sets Di, and the heuristics discussed in class, how would you go about selecting test cases?

   [answer here – you don’t need specific test cases; your answer should characterize how all significant test cases are to be chosen. —SS]

   • Test for boundary conditions suggests 1, 5 − 1, 7 + 1, 35 + 1 etc.
   • Black box test suggests normal cases like 5, 7, 35, 14, 6 etc.
   • The worst case of the program suggests a number that is not a multiple of 5 or 7, such as 6.
   • Condition-Coverage suggests all different combinations of the if expression.
   • Path-Coverage characterize the test cases such as 5, 7, 35, and 1.
   • The statement coverage or Edge coverage cases will be covered in the above cases for this question.

Question 7 Below is a partial specification for an MIS for the game of tic-tac-toe (https: //en.wikipedia.org/wiki/Tic-tac-toe). You should complete the specification.

[The parts that you need to fill in are marked by comments, like this one. You can use the given local functions to complete the missing specifications. You should not have to add any new local functions, but you can if you feel it is necessary for your solution. As you edit the tex source, please leave the wss comments in the file. You can put your answer immediately following the comment. —SS]

Syntax
Exported Constants
SIZE = 3 //size of the board in each direction

Exported Types

cellT = { X, O, FREE } Exported Access Programs

Routine name

init

getb
get turn
is valid move is winner
is game over

Semantics

State Variables

b: boardT Xturn: B

State Invariant

In

N, N N, N

cellT

Out Exceptions

cellT OutOfBoundsException cellT
B OutOfBoundsException B

B

[Place your state invariant or invariants here —SS]

Assumptions

The init method is called for the abstract object before any other access routine is called for that object. The init method can be used to return the state of the game to the state of a new game.

Access Routine Semantics

init():
• transition:

• exception: none move(i, j):

< FREE, FREE, FREE > Xturn,b:=true,< <FREE,FREE,FREE> >

< FREE, FREE, FREE >

• transition: Xturn, b[i, j] := ¬Xturn, (Xturn ⇒ X|¬Xturn ⇒ O)
• exception

  exc := (InvalidPosition(i, j) ⇒ OutOfBoundsException|¬is valid move(i, j) ⇒ InvalidMoveException)

  getb(i, j):
  • output: out := b[i, j]
  • exception exc := (InvalidPosition(i, j) ⇒ OutOfBoundsException)

  get turn():

  • output: [Return the cellT that corresponds to the current turn —SS]

    out:=(Xturn⇒X |¬Xturn⇒O)

  • exception: none

    is valid move(i, j):
    • output: out := (b[i][j] = FREE)
    • exception exc := (InvalidPosition(i, j) ⇒ OutOfBoundsException)

    is winner(c):
    • output: out := horizontal win(c, b) ∨ vertical win(c, b) ∨ diagonal win(c, b) • exception: none

    is game over():

    • output: [Returns true if X or O wins, or if there are no more moves remaining —SS]

      out := is winner() ∨ ¬(∃(i, j : N | 0 ≤ i, j ≤ SIZE − 1 : is valid move(i, j)))

    • exception: none

      Local Types

boardT = sequence [SIZE, SIZE] of cellT

Local Functions InvalidPosition: N × N → B

InvalidPosition(i, j) ≡ ¬((0 ≤ i < SIZE) ∧ (0 ≤ j < SIZE)) count: cellT → N

[For the current board return the number of occurrences of the cellT argument —SS]

count(c) ≡ ∀(i, j : N | 0 ≤ i, j ≤ SIZE − 1 ∧ b[i][j] = c : 1)

horizontal win : cellT × boardT → B
horizontal win(c,b) ≡ ∃(i : N|0 ≤ i < SIZE : b[i,0] = b[i,1] = b[i,2] = c)

vertical win : cellT × boardT → B
vertical win(c,b) ≡ ∃(j : N|0 ≤ j < SIZE : b[0,j] = b[1,j] = b[2,j] = c)

diagonal win : cellT × boardT → B

[Returns true if one of the diagonals for the board has all of the entries equal to cellT —SS]

diagonal win(c,b)≡(b[0,0]=b[1,1]=b[2,2]=c)∨(b[0,2]=b[1,1]=b[2,0]=c)

Question 8  For this question you will implement in Java an ADT for a 1D sequence of real numbers. We want to take the mean of the numbers in the sequence, but as the following web- page shows, there are several different algorithms for doing this: https://en.wikipedia.org/wiki/ Generalized_mean

Given that there are different options, we will use the strategy design pattern, as illustrated in the following UML diagram:

Figure 1: UML Class Diagram for Seq1D with Mean Function, using Strategy Pattern

You will need to fill in the following blank files: MeanCalculator.java, HarmonicMean.java, QuadraticMean.java, and Seq1D.java. Two testing files are also provided: Expt.java and TestSeq1D.java. The file Expt.java is pre-populated with some simple experiments to help you see the interface in use,
and do some initial testing. You are free to add to this file to experiment with your work, but the file itself isn’t graded. The TestSeq1D.java 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.java file. As usual, the
final test is whether the code runs on mills. You do not need to worry about doxygen comments.

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

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. The real type in the MIS should be implemented by Double (capital D) in Java.

[Complete Java code to match the following specification. —SS]

Page 12 of 21

CS2ME3/SE2AA4

Mean Calculator Interface Module Interface Module

MeanCalculator

Uses

None

Syntax
Exported Constants None

Exported Types

None

Exported Access Programs
Routine name In Out Exceptions

meanCalc seq of R R Considerations

meanCalc calculates the mean (a real value) from a given sequence of reals. The order of the entries in the sequence does not matter.

Page 13 of 21

CS2ME3/SE2AA4

Harmonic Mean Calculation Template Module inherits MeanCalculator

HarmonicMean

Uses

MeanCalculator

Syntax
Exported Constants None

Exported Types

None

Exported Access Programs

Routine name

meanCalc

Semantics State Variables None

State Invariant

None

Assumptions

None

In Out

seq of R R

Exceptions

Access Routine Semantics

meanCalc(v)
• output: out := |x|

+(x:R|x∈v:1/x) • exception: none

Page 14 of 21

CS2ME3/SE2AA4

Quadratic Mean Calculation Template Module inherits MeanCalculator

QuadraticMean

Uses

MeanCalculator

Syntax
Exported Constants None

Exported Types

None

Exported Access Programs

Routine name

meanCalc

Semantics State Variables None

State Invariant

None

Assumptions

None

In Out

seq of R R

Exceptions

Access Routine Semantics

meanCalc(v)

• output: out := 􏰂+(x:R|x∈v:x2) |x|

• exception: none

Seq1D Module Template Module

Seq1D

Uses

MeanCalculator

Syntax Exported Types Seq1D = ?

Exported Constants

None

Exported Access Programs

Routine name In Out

new Seq1D seq of R, MeanCalculator Seq1D setMaxCalculator MaxCalculator
mean R

Semantics State Variables

s: seq of R
meanCalculator: MeanCalculator

State Invariant

None

Assumptions

Exceptions

IllegalArgumentException

• The Seq1D 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 real numbers provided to the constructor will be zero or positive.

Page 16 of 21

CS2ME3/SE2AA4

Access Routine Semantics

new Seq1D(x, m):
• transition: s, meanCalculator := x, m
• output: out := self
• exception: exc := (|x| = 0 ⇒ IllegalArgumentException)

setMeanCalculator(m):
• transition: meanCalculator := m • exception: none

mean():
• output: out := meanCalculator.meanCalc() • exception: none

Page 17 of 21

CS2ME3/SE2AA4

Code for MeanCalculator.java

package src;

import java.util.ArrayList;

public interface MeanCalculator {
public Double meanCalc(ArrayList <Double > v);

}

Code for HarmonicMean.java

package src;
import java.util.ArrayList;
public class HarmonicMean implements MeanCalculator {

public

} }

Double meanCalc(ArrayList <Double > v) { Double de_sum = 0.0;
for (Double e : v) {

de_sum += 1.0 / e; return v.size() / de_sum;

}

Page 19 of 21

CS2ME3/SE2AA4

Code for QuadraticMean.java

package src;
import java.util.ArrayList;
public class QuadraticMean implements MeanCalculator {

public

} }

Double meanCalc(ArrayList <Double > v) { Double qu_sum = 0.0;
for (Double e : v) {

qu_sum += Math.pow(e, 2); return Math.sqrt(qu_sum / v.size());

}

Code for Seq1D.java

package src;
import java.util.ArrayList; public class Seq1D {

private ArrayList <Double > s;
private MeanCalculator meanCalculator;

public Seq1D(ArrayList <Double > x, MeanCalculator m) throws IllegalArgumentException {

if (x.size() == 0) {
throw new IllegalArgumentException(“Can not be

}

}

empty list”);

this.s = x; this.meanCalculator = m;

public void setMeanCalculator(MeanCalculator m) { this.meanCalculator = m;

}

public Double mean() {
return meanCalculator.meanCalc(s);

} }

THE END.

Page 21 of 21