CS 2401 Test #1

Date: Wednesday, June 27, 2012.

Name: ___________________________________________________________________

1. The 2012 Olympic Games are about to start. To help sports commentators determine in real time how countries are doing, the list of gold medals won by each country was originally saved in an array of countries and an array of medals. Now commentators have requested additional information about countries and medals. To simplify implementation, information has to be transferred from the existing arrays into a linked list to get the additional information requested by commentators into list nodes. Write a Java method to transfer country and gold medal data from the arrays into a linked list with all elements in the same order. Your method should take in a reference per array and return a reference to the head node of the linked list.

2. Use a gold-medal array with the values {1, 2, 3, 4, 5, 6, 10} to return the index of a country that has won 10 medals and use it again to return the index of a country that has won 20 medals. Use binary search to find the index in each case. Write Java code for binary search and trace it for each search. What is the worst-case complexity of the binary search? Explain your answer.

3. The number of gold, silver, and bronze medals won by all countries are stored in a 2-D array with a column per medal and as many rows as countries participating in the Olympic Games. Write a Java method that computes the sum of all the medals won. What is the computational complexity of this method? Explain your answer.

4. Using the linked list in Problem 1 show, step by step, how we can add a new country with its count of gold medals at the beginning of the linked list. Write Java code for adding an element to the linked list and draw how the corresponding boxes change.

5. Six grams of gold are used for each gold medal. Using the gold medal array in Problem two as an example, compute how much gold will be used to make all the gold medals won. Write a Java method to take in the gold medal array and print the amount of gold to be used. What is the computational complexity of this method?