CMPU 102 - Assignment 1
Recursion
Assigned (in class): Mon/Tue, Jan. 28/29
Due: Fri, Feb. 8

KSmall (find the k-th smallest element)

In this assignment you will:

  1. solve a problem recursively,
  2. refresh yourself on elements of Java, 
  3. login to your Linux Computer Science account to do all your work,
  4. use NetBeans to modify an existing project, and
  5. use the submit102 script from the Linux prompt to hand in your project.

Summary: You will implement a recursive method that returns the kth-smallest element of an array of integers. The algorithm you will implement recursively partitions an array, as described on pp. 148--152 of the text, until the partitioned element is in the kth position of the array (note: the kth element of a Java array is at index k-1).

Download the starter project

  1. Click here to download the starter project: kth-smallest.zip. 
  2. Save it in your cs102 directory.
  3. Unzip the file.
  4. You should be able to Open this as an existing project in NetBeans (described next)

Launch NetBeans and Open Project

  1. From NetBeans, go to the File menu and select "Open Project" -- or click on the third button from the left on the button bar.
  2. Navigate to your cs102 folder and select the folder named "kth-smallest." 
  3. The "Open Project Folder" button should be enabled. Click it to open the starter project.
  4. You should be able to compile and run the project as is--though the output won't be correct yet.
  5. The top left pane in NetBeans is a more sophisticated version of the top left pane in DrJava. To find your source files, you should be able to navigate down through "Source Packages" and "kthsmallest" to reveal the three source files that comprise this project:
    1. ArrayUtils.java
    2. Main.java
    3. TestArrayUtils.java
  6. Double-click on each of the three Java source files to open them for editing. The upper right pane in NetBeans is tabbed, for selecting which open file you want to edit. 
  7. The only file you will need to modify for this project is ArrayUtils.java. It is in this file you will find a stub for the kSmall method you need to implement.

The ArrayUtils Class and the kSmall( ) method

In class ArrayUtils, you will implement the following method: 

To implement your kSmall method, you will follow the algorithm given in the text at the end of Section 3.3, pp. 148--152. In particular, you should  reread the end of Section 3.3 in the text, and be sure you understand the recursive solution described. The high level solution given proceeds as follows:

  1. Selecting a pivot item in the array (to simplify things, you will always choose the first item as the pivot)
  2. Cleverly arranging, or partitioning, the items in the array about this pivot item
  3. Recursively applying the strategy to one of the partitions

The challenging part will be figuring out how to do step 2. The subproblems are well-described, which should translate directly into your recursive calls. We'll discuss partitioning strategies in class.

Sample Output

When your kSmall() is correctly implemented, you should see tests that look like this (of course, you will have diferent random numbers...):

====================================================================
Array before calling kSmall(11, ...):
    [ -31  77 -46  15 -97  60 -64 -76  75 -71  92 -58 -31 -90 -54 ]
Array after calling kSmall(11, ...):
    [ -54 -46 -97 -64 -76 -71 -58 -31 -90 -31  15  60  77  75  92 ]
kth smallest number = 15
---> Correct!

Notice that in the example above, the 11th smallest number is 15, and that the array after calling kSmall() is correctly partitioned around the location where 15 is stored. You should see only Correct test outcomes.

Once you've run and verified that your kSmall() is working properly, you are ready to submit your project.

Submitting your solution

From a terminal window, type the following commands: 

cd
cd cs102 
submit102 kth-smallest