CS 2401 Test #1

Date: Thursday, September 22, 2011.

Name: ___________________________________________________________________

In the US, September 22 is the American Business Women's Day. It was established to celebrate women's achievements in business. In this test, let us help business women to process their sales data.

1-2. A list of items sold by a female-owned business numbers can be represented both as an array and as a linked list. Write a Java method to convert from an array into an equivalent linked list, with all data elements in the same order. Your method should take in an array and return a linked list.

3-4. Suppose that the array stores the names of the items sold by a business, in alphabetic order. We need to find an index of a given item. Let us use binary search for this. Write Java code for binary search in an array of strings and trace it on the following two examples. In both examples, the list consists of the following items: cars, chairs, computers, desks, pads, pens, software, and textbooks (in this order). In the first example, we look for software. In the second example, we look for cookies (the item which is not on the list). What is the worst-case complexity of binary search? Explain your answer.

5-6. Let us now assume that we store the price of item i sold in month j as a 2D array 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 the items as a linked list. We have recorded two items: computers and desks. After the list is formed, we realized that we missed the item "chairs". Show, step by step, how we can add an element "chairs" at the beginning of the linked list consisting of the elements "computers" and "desks". Write Java code for adding an element to the linked list and draw how the corresponding boxes change.

9-10. A European affiliate of our company keeps a similar record, but in Euros. To get an overall picture of the company finances, we need to convert these values into dollars. Write a Java method that takes an array of Euro values and returns a new array of dollar values. The conversion formula is 1 Euro = 1.4 US dollars. What is the computational complexity of this method?