COMPSCI_2ME3 -  Final 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.

•    Use a VPN (Virtual Private Network) since this improves the connection to the CAS servers.

•    Commit and push your tex file, compiled pdf file, and code files frequently. As a minimum you should do a commit and push after completing each question.

•    Ensure that you push your solution (tex file, pdf file and code files) before time expires on the test. 

•    If you have trouble with your git repo, the quickest solution may be to create a fresh clone.

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. Use the allocated marks as a guide on how to divide your time between questions.

7.    The quality of written answers will be considered 

8.    The set N is assumed to include 0.


Question 1 [5 marks]          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. Because 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 [5 marks] Critique the following requirements specification for a new cell phone application, 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 specification?

“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 [5 marks]          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 implementation 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 [5 marks] 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]

A.     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) 1month

B.     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

C.      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 [5 marks] 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]

A.     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.

B.     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).

C.      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 [5 marks] Consider the following natural language specification for a function that looks for resonance when the input matches an integer multiple of the wavelengths 5 and 7. Provided an integer input between 1 and 1000, the function returns a string as specified below:

•    If the number is a multiple of 5, then the output is “resonance 5”

•    If the number is a multiple of 7, then the output is “resonance 7”

•    If the number is a multiple of both 5 and 7, then the output is “resonance 5 and 7”

•    Otherwise, the output is “no resonance”

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

A.     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.

B.     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 [5 marks] 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
In
Out
Exceptions
init
 
 
 
move
N, N
 
OutOfBoundsException, InvalidMove-

Exception
getb
N, N
cellT
OutOfBoundsException
get turn
 
cellT
 
is valid move
N, N
B
OutOfBoundsException
is winner
cellT
B
 
is game over
 
B
 
Semantics
State Variables

b: boardT Xturn: B

State Invariant

[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:

< FREE,FREE,FREE >

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

< FREE,FREE,FREE >

•                     exception: none move(i, j):

•                     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 [5 marks] 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 webpage 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]

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.

Harmonic Mean Calculation
Template Module inherits MeanCalculator

HarmonicMean

Uses

MeanCalculator

Syntax
Exported Constants

None

Exported Types

None

Exported Access Programs

Routine name
In
Out
Exceptions
meanCalc
seq of R
R
 
Semantics
State Variables

None

State Invariant

None

Assumptions

None

Access Routine Semantics meanCalc(v)

•    output: out :=  

•    exception: none

Quadratic Mean Calculation
Template Module inherits MeanCalculator

QuadraticMean

Uses

MeanCalculator

Syntax
Exported Constants

None

Exported Types

None

Exported Access Programs

Routine name
In
Out
Exceptions
meanCalc
seq of R
R
 
Semantics
State Variables

None

State Invariant

None

Assumptions

None

Access Routine Semantics meanCalc(v)

•    output: out :=  

•    exception: none

Seq1D Module
Template Module

Seq1D

Uses

MeanCalculator

Syntax
Exported Types Seq1D = ?

Exported Constants

None

Exported Access Programs

Routine name
In
Out
Exceptions
new Seq1D
seq of R, MeanCalculator
Seq1D
IllegalArgumentException
setMaxCalculator
MaxCalculator
 
 
mean
 
R
 
Semantics
State Variables s: seq of R

meanCalculator: MeanCalculator

State Invariant

None

Assumptions • 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.

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


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;

}

}


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.