Exam 2015, questions PDF

Preview

Summary

Download Exam 2015, questions PDF

Description

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

This exam paper must not be removed from the venue

Venue

____________________

Seat Number

________

Student Number

|__|__|__|__|__|__|__|__|

Family Name

_____________________

First Name

_____________________

School of Information Technology and Electrical Engineering EXAMINATION Semester One Final Examinations, 2015

CSSE2002 Programming in the Large This paper is for St Lucia Campus students. Examination Duration:

120 minutes

Reading Time:

10 minutes

Exam Conditions:

For$Examiner$Use$Only$ Question))

Mark)

Q1)

)

Q2)

)

This is an Open Book Examination

Q3)

)

During reading time - write only on the rough paper provided

Q4(a))

)

This examination paper will be released to the Library

Q4(b))

)

Materials Permitted In The Exam Venue:

Q5)

)

(No electronic aids are permitted e.g. laptops, phones)

)

)

Calculators - No calculators permitted

)

)

Materials To Be Supplied To Students:

)

)

1 x 14 Page Answer Booklet

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

)

This is a Central Examination

Rough Paper Instructions To Students: Additional exam materials (eg. answer booklets, rough paper) will be provided upon request. Answer each part of the following 5 questions in the Answer Booklet provided. Total marks 60.

Page 1 of 13

) Total) ________)

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 1 [12 marks] Question 1 (a) [4 marks] What is printed in the output window when the code given below is compiled and run? public static void main(String[] args) { int[] list = { 4, 6, 11, 8, 9, 3, 12 }; int sum = 0; boolean counting = false; for (int i = 0; i < list.length; i++) { if ((list[i] % 3 == 0 || list[i] % 2 == 0)) { if (!counting) { sum = list[i]; } else if (list[i - 1] < list[i]) { sum += list[i]; } else { sum = list[i]; } counting = true; System.out.println(i + ": " + sum); } else { counting = false; System.out.println(i + ": -"); } } }

Page 2 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 1 (b) [4 marks] Given the following definition of a class Pair: public class Pair { private int x; private int y; public Pair(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public int getY() { return y; } public void plus(Pair p) { x = x + p.x; y = y + p.y; } public String toString() { return "(" + x + ", " + y + ")"; } } What is printed in the output window when the code given below is compiled and run? (You may assume that the class ArrayList has been imported from the package java.util in the java class libraries.) public static void main(String[] args) { ArrayList x = new ArrayList(); x.add(new Pair(1, 2)); x.add(new Pair(3, 4)); x.add(new Pair(5, 6)); ArrayList y = copy(x); for (int i = 0; i < y.size(); i++) { y.get(i).plus(new Pair(1, 1)); } x.remove(2); System.out.println(x); System.out.println(y); } public static ArrayList copy(ArrayList x) { ArrayList y = new ArrayList(); for (int i = 0; i < x.size(); i++) { Pair p = x.get(i); y.add(p); } return y; }

Page 3 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 1 (c) [2 marks] Assuming the same definition of the class Pair from Question 1(b), what is printed in the output window when the code given below is compiled and run? (You may assume that the interface Comparator, and classes ArrayList and Collections have been imported from the package java.util in the java class libraries.) public static void main(String[] args) { ArrayList list = new ArrayList(); list.add(new Pair(4, 3)); list.add(new Pair(2, 9)); list.add(new Pair(10, -5)); list.add(new Pair(6, 6)); Collections.sort(list, new Comparator() { public int compare(Pair a, Pair b) { return (a.getX() + a.getY()) - (b.getX() + b.getY()); } }); System.out.println(list); } Question 1 (d) [2 marks] Rewrite the implementation of the compare method from Question 1(c) so that it defines a total ordering on pairs in which pairs are ordered first by their y-coordinate, and then by their x-coordinate. E.g. so that pair (4, 3) is less than (2, 9) because y-coordinate 3 is less than y-coordinate 9; and (2, 9) is less than (4, 9) because the y-coordinates of those pairs are equal, but x-coordinate 2 is less than x-coordinate 4.

Page 4 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 2 [12 marks] The following class IntegerSet represents a set of integers that can be used to provide fast access to the smallest IntegerSet.NUM integers in the set. (In the method specifications, \result is used to refer to the return value of the method.) public class IntegerSet { public static final int NUM = 5; private ArrayList smallest; private ArrayList rest; /** Creates a new empty set of integers. * * @ensure Creates a new set such that this.contains(x) is * false for all integers x. */ public IntegerSet() { smallest = new ArrayList(); rest = new ArrayList(); } /** Returns the number of elements in this set of integers. * * @ensure \result is the size of the set of all integer * values v such that this.contains(v). */ public int size() { return smallest.size() + rest.size(); } /** Checks to see if the integer set contains a particular * integer value. * * @ensure \result is true if an only if x is not null and * this set of integers contains an integer with * the same int value as x. */ public boolean contains(Integer x) { return (smallest.contains(x) || rest.contains(x)); } /** * Returns the ith smallest integer contained in the set, * where i is counted from zero so that the smallest * element in the set is this.get(0), the second smallest * element in the set is this.get(1) etc. * * @require 0 NUM) { rest.add(smallest.remove(smallest.size()-1)); } } } } Recall that for a java.util.ArrayList of type ArrayList, •

Method boolean contains(Object o)returns true if and only if the list contains at least one element e such that if o==null then e==null else o.equals(e)).

•

Method Integer get(int index) returns the element at position index in the list. It throws an IndexOutOfBoundsException if the index is out of range, i.e. (index < 0 || index >= size()).

•

Method void add(int index, Integer e)inserts element e at position index in this list, and shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices). It throws an IndexOutOfBoundsException if the index is out of range, i.e. (index < 0 || index > size()).

•

Method boolean add(Integer e) appends the element e to the end of the list.

•

Method Integer remove(int index) removes and returns the element at position index in this list. It throws an IndexOutOfBoundsException if the index is out of range, i.e. (index < 0 || index >= size()).

•

Method boolean remove(Object o) removes the first occurrence of the specified element from the list, if it is present.

Page 6 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 2 (a) [8 marks] Recall that a class invariant (sometimes called an implementation invariant) is used to define which instance variable values are legal. Such a class invariant must be •

established by the constructors of the class (i.e. when a constructor is invoked from a state satisfying its precondition, then it must be terminate in a state satisfying the class invariant).

•

preserved by each of the methods of the class when they are called from states satisfying their preconditions (i.e. when these methods are invoked from a state that satisfies their precondition and the class invariant, then they will terminate in a state satisfying the class invariant.)

Provide a class invariant for the IntegerSet class that is strong enough to show that both methods size and get are correct with respect to their specifications in the IntegerSet class (i.e. when these methods are invoked from a state that satisfies their precondition and the class invariant, then they will terminate in a state satisfying their post-condition.) The class invariant can be expressed in a combination of English and Java notation. Question 2 (b) [4 marks] Provide a correct implementation of the following method remove for the IntegerSet class. The implementation of the whole class IntegerSet should remain correct after the addition of your remove-method implementation. (Your method should preserve the class invariant from the answer to part (a) of this question.) /** * Removes an integer from the set. * * @ensure if x is contained in the set, then it is removed * from the set, otherwise the set is unchanged by * this operation. */ public void remove(Integer x) { }

Page 7 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 3 [12 marks] Consider the method intersect below. (In the specification, \result is used to refer to the return value of the method.) /** * Returns true if and only if the sorted arrays x and y * contain at least one integer in common. * * @require x!=null && y!=null && !x.contains(null) && * !y.contains(null) && and both arrays of integers * x and y are sorted in ascending (integer) order. * @ensure \result is true iff there exists an integer n such * that x.contains(n) and y.contains(n) */ public static boolean intersect(List x, List y) { int i = 0; int j = 0; while (i < x.size() && j < y.size()) { if (x.get(i).equals(y.get(j))) { return true; } else if (x.get(i) < y.get(j)) { i++; } else { j++; } } return false; } Question 3 (a) [6 marks] Provide a set of black-box test cases for the method. Each test case should include the input values, the expected return value or exception thrown, and a brief justification for the test case. Question 3 (b) [6 marks] Provide a set of white-box test cases for the method. Again each test case should include the input values, the expected return value or exception thrown, and a brief justification for the test case. It is OK to include test cases that are also listed in the answer to Question 3(a). (Path coverage for loops is expected.)

Page 8 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 4 [12 marks] Question 4 (a) [6 marks] Provide a recursive implementation of method intersect from Question 3. You may use one or more additional (auxiliary) methods to do this. Comments, including specification of methods, are not required. Question 4 (b) [6 marks] Consider the following requirements for a program for simulating traffic in a seaport. A seaport has at least one wharf where ships can dock. At any point in time, a wharf can have at most one ship docked at it, and a first-in-first-out queue of ships waiting to dock at the wharf. If there is at least one ship waiting to dock, then the dock cannot be empty (that is, ships dock as soon as they are able to). Each ship has an expected arrival time at the seaport, and an amount of time (a duration) that the ship needs to dock for. When a new simulation is started, it is given the number of wharves at the seaport, and the details of the ships that are expected to arrive. Time is modelled in discrete units starting from 0. The simulation can be advanced one time interval at a time. It commences at time 0, in a state where there are no ships docked at any of the seaport’s wharves (or waiting to be docked at those wharves). When the simulation is advanced a time interval, the traffic simulator first updates each wharf, so that any ship that has been docked at a wharf for it’s scheduled amount of time is removed from the wharf, and the next ship waiting to use that wharf (if any) is moved onto it to dock. Then, any ships that are scheduled to arrive at that unit of time are assigned to wharfs (in any order). When a ship is assigned to a wharf, it is assigned to the wharf with the smallest wait time, where the wait time is calculated based on the remaining time the current ship (if any) docked at the wharf needs, plus the docking time required for all the ships already waiting to use the wharf. If a ship is assigned to an empty wharf, it is immediately docked at the wharf, and if it is assigned to a wharf that is currently occupied, it is added to the end of the waiting queue for that wharf. After time has been advanced an interval in the simulation , the current state of each wharf in the seaport is printed to standard output. The simulation terminates when there are no remaining ships to arrive at the port, and there are no ships docked at any of the wharves, or waiting to dock at any of the wharves. Design a class PortSimulator that implements the seaport-simulating program in an Object-oriented way, along with at least two other analysis or design classes that it uses to implement the functionality. For the PortSimulator class, and the other classes in your design: •

give a brief one-sentence description of the purpose of the class, and a brief description of how it relates to the other classes.

•

briefly list any queries, commands and constraints that you think that class should have.

Your design should be easy to implement without having to perform further design tasks.

Page 9 of 13

Semester One Final Examinations, 2015

CSSE2002 Programming in the Large

Question 5 [12 marks] Consider the following class definitions. (\result in the method specifications refers to the value returned by the method.) public class A { /** * @require list != null && 0 < min && min < max * @ensure \result is the set of all of the positive * integers n in list such that min...