Name __________________________ Date: 11/30/05

AP CS Java - Mr. Merlis Block 4 ACE

Day 28 – WHAT’S GOING ON

TODAY’S AGENDA

- Labs 1 and 2 are due TODAY. Lab 3 is due FRIDAY by the end of class.

- Go over questions 21-30 from Practice Exam A1.

- Work on labs.

LAB 2 – Working with Arraylist and Random

èOverview, Fill, print and sort an ArrayList with 50 random integers in the range 100 to 1000.

WHAT I EXPECT

- YOU SHOULD ALREADY HAVE A FOLDER called “Labs” (from last class)

- Create a new project called “Lab2List”

- Create the classes ListWorks and an application program called “Lab2”

- All methods should be static.

Visit the website to see the main method.

Concepts and Classes

ArrayList, Integer, EasyFormat, Iterator, compareTo, Java.util.Random, Math.random(), overloading, selection sort, cast operator

LAB 3 – Permutations (20 points)

Create a class to generate permutation of consecutive integers. For example, 1,2,3,4 are consecutive integers. 2,4,3,1 is a permutation of those integers (a rearrangement).

WHAT I EXPECT

- YOU SHOULD ALREADY HAVE A FOLDER called “Labs” (from last class)

- YOU SHOULD ALREADY HAVE A PROJECT called “Lab2List”

- Create the classes PermutationGenerator and an application program called “Lab3”

The PermutationGenerator should generate permutations for any range of numbers. Fill an ArrayList, itsNumbers, with the Integers low to high in the constructor (sequentially, in order).

The method nextPermutation returns a list of the itsNumbers in random order with no repetitions. To do this create a new list and remove each number randomly from the original list and append it to the new list. The list element to be removed is selected randomly. Be sure to replace the instance variable holding the ArrayList for the class with the permutation before returning it.

PermutationGenerator pg = new PermutationGenerator(1, 52);

ListWorks.print(pg.nextPermutation(),13);

Use the above to test your class and methods. (This shuffles a deck of 52 cards).

Extra Credit – Run an experiment to calculate the number of times a list has to be permutated to be back in order. Write static methods for PermutationTest with these headers:

public static boolean inorder(ArrayList list) // returns true if the list is in increasing order

public static int runExperiment(int lengthOfList, int times) // returns the average number of

//permutations necessary to put a list in order. Do at least (3,100), (4,100), (5,100).