CS 231: Lab #1

Title image Spring 2019

Java and ArrayLists

The goal of this lab period is to get you started on the current assignment. In particular, we'll look at how to import and use the ArrayList class, one of the abstract data types provided by the standard library.

An ArrayList is a flexible array type similar to a Python list. It can be accessed by using an index into the array, and you can append, insert, or remove elements of the array. You can see all the details in the Java ArrayList documentation

The main task for the lab is to develop an algorithm that shuffles the elements of an array to put them into a random order.

Tasks

  1. Project Setup

    Create a working directory for today's lab. Then start a Java file called Shuffle.java.

    + (more detail)

    • Mount your network drive on Personal. In the Finder, use the Go::Connect To Server menu option to mount smb://filer.colby.edu the Personal volume.
    • Navigate to your folder on the Personal volume and create a folder for the current project.
    • Using an editor of your choice, e.g. TextWrangler, create a new Java file and save it in your new working directory.
    • Open the Terminal, then cd to your working directory. You can use the Finder shortcut of first typing cd and a space in the terminal and then dragging and dropping your working directory folder into the Terminal window to get the path.
  2. File Header

    All Java files should include a comment header, describing the file name, the author, and the date, e.g.,

    /**
     * File: Shuffle.java
     * Author: FirstName LastName
     * Date: MM/DD/YYYY
     */	

    +

    The above is an example of a block comment, a capability not available in Python. A block comment starts with /* and ends with */.

    In addition to the standard header above, it's good to include a brief description of the purpose and capabilities of the class at the top of the file.

  3. Import Packages

    Import the ArrayList and Random classes into your file using the following syntax.

    import java.util.ArrayList;
    import java.util.Random;

    +

    Similar to Python, Java uses an import statement to get access to standard or user-created libraries. The java.util library contains standard data types, algorithms, and capabilities. You can use wildcards in import statements, (e.g. import java.util.*, but that may take more time when compiling your code. Unless you need lots of packages, good practice is to import only the packages you need.

  4. Create a Shuffle Class

    Create a class Shuffle that has a main function only. To start a class use the public class keywords followed by the name of the class, then start a block using an open curly bracket {. To define a main function, use the following signature.

    public static void main ( String[] args )	{ 

    +

    Unlike Python, but similar to C/C++, execution of a Java class begins in its main function. The main function must have the signature public static void main( String[] xxx ) where xxx can be a name of your choice. Common practice is to use args or argv for the argument to main, following the C/C++ convention. The parameter to main will contain any strings provided on the command line when the program was executed.

  5. Create an ArrayList of 10 Random Numbers

    In your main function, declare and allocate a new ArrayList object and a new Random object. Then use a for loop to add ten random integers between 0 and 99 to your ArrayList. Look at the documentation for the Random class and the ArrayList class to figure out how. Have your loop print out the random numbers (as they are generated) using System.out.println().

    +

    Unlike Python, in Java you have to declare the type of each variable before you can use it. To declare a variable, use the name of the type and then the name of the variable.

    ArrayList arr;

    In Java you have to use the new keyword to allocate a new object. Use new followed by the name of the object you want to create called as a function, similar to Python.

    arr = new ArrayList();

    Of course, you can do this all on one line and declare and allocate the variable in one step.

    ArrayList arr = new ArrayList();

    ArrayLists are generic classes, which means they are designed to contain any type of object. The class is defined as ArrayList<E>, where E is a type variable. You will be making an ArrayList that should contain Integers, so you should specify Integer in place of E. For example, the following defines an ArrayList that can hold only things of type Integer.

    ArrayList<Integer> arr = new ArrayList<Integer>();

    If you leave out the type specifier in an ArrayList declearation, then it will be of type Object, which is the parent class for all classes. An ArrayList of type Object can hold references to any class type.

    The ArrayList method add is the analog to the append method for Lists in Python. The following would add the value in x to the end of the ArrayList.

    arr.add( x );

    Standard for loops in Java are different from Python but similar to C/C++. A for loop definition has three parts: initialization, loop condition, and loop action. The initialization step occurs only the first time the loop executes, the loop will continue to execute while the loop condition is true, and the loop action will occur after each loop iteration. The following example shows a loop definition that will execute the contents of the loop block ten times.

    for(i=0;i<10;i++) {
    /* loop block code here */
    }

    You will need to either declare the variable i as an int prior to the loop, or you can declare the loop variable in the initialization step of the for loop itself.

    for(int i=0;i<10;i++) {
    /* loop block code here */
    }

    To create random numbers, you need to use a Random object, which must be declared and allocated.

    Random ran = new Random();

    See the documentation for the list of functions the Random object supports. One of those functions is nextInt, which returns a pseudorandom integer. You can specify an upper bound (exclusive) by passing in an integer value. For example, the following returns an integer between 0 and 49.

    int val = ran.nextInt(50);
  6. Print the Values in the ArrayList

    Loop through your ArrayList again, get each value in turn and print it out using System.out.println().

    +

    As specified in the documentation for an ArrayList, to get a value from position i in an ArrayList you need to use the get method. The get method takes the index as the argument and returns the value at that position in the ArrayList. It will throw an error if the index is out of bounds. Like Python, Java is 0-indexed, so index 0 is the first position in the list. The following gets the ith value from the ArrayList arr and assigns it to an Integer variable x.

    Integer x = arr.get(i);
  7. Remove the Values in Random Order

    Loop 10 times and randomly remove one element from the ArrayList each time, printing out the value that was removed and the remaining values in the list (all on one line). You can use System.out.print() to send something to the command line without a newline. Note that you'll have to select a random number that is always strictly less than the number of elements left in the list.

    +

    Use the nextInt method of your Random object to generate random indices. You can use the ArrayList function size to get the number of elements in an ArrayList, which is the upper bound for legal indices.

  8. Change things around so that instead of assigning random numbers to the ArrayList in the beginning it assigns the values 1 through 10. Then run your program multiple times and look at its behavior.

  9. How can you programatically create a random permutation of a set of elements? In other words, given an ArrayList with elements in order, develop a method of creating an ArrayList with those elements in a randomized order. You don't have to do the shuffling in place, but that's an interesting challenge. Come up with a design and implement it. In this week's assignment, shuffling a deck of playing cards involves creating a random permutation of the set of cards in the deck.

    +

    If you start with a set of numbers in order, you already figured out how to remove the values in a random order. What if you put the values withdrawn from the ArrayList into a new ArrayList?

When you are done with this exercise, you can get started on the project.