Project 1 Solution

Description

Section Readings: 1.1, 1.2

Problem 1. (Three Sort) Write a program ThreeSort that takes three int values as command-line 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 command-line argument and prints an N-by-N 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

CS210 Project 1 Swami Iyer

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)

// matrix-matrix product

public static double[][] mult(double[][] a, double[][] b)

// transpose

public static double[][] transpose(double[][] a)

// matrix-vector product

public static double[] mult(double[][] a, double[] x)

// vector-matrix 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

CS210 Project 1 Swami Iyer

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 ra-tional 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 two-argument 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

CS210 Project 1 Swami Iyer

In case you are curious about the test client, it computes the value of using the cele-brated 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:

1. ThreeSort.java

2. InstrumentedBinarySearch.java

3. RelativelyPrime.java

4. Matrix.java

5. Rational.java

6. report.txt

Spring 2015 4 of ??