Try our Free Online Math Solver!

Computer Science 1110 Exam
This 90minute 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 twodimensional 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..k1] 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..h1]
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..q1]. 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..q1].
Prev  Next 