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: 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.
  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;
        found = true;
      else if (a[mid].compareTo(elem) > 0}{
        upper = mid - 1;
        lower = mid + 1;
      return mid;
      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: The program should also count the number of friends and record it into the variable numberOfFriends.