CS180 Spring 2011

Project 1: Group Clustering

Assigned : Wed Feb 3^rd, 2011

Due : 11:59pm Sat Feb 12^th, 2011

1. Objectives

In this project, you would learn how to:

• Map a problem and its solution into a Java program.

• Write your own Java classes.

• Program with conditionals and loops.

• Sort an array (using Selection Sort).

• Call some provided Java classes to get user input and display your results.

2. Setup

• Login with your UNIX account. Then create a directory named project1 under your cs180 directory. To do that, issue the following commands in the terminal:

  >> pwd

  /home/yourlogin/cs180

  >> mkdir project1

  >> cd project1

• Download file project1.jar and save it into project1 folder.

• Goto Dr Java Menu, Edit -> Preferences -> Resource Location (First option under Categories) -> Extra Class Path -> Click Add. Select the project1.jar file in the menu and Apply.

• Create a Java file called Project1.java which is your main program of this project.

3. Project Description

The instructor of CS180 wants to divide the class into three different groups based on the students’ score of the first lab. The way to form these groups is described as follows:

• Students’ scores in the first group are all higher than the students’ scores in the second group.

• Students’ scores in the second group are all higher than the students’ scores in the third group.

• The gap between the first group and the second group, which is defined as the difference between the lowest score of the first group and the highest score of the second group, and the gap between the second group and the third group are maximized.

The instructor wants to have a program such as it allows him to input each student’s score and display the scores in each group. He also want the scores in each group are displayed in descending order.

4. Steps to Solve the Problem

In this section, we will help you to develop your code incrementally and make use of the classes and methods we have provided to build your program.

Step 1: User input

At first, your program (Project1.java) should be able to ask user to input scores.

However, to simplify this step, we have already implemented two classes cs180.GuiInput and cs180.ConsoleInput. Using GuiInput class allows users to input students’ scores from user interface and ConsoleInput allows users to enter from console. You can use either of the two classes. These classes have been packaged into the project1.jar. All you need to do is to import theses classes into your program and call the corresponding method of these classes.

You should create a method in Project1 called input() to implement this step.

Step 2: Sorting

The results from User Input step would be an array of scores. The next thing you need to do is to sort this array in descending order. It's up to you to choose any types of sorting methods you prefer. Here we suggest you to implement Selection Sort, which conceptually works by comparing the entire array for the lowest score and moves it to the first position. It then compares the rest of the array for the next-lowest score and places it in the second position and so on until all items are in the required order. More formal steps in a Selection Sort algorithm are described as follows:

You should create a method called sort() in your Project1 file to implement the above Selection Sort method. The result of this step is an array sorted in descending order.

Note: You may want to reference Selection Sort for more details.

Step 3: Partition into groups

Once you have the sorted array, the next thing you need to do is to search over this sorted array to find the maximum gap between two consecutive scores. The upper part of the score array belongs to the first group. Then you, again find the maximum gap between two consecutive scores in the lower part of the array. The result of this step is the second and the third group. You can see an example of how groups are partitioned in Figure 1.

Figure 1. An example of partition into groups. The gap between group 1 and 2 is 20 while between group 2 and 3 is 12.

You should create another method called partition() to implement this step.

Step 4: Display groups

In this step, your program should be able to display the scores in each group. To help you with this step, we have implemented two classes cs180.GuiOutput and cs180.ConsoleOutput. Similar to the input classes, GuiOutput prints scores in different groups on user interface and ConsoleOutput prints scores on console. You may use either of the two classes. Do remember that your instructor want to see the scores in each group in descending order.

You should create a method in Project1 called output() to implement this step.

Step 5: The big picture

In the main function of Project1, create an object of class Project1 and sequentially call your implemented methods in the previous steps to solve the problem.

5. Extra credit

Now, in stead of dividing students into three groups as before, the instructor wants the program to divide the students' scores into n different groups where n is any number input from the user.

Your program should take in 'n', the number of groups, as a command line argument. Based on this, divide the students' scores into groups similar to what we have described in the previous sections.

Hint: It may be easier to run your java program from the terminal/shell in order to specify a command line input argument.

6. Grading rubric

Criteria	Points
Coding Standards (see here)	5
Program Compile	10
User Input	10
Sorting	25
Partition into groups	40
Display Groups	10
Extra Credit	10
Total (without extra credit)	100
Total (with extra credit)	110

7. Turn in instructions

• Change your current folder to your cs180 folder and run the turnin command:

  >> pwd

  /home/yourlogin/cs180/project1

  >> cd ..

  >> pwd

  /home/yourlogin/cs180

  >> turnin -v -c cs180=XXX -p project1 project1

*XXX is your recitation section number. Check it here if you don’t remember.