Description

DAY CLASS, Version 1 Dr. S. Smith
DURATION OF EXAMINATION: 2.5 hours (+ 30 minutes buffer time)

NAME: [Enter your name here —SS] Mingzhe Wang
Student ID: [Enter your student number here —SS] 400316660

Special Instructions:
1. 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.
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 during grading. Please make your answers well-written and succinct.
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]
• 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.
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
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.