Solved-Lab 1- Solution

Description

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.

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:

1. Euclid.java

2. Factorial.java

3. Histogram.java

4. BinarySearch.java

2 of 2