CS 2401 Test #1

Date: Wednesday, February 16, 2011.

Name: ___________________________________________________________________

1-2. A list of 50 integers can be represented both as an array and as a linked list.

• Which representation takes longer time to find the second element of the list?
• Write Java code for both representations and explain your answer about time 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, 1, 2, 3, 4, 5, 6, and 7 (in this order). In the first example, we look for the number 6. In the second example, we look for the number 8. What is the worst-case complexity of binary search? Explain your answer.

```

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

```

```
7-8. Show, step by step, how we can add an element 2 at the beginning of the linked list consisting of the elements 14 and 2011. Write Java code for adding an element to the linked list and draw how the corresponding boxes change.

```

```
9-10. At present, 1 US dollar is approximately equal to 12 pesos, so to convert a dollar amount into pesos, we need to multiply this amount by 12. Write a Java method that takes an array of dollar values and returns a new array of peso values by multiplying each element of the original array by 12. What is the computational complexity of this method?