Department of Computer Science and Software Engineering
SEMESTER 1, 2018 EXAMINATIONS
CITS1001
Object-oriented Programing and Software Engineering
FAMILY NAME: ____________________________ GIVEN NAMES: ______________________
STUDENT ID: SIGNATURE: ___________________________
This Paper Contains: 20 pages (including title page) Time allowed: 2:00 hours
INSTRUCTIONS:
Answer all questions. The paper contains eight questions, each worth ten marks. Write your answers in the spaces provided on this question paper. No other paper
will be accepted for the submission of answers.
Your answers are not required to reproduce code which is given in the questions. Do not write in this space.
PLEASE NOTE
Examination candidates may only bring authorised materials into the examination room. If a supervisor finds, during the examination, that you have unauthorised material, in whatever form, in the vicinity of your desk or on your person, whether in the examination room or the toilets or en route to/from the toilets, the matter will be reported to the head of school and disciplinary action will normally be taken against you. This action may result in your being deprived of any credit for this examination or even, in some cases, for the whole unit. This will apply regardless of whether the material has been used at the time it is found.
Therefore, any candidate who has brought any unauthorised material whatsoever into the examination room should declare it to the supervisor immediately. Candidates who are uncertain whether any material is authorised should ask the supervisor for clarification.
Supervisors Only – Student left at:
This page has been left intentionally blank
CITS1001, Semester 1 2018 2
This page has been left intentionally blank
CITS1001, Semester 1 2018 3
Class structure
1a)
1b)
Write a Java class Country to represent a country, for tracking membership of the United Nations. The class should have
three instance variables that capture
o the country’s name,
o its status with respect to the UN (either not a member, or a member of the
General Assembly, or a temporary member of the Security Council, or a
permanent member of the Security Council), and o whether it has paid its UN membership dues;
a constructor that sets up each of these variables (with appropriate error-checking on the status variable);
accessor methods for each of these variables; and
a mutator method for the status variable. (5 marks)
Write a Java class UN to represent the member countries of the United Nations. The class should have
one instance variable that holds information about the member countries;
a constructor that sets up this variable;
an accessor method that takes an integer and that returns the corresponding Country object;
a method newMember that takes a Country object and updates all instance variables appropriately; and
a method sameStatus that takes two Country objects and returns true
iff they have the same status in the UN. (5 marks)
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 4
CITS1001, Semester 1 2018 5
Numbers
2) Complete the class Circle by writing the four methods marked TODO below.
public class Circle
{
double cx, cy; // coordinates of the centre
double r; // radius
public Circle(double cx, double cy, double r)
{
if(r <= 0)
throw new IllegalArgumentException("Negative radius");
this.cx = cx;
this.cy = cy;
this.r = r;
}
// returns the distance between points x1,y1 and x2,y2
public double distance(double x1,double y1,double x2,double y2)
{
} }
// TODO
// returns true iff the circle intersects the x-axis
public boolean intersectsX()
{
// TODO
(2 marks)
(2 marks)
}
}
// returns true iff this circle extends further to the right
// than circle c
public boolean furtherRightThan(Circle c)
{
// TODO (3 marks) }
// returns the distance from the closest point on the circle
// to the origin
public double distanceToOrigin()
{
// TODO
(3 marks)
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 6
CITS1001, Semester 1 2018 7
Booleans
3) Suppose you are given an integer array xs that is sorted in ascending order and you are asked to check whether any pair of numbers on xs adds up to a number n. One fast way to do this is to first check the sum of the smallest and largest numbers, and then
if this sum is correct, the search has succeeded;
if it is too small, the smallest number can be excluded from the search; if it is too large, the largest number can be excluded.
In the latter two cases, the search continues with the rest of the array. The search fails if/when only one array element remains.
Write the following method that implements this process.
// returns true iff two numbers on xs sum to n
// assumes that xs is sorted in ascending order
public boolean twoSum(int[] xs, int n)
For example, twoSum({1,4,6,8,9}, 12) should return true, and twoSum({1,4,6,8,9}, 11) should return false.
(10 marks)
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 8
CITS1001, Semester 1 2018 9
Collections
4a) List the three key differences between arrays and ArrayLists in Java. (3 marks)
4b) Consider a class with a field variable xs declared by ArrayList
Write a method alternating that removes alternating elements from xs. For example, if xs is <“A”, “B”, “C”, “D”, ”E”>,
after alternating has run, xs will be {“A”, “C”, ”E”}.
Similarly, if xs is <“A”, “B”, “C”, “D”, “E”, “F”>,
after alternating has run, xs will be {“A”, “C”, “E”}. (4 marks) // removes alternating elements from the field variable xs
public void alternating()
4c) Describe how alternating would have to be written if xs were an array
variable instead of an ArrayList. What issues might this cause? (3 marks)
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 10
CITS1001, Semester 1 2018 11
Software design
5) Briefly define the following concepts with respect to Java classes.
a) Cohesion
b) Coupling
c) Robustness
d) Modularization
e) Encapsulation
(2 marks) (2 marks) (2 marks) (2 marks) (2 marks)
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 12
CITS1001, Semester 1 2018 13
Multi-dimensional arrays
6) The game Othello is played on an 8×8 board of squares, each of which is either empty or it holds a Black piece or a White piece. On Black’s move it is legal for them to place a new piece on an empty square x,y iff there is a straight line of one or more White pieces from x,y to another square holding a Black piece. For example, on this board:
it is legal for Black to place a piece on any of the squares marked by a small circle: (3,1), or (4,1), or (4,2), or (6,3), or (3,5), or (5,5).
Write the following method. (10 marks) // returns true iff Black can place a piece at x,y on board
public boolean canPlaceAt(int x, int y, int[][] board)
board is an 8×8 array where each element is 0 if the corresponding square is empty, 1 if it is occupied by a Black piece, and –1 if it is occupied by a White piece. Squares are numbered 0..7 up and across from the bottom-left-hand corner.
You will probably find it helpful to define a private helper method that checks whether the new piece makes a line in one direction from x,y.
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 14
CITS1001, Semester 1 2018 15
Sorting
7) “Shell sort” is a variant of the insertion sort algorithm. The code below sorts the array ys into ascending order.
// shellsort sorts ys in-place
public void shellsort(int[] ys)
{
int gap, k, j, temp;
for(gap = ys.length / 2; gap >= 1; gap = gap / 2)
{
} }
for(k = gap; k < ys.length; k++)
{
temp = ys[k];
j = k;
while(j >= gap && ys[j – gap] > temp)
{
ys[j] = ys[j – gap];
j = j – gap; }
ys[j] = temp;
}
a) Show how the application shellsort({8, 2, 1, 9, 5, 6, 3, 7, 4})
is processed. In particular, show the state of the array ys at the end of each iteration of the outermost loop.
b) Briefly describe the role of the variable j in the method.
c) Forwhatkindofdatawillshellsortbefastest?Why?
(6 marks) (2 marks) (2marks)
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 16
CITS1001, Semester 1 2018 17
Recursion
8a) What are the two roles of the base cases in a recursive Java method?
8b) The Antarctica Army IT section wants to set up a recursive Java class Soldier to represent a serving soldier and his/her command relationships with other soldiers. What two instance variables would you suggest in this class to represent these relationships?
8c) Ackermann’s function is defined by the following equation.
(2 marks)
(2 marks)
(3 marks) (3 marks)
𝑛 + 1
𝐴(𝑚, 𝑛) = {𝐴(𝑚 − 1,1)
𝐴(𝑚 − 1, 𝐴(𝑚, 𝑛 − 1))
𝑖𝑓 𝑚 = 0
𝑖𝑓 𝑛 = 0 𝑜𝑡h𝑒𝑟𝑤𝑖𝑠𝑒
Write a recursive method that calculates Ackermann’s function. 8d) Show the sequence of method calls that your definition generates
for the invocation ackermann(1, 2).
Use this space and the page opposite for your answer to this question
CITS1001, Semester 1 2018 18
CITS1001, Semester 1 2018 19
END OF PAPER
CITS1001, Semester 1 2018
20