CS 1401
Introduction to Computer Science
Fall 2012
Test 3, TR 121:20 pm class section, December 4, 2012
Name: __________________________________________________________
Background: On this day, in 1123, Omar Khayyam died. To most
people, he is known as a Persian poet, the author of Rubaiyat, but
mathematicians and computer scientists also know him as a talented
mathematician who invented many useful algorithms for solving
algebraic and geometric problems. His geometric ideas eventually led
to the development of nonEuclidean geometry and Einstein's Relativity
Theory.
1. One of the algorithms invented by Khayyam was an algorithm for
computing a root of arbitrary kth order of a given number
a. In this algorithm, once we have a previous approximation
p, we compute the next one as
n = (1/k) * ((k  1) * p +
a / p^{k1}).
For example, if we use p = 1.0
as the first approximation to square root of 2 (k = 2 and
a = 2.0), we get the next
approximation n = (1/2) * ((2  1) * 1 +
2.0 / 1^{21}) = (1/2) * (1 + 2) = 1.5.
Define a Java method next(int k, double a, double p)
that, given k, a, and the previous approximation p,
uses Khayyam's formula to compute the next approximation to the kth
root of a. Use exceptions to make sure that when we try to apply this
method to the case when p = 0, the method
should return a meaningful error message.
In the main method, apply your method to the above case
k = 2,
a = 2.0, and p = 1.0.
2. Khayyam authored a textbook that was used by many generations
of students all over the world. Let us assume that the names of
the countries
are listed in an array countries, and the array students
stores the numbers of students from different countries who
used Khayyam's textbook to study:
 countries[0] stores the names of the first country, in
which students[0] students use this textbook;
 countries[1] stores the names of the first country, in
which students[1] students use this textbook;
 etc.
Write a method that, given an array of integers, computes the index of
its largest element. In the main program,
use this method to print the name of the country where the largest amount of students
studied. Trace your program stepbystep on the
example when both arrays have two elements: countries[0] = "Persia",
students[0] = 100, countries[1] = "France",
and students[1] = 10.
34. The names of the variables used in Khayyam's algorithm are stored, in alphabetic order,
in an array var.
 Write a method for linear search, and
trace, stepbystep, how your method will search for beta in the
array consisting of three variables alpha, beta, and gamma.
 Explain, on the example of an extended array
consisting of seven variables alpha, beta, gamma, delta, x, y, and z,
how the following binary search method
will look for the variable
delta
public static int binarySearch(String[] a, String elem){
boolean found = false; int lower = 0; int upper = a.length  1;
int mid = 0;
while(!found && lower <= upper){
mid = (lower + upper) / 2;
if(a[mid].equals(elem)){
found = true;
}
else if (a[mid].compareTo(elem) > 0}{
upper = mid  1;
}
else{
lower = mid + 1;
}
}
if(found){
return mid;
else{
return 1;
}
}
Here, a[mid].compareTo(elem) > 0 means that the string
a[mid] follows the desired string elem in the alphabetic order.
5. Design a class Rubaiyat for describing poems composed by
Omar Khayyam, each element of which contains
three fields: the poem's name, the year when it was composed, and
the year when it was first published. Do not forget to add a constructor method and
accessor ("get") and modifier ("set") methods. In the main
program, create a new object corresponding to the poem "The Moving
Finger" composed in 1100 and published in the same year.
6. Omar Khayyam had many friends who supported him
throughout all his life. Write a
program that would ask Mr. Khayyam to record the names of all his
friends. This program should:
 ask Mr. Khayyam whether they are still more
friends to write, by
asking him to type Yes or No;

if there are more friends to add, the program should ask for
the name of the next friend. The program should record the friends'
names into an array
friends:
 the name of the first friend should be stored in the element
friends[0];
 the name of the second friend should be stored in the element
friends[1];
 etc.
The program should also count the number of friends and record it
into the variable numberOfFriends.