## CS 2401 Test #1

Date: Thursday, February 17, 2011.

Name: ___________________________________________________________________

1-2. A list of 17 real numbers can be represented both as an array and as a linked list.

• Which representation takes longer time to find the third element of the list?
• Write Java code for both representations and explain your answer about computational complexity by tracing this code.

```

```
3-4. Write Java code for binary search and trace it on the following two examples. In both examples, the list consists of elements 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, and 7.0 (in this order). In the first example, we look for the number 6.0. In the second example, we look for the number 6.1. What is the worst-case complexity of binary search? Explain your answer.

```

```
5-6. Write a Java method for computing the product of all the elements of a 2-D array of size m times n. What is the computational complexity of this method?

```

```
7-8. Suppose that we have a linked list consisting of the elements 2, 15, and 2011, and we have a pointer pointing to the element 15. Show, step by step, how we can delete the element 15 to which the pointer points. Write Java code for deleting an element from the linked list and draw how the corresponding boxes change.

```

```
9-10. With the rapidly changing weather, many people watch the weather reports. While the weather is more or less the same on both sides of the border, the TV stations of our two countries use different temperature scales. A temperature in Fahrenheit tF can be obtained from the temperature tC in Celsius by using the formula tF = 32.0 + 1.8 * tC Write a Java method that takes an array of Celsius temperatures and returns a new array of Fahrenheit temperatures -- by applying the above formula to each element of the original array. What is the computational complexity of this method?