Section Readings: 1.1
Problem 1. (Euclid’s Algorithm) Implement the static method gcd() in Euclid.java such that it uses Euclid’s algorithm (see page 4 of text) to compute and return the greatest common divisor (GCD) of the arguments p and q.
java Euclid 105 24
3
java Euclid 1111111 1234567
1
Problem 2. (Factorial) Implement the static method ln() in Factorial.java such that it computes the value of ln(N!) recursively. Recall that N! = 1 2 (N 1) N, 0! = 1, and ln(x + y + z) = ln(x) + ln(y) + ln(z).
java Factorial 100 363.7393755555636
java Factorial 1000 5912.128178488171
Problem 3. (Histogram) Implement the static method frequency() in Histogram.java that takes an array a[] of int values and an integer M as arguments and returns an array of length M whose ith entry is the number of times the integer i appears in the argument array.
java Histogram 0-0 1-3 2-2 3-2 4-4 5-2 6-0 7-3 8-3 9-3
10-4
11-4
Problem 4. (Whitelist) Add to the BinarySearch test client the ability to respond to a second argument: + to print numbers from standard input that are not in the whitelist,
to print numbers that are in the whitelist.
Spring 2015 1 of 2
CS210 Lab 1 Swami Iyer
java BinarySearch tinyW.txt + < tinyT.txt
50
99
13
java BinarySearch tinyW.txt - < tinyT.txt
23
10
18
23
98
84
11
10
48
77
54
98
77
77
68
Files to Submit:
Euclid.java
Factorial.java
Histogram.java
BinarySearch.java
Spring 2015 2 of 2
