Project 1 Solution

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






Spring 2015 1 of ??
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







Spring 2015 2 of ??
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







Spring 2015 3 of ??
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:




ThreeSort.java



InstrumentedBinarySearch.java



RelativelyPrime.java



Matrix.java



Rational.java



report.txt





















































































































Spring 2015 4 of ??