## CS 1401 Introduction to Computer Science Fall 2012 Test 3, TR 12-1: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 non-Euclidean geometry and Einstein's Relativity Theory.

1. One of the algorithms invented by Khayyam was an algorithm for computing a root of arbitrary k-th 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 / pk-1).
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 / 12-1) = (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 k-th 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 step-by-step on the example when both arrays have two elements: countries[0] = "Persia", students[0] = 100, countries[1] = "France", and students[1] = 10.

```

```
3-4. 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, step-by-step, 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.