CSE1030 Test 3 Sample Programming Question


This is a sample programming test. All of the recursive methods you are asked to write operate on lists; this may not be the case for the actual test.


Setting Up

In eclipse:

  1. Create a new Java Project (perhaps called test3)
  2. In your project, create a new Package called cse1030.test3

Programming Question

Complete the utility class IntegerLists which provides three methods that operate on lists of integers. You MAY NOT add any additional import statements, except for testing purposes. Your methods must be recursive, and may use only the following methods from List:

The methods that you need to implement are described below.

public static Integer minimum(List<Integer> t)
This method finds the minimum integer in a list. The minimum element in a list t can be found recursively as:

Math.min(first, u)

where first is the first element in t, and u is the original list t with the first element removed.

public static int indexOf(Integer i, List<Integer> t)
This method finds the index of the first occurrence of the integer i in the list t; it returns -1 if i is not equals to some element in t. A similar method for LinkedList was discussed in the lectures on Tue Nov 19 and Thu Nov 21.

public static void sort(List<Integer> t)
This method sorts a list t so that the elements are in ascending order. Perhaps the easiest way to recursively sort a list is to:

  1. find the minimum element m in the list [Hint: Use your freshly implemented minimum method]
  2. find the index of m in the list [Hint: Use your freshly implemented indexOf method]
  3. swap the first element of the list and m (this moves the smallest element of the list to front of the list) [Hint: Use the list method set twice]
  4. recursively sort the sublist u, where u is the sublist of t starting from the second element of t

Now complete the controller for the following GUI application:

The application allows the user to type in a string of integers (separated by spaces). When the user presses the Process the list button, the string is converted into a list of integers, and the list is processed to:

You should be able to infer the sequence of method invocations required by examining the APIs for the model and view.

The API for all of the classes in this test can be found at the following link:

You will require the following the JAR file:

Starter code for the two classes is available:

Note that the GUI also serves as a test program.