CS 1401 Introduction to Computer Science Fall 2012 Test 2, MW class section, November 14, 2012

Name: __________________________________________________________

Background: On this day, in 1716, the famous scientist Gottfried Leibniz died. With Isaac Newton, he was one of the founders of calculus. To computer scientists around the world, he is most known for his research on binary system -- which is now the basis of all computers -- and for his strong belief that all the knowledge can be described in terms of 0s and 1s.

1. A local grocery store has a discount on 12-can packages of diet coke: if you buy one or two, you pay \$4.50 each, but if you buy at least three, the price per package drops to \$3.50. So, if you buy two packages, you pay 2 x \$4.50 = \$9.00, but if you buy four, you pay 4 x \$3.50 = \$14.00. Define a Java method cokes(int n) that, given a number of packages, returns the amount you need to pay. In the main program, apply this method to compute the price of three packages (i.e., take n = 3).

```

```
2. In the history of science, Leibniz is known for a prolonged argument with Newton about who was the first to discover calculus. Let us design a program that would help in resolving such disputes. Let us assume that, for some invention, we have an array invention that stores the years in which different people discovered this idea:
• invention[0] stores the year in which the first researcher came up with this idea,
• invention[1] stores the year in which the second researcher came up with this idea,
• etc.
Write a method that, given an array of integers, computes the index of its smallest element. Trace your method step-by-step on the example of an array that has three elements: invention[0] = 2000, invention[1] = 1998, and invention[2] = 2002.

```

```
3-4. The names of the researchers who contributed to development of binary systems are stored, in alphabetic order, in an array names.
• Write a method for linear search, and trace, step-by-step, how your method will search for Leibniz in the array consisting of three names Atanassov, Leibniz, von Neumann.
• Explain, on the example of an extended array consisting of six names Atanassov, Berry, Boole, Leibniz, von Neumann, Zuse, how the following binary search method will look for the name Leibniz.
```  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 Pioneers describing computer pioneers, each element of which contains three fields: the pioneer's name, his or her birth year, and the string describing this person's contribution to computing. Do not forget to add a constructor method and accessor ("get") and modifier ("set") methods. In the main program, create a new object with your own name.

```

```
6. A professor grades the test and places the grades into a computer. Write a program that would help. This program should:
• ask the user whether he is done with grading, by typing D (meaning "done") or N (meaning "not yet done");
• if the professor is not yet done with grading, the program should read the grade of the next student from the keyboard and store this grade in the next element of the array grades:
• the grade of the first student is stored in the element grades[0];
• the grade of the second student is stored in the element grades[1];
• etc., until the professor says "done" (D).