CS 2401 Test #1

Date: Wednesday, September 21, 2011.

Name: ___________________________________________________________________

In Northern Hemisphere, September 22 is usually considered to be the last day of summer. This is an important day for meteorologists who record the temperature, wind speed, and other weather parameters on each day. Let us help them process the recorded data.

1-2. For each data type (e.g., temperature), daily values form a list. A list of numbers can be represented both as an array and as a linked list. Write a Java method to convert from a linked list into an equivalent array, with all data elements in the same order. Your method should take in a reference to a head node in the linked list and return an array.

3-4. Suppose that the array stores the dates when measurements were made at some remote location, in increasing order. We need to find an index of the value recorded on a given day. Let us use binary search for this. Write Java code for binary search and trace it on the following two examples. In both examples, the list consists of elements 10, 12, 13, 14, 16, 17, 18, and 20 (in this order). In the first example, we look for September 18. In the second example, we look for September 19. What is the worst-case complexity of binary search? Explain your answer.

5-6. Let us now assume that we store temperatures as a 2D array t, so that the temperature at a location i on given day j is stored as t[i][j]. We originally started with an array of size n x n, but it turned out that it is not large enough. Write a code to resize this array to have s > n rows and t > n columns, keeping all of the original data intact and filling the new positions with zeros.

7-8. Suppose that we store temperatures as a linked list. We have recorded two temperatures: 90 (corresponding to September 18) and 88 (corr. to September 19). After the list is formed, we realized that we missed the value 85 measured on September 17. Show, step by step, how we can add an element 85 at the beginning of the linked list consisting of the elements 90 and 88. Write Java code for adding an element to the linked list and draw how the corresponding boxes change.

9-10. Currently, the temperatures are stored in Fahrenheit (F); to compare them with temperatures around the world, we need to convert them to Celsius (C). Write a Java method that takes an array of F values and returns a new array of C values. The conversion formula is tC = (5 / 9) * (tF - 32). What is the computational complexity of this method?