Description
Section Readings: 1.1, 1.2
Problem 1. (Three Sort) Write a program ThreeSort that takes three int values as commandline arguments and prints them in ascending order, separated by spaces. Use Math.min() and Math.max(); you are not allowed to use any conditionals.

java ThreeSort 1 2 3
1 2 3

java ThreeSort 1 3 2
1 2 3

java ThreeSort 2 1 3
1 2 3

java ThreeSort 2 3 1
1 2 3

java ThreeSort 3 1 2
1 2 3

java ThreeSort 3 2 1
1 2 3
Problem 2. (Remove Duplicates) Modify InstrumentedBinarySearch from Lab 2 to remove any duplicate keys in the whitelist after the sort. The number of keys examined in this case should be smaller than when the duplicates are not removed. Do you see why? You are not allowed to use any collection data type (eg, ArrayList). Hint: Determine the number of unique elements in whitelist[]; copy those elements into a new array of that size; and make whitelist point to that array.

java InstrumentedBinarySearch tinyW.txt < tinyT.txt
65
Problem 3. (Relatively Prime Numbers) Write a program RelativelyPrime that takes an int value N as a commandline argument and prints an NbyN matrix such that the element in row i and column j (1 i; j N) is a “*” (a star) if i and j are relatively prime (ie, GCD(i; j) = 1) and ” ” (a space) otherwise. The row numbers should be printed at the end of each row.

java RelativelyPrime 10
**********1
* 
* 
* 
* 
* 
2 
* * 
* * 
* * 
* 
3 

* 
* 
* 
* 
* 
4 
* * * 
* * 
* * 
* 
5 

* 
* 
* 
6 

* * * 
* * * 
* 
* * 
7 

* 
* 
* 
* 
* 
8 
* * 
* * 
* * 
* 
9 

* 
* 
* 
* 
10 
Spring 2015 1 of ??
Problem 4. (Matrix Library) Write a Matrix library that implements the following API:
public class Matrix
// vector dot product
public static double dot(double[] x, double[] y)
// matrixmatrix product
public static double[][] mult(double[][] a, double[][] b)
// transpose
public static double[][] transpose(double[][] a)
// matrixvector product
public static double[] mult(double[][] a, double[] x)
// vectormatrix product
public static double[] mult(double[] x, double[][] a)

java Matrix < matrix.txt
x:
3
1.00000 1.00000 1.00000 y:
3
1.00000 2.00000 1.00000 a:
3 3
1.00000 4.00000 1.00000
2.00000 3.00000 5.00000
1.00000 6.00000 2.00000 b:
3 3
0.00000 9.00000 7.00000
4.00000 6.00000 1.00000
2.00000 4.00000 5.00000 dot(x, y) = 4.0
mult(a, b):
3 3
18.00000 37.00000 16.00000
22.00000 56.00000 42.00000
28.00000 53.00000 23.00000 transpose(a):
3 3
Spring 2015 2 of ??
1.00000 2.00000 1.00000
4.00000 3.00000 6.00000
1.00000 5.00000 2.00000
mult(a, x):
3
6.00000 10.00000 9.00000
mult(y, b):
3
10.00000 25.00000 14.00000
Problem 5. (Rational Numbers) Implement an immutable data type Rational for rational numbers that supports addition, subtraction, multiplication, and division. Use Euclid’s algorithm (see page 4) to ensure that the numerator and denominator never have any common factors (eg, 4/8 is represented as 1/2), and do this within the twoargument constructor.
public class Rational

constructs rational number n / d. Rational(long n, long d)

constructs rational number n / 1. public Rational(long n)

sum of this number and b.
public Rational plus(Rational b)

difference of this number and b. public Rational minus(Rational b)

product of this number and b. public Rational times(Rational b)

quotient of this number and b.
public Rational quotient(Rational b)

is this number equal to b?
public Rational plus(Rational b)

string representation public String toString()
$ java Rational 40
PI (using Leibniz series) = 3.09162
Spring 2015 3 of ??
In case you are curious about the test client, it computes the value of using the celebrated Leibniz series, whose n terms are

= 1
1
+
1
1
+ +
1
:
4
3
5
7
2n 1
The approximation is not very good because Leibniz series converges extremely slowly and we can’t try bigger values of n because it causes over ow in the long data type we use to represent the numerator and denominator in Rational.
Files to Submit:

ThreeSort.java

InstrumentedBinarySearch.java

RelativelyPrime.java

Matrix.java

Rational.java

report.txt
Spring 2015 4 of ??