# Computer Science 1110 Exam

This 90-minute exam has 6 questions (numbered 0..5) worth
a total of 100 points. Spend a few minutes

looking at all the questions before beginning. Use the back of the pages if you
need more space.

**Question 0 (2 points).** Fill in the information,
legibly, at the top of each page. (Hint: do it now.)

**Question 1 (13 points). Arrays and methods .**

Below to the left is a square array . Write a method that
turns such an array into its transpose, which is

shown to the right. The transpose of a square array arises from switching rows
and columns. If the array is

the pixels in an image, then transposing the image turns it on its side.

You do not have to write loop invariants, although the
practice of writing an invariant for a loop and

stating in a comment at the beginning of the repetend what the repetend does
increases programming effectivity.

And if you want to swap b[h] and b[k], just say that instead of writing it in
Java.

/** = Change m into its transpose.

Precondition: m is not null and is square (the number of rows = the number of
columns) */

**public static void** transpose (int[][] m) {

**Question 2 (27 points). Miscellaneous**

(a) Write a single statement that declares and initializes a two-dimensional int
array b to look like the

table that appears to the right

(b) To the right is a class definition. Below are 5
statements. Draw the

variables that are declared in the statements. Then, execute the statements

one by one, in order , drawing any objects that are created during execution

and storing values in appropriate variables when an assignment is executed.

When storing a value in a variable , cross out, do not erase, the old value.

C h= new C(3, 1);

C k= new C(5, 6);

C j= h;

j.x= j.x + 1;

j.y= h.x + h.y;

public class C { public int x; public int y; public C(int a, int b) { x= a; y= b; } } |

(c) Any positive integer can be reduced to a single digit
by repeatedly adding its digits together until the

result is < 10. For example, change 257 to 25 + 7 and then to 7 + 7 and then to
14 and finally to 5. Or do

it this way: change 257 to 2 + 57 and then to 2 + 12 and then to 2 + 3 and then
to 5. Or, try 257 -> 25 + 7

-> 32 -> 5. There are other ways to do it. Write the following recursive
function. Do not use a loop, and

do not introduce Strings

/** = n reduced to a single digit (by repeatedly adding
its digits. Precondition: n > 0 */

public static int addUp (int n) {

**Question 3 (18 points) **Below is a class Rational.
Complete the bodies of the constructor, and functions

toString and equals. Read the whole class, all of its methods, before doing
anything.

/** An instance is a rational number */ public class Rational { /** Class invariant: the rational number is num / den Restrictions on fields: 1. den > 0 2. if num = 0, then den = 1 3. num / den is in lowest possible terms. E.g. instead of 20/8 or –5/10, these rational numbers are stored as 5/2 and –1/2. */ private int num; private int den; /** Constructor: an instance with rational number n / d. Precondition: d != 0 */ public Rational(int n, int d) { } } } |

**Question 4. **(25 points). Vector v may contain
instances of many different classes, e.g. Rational (see

question 3), Integer, Double, and others. There may be duplicates in v —for
example, two instances of

Rational in class v may contain the same rational number. We want to write
procedures that will remove

duplicates of class Rational from v. By a duplicate, we do not mean the same
object; rather, we mean an

object that contains the same rational number.

Below, two procedures are specified. Write their bodies.
Do not use recursion.

You must use the invariants P1, and P2, which are given both in English and as

pictures, to write loops (with initialization). Remember our principle to rely
on

previously written functions, where possible.

Use v.remove(k) to remove element k from v. |

/** Remove all Rational elements from v[h..] that have the
same value as r.

Precondition: 0 <= h < v.size(). */

public static void removeRationalEquals(Vector v, int h, Rational r) {

// inv P1. No Rational element in

v[h..k-1] has the same value as r */

// Postcondition: no Rational element in v[h..] has the
same value as r

}

/** Remove all duplicate Rational numbers from v (so that
each appears in it only once). */

public static void removeRationalDups(Vector v) {

// inv P2: No Rational instance in v[0..h-1]

has a duplicate in v.*/

Postcondition: No Rational instance in v has a duplicate
in v.

}

**Question 5 (15 points).** Known algorithms.

(a) (10 pts) Write a specification and header for a binary search

function that searches sorted array segment b[p..q-1]. Your

specification may be in terms of pictures , English, mathematical

notation, or a mixture of all of them. But it must be a specification

of binary search as we have presented the algorithm in

class. Note carefully which array segment is to be searched.

(b) (10 pts) Develop the body of the function specified
above. When developing the body, write the invariant

for the loop first. Then develop the loop and initialization using the four
loopy questions. An

answer that does not have a suitable loop invariant will receive no credit. Note
carefully that the

sorted array segment to be searched is b[p..q-1].

Prev | Next |