Lab 03

Short Assignment 03 – Exhaustive Search

Introduction

Today’s lab will be an introduction to the algorithmic structure of exhaustive search and will help prepare you for PA3. The first part of the lab will be to generate all of the binary numbers for an N-bit number, in ascending order. The second part of the lab will be to generate all of the possible dice roll combinations for a six-sided dice. This lab will also reinforce your skills relating to arrays and recursion.

Exhaustive search is where every possible solution is enumerated. This is also known as the brute-force approach. In many cases, exhaustive search is the simplest solution, and the one to try first.

Remember, in lab sessions you can share code. For programming assignments you cannot.

The Assignment

This is the first assignment where you will have multiple classes. Part One should be completed in the Lab3Binary.java file and Part Two should be completed in the Lab3Dice.java file.

Part One: Exhaustively print out 0-2^N - 1, where N is the number of bits, in ascending order in binary.

Part Two: Exhaustively print out the dice rolling combinations for N six-sided dice.

Here’s the package info for both files:

package com.gradescope.lab03;

Submit both .java files to gradescope at once.

Part 1 - Binary Introduction

For Part 1 of this lab we are completing a class that generates an ArrayList in ascending order all with the binary representations of the numbers 0-2^N - 1, where N represents the number of bits.

For example, if N = 2, then the output would be:

[00, 01, 10, 11]

Additionally, this activity relies on the enumerate (exhaustive search) algorithm described in class, so you should refer to those slides for help while working through this lab.

Step 1

Consider what decisions need to be made in order to enumerate over all of the binary numbers starting from 00000 and getting to 11111 (for N = 5).

• What parameters do you need with your enumerate method? What do these parameters represent?

• What value, 0 or 1, should you start setting each bit to? What part of the enumeration method relates to changing the bit’s value?

• How should you move to the next bit? How will you achieve this in your recursive enumeration call?

• Look back at the lecture slides to recall the format of the enumerate algorithm and copy over any necessary code.

Step 2

The enumerate algorithm requires a recursive call of the enumerate method. To conclude this activity, you need to a recursive step and select a base case condition.

• What parameters should be equal for you to stop the recursion?

• Where should the base case be located in your enumerate method?

• Where should you call the method again?

Test case (main)

Your code should run with the following main method:

public static void main(String[] args) {
        ArrayList<String> allSolutions = new ArrayList<String>();
        binary(5, "", allSolutions);
        System.out.println(allSolutions);
    }

Part Two - Dice Introduction

This activity is very similar to the previous binary activity, so make sure to complete that activity first and reuse the enumerate algorithm here.

Step 1

Consider what decisions need to be made in order to enumerate over all of the possible roll combinations for N dice.

For example, if N = 1, then the output would be:

[1, 2, 3, 4, 5, 6]

For N = 2, the output would be:

[11, 12, 13, 14, 15, 16, 21, 22, 23, 24, 25, 26, 31, 32, 33, 34, 35, 36, 41, 42, 43, 44, 45, 46, 51, 52, 53, 54, 55, 56, 61, 62, 63, 64, 65, 66]

• What parameters do you need with your enumerate method? What do these parameters represent?

• What value should you start setting each die to? Is this a different value than the start value used during the binary activity?

• How should you move to selecting the value of the next roll? How will you achieve this in your recursive enumeration call?

• Look back at Part 1 or the lecture slides to recall the format of the enumerate algorithm to copy over any necessary code.

Step 2

The enumerate algorithm requires a recursive call of the enumerate method. To conclude this activity, you need to implement the recursive call and select a base case condition. Think and discuss with your partner the following questions.

• What parameters should be equal for you to stop the recursion?

• Where should the base case be located in your enumerate function?

• Where should you call the method recursively?

Test case (main)

Your code should run with the following main method:

public static void main(String[] args) {
        ArrayList<String> allSolutions = new ArrayList<String>();
        String solution = "";
        roll(2, solution, allSolutions);
        System.out.println(allSolutions);
    }

Resources

Look up methods to take advantage of Java’s libraries.

• System.out.println() is your friend for testing and output
• Declaring an ArrayList:
  • ArrayList<Integer> array = new ArrayList<Integer>();
• Adding a value in an ArrayList:
  • array.add(1);