CSCI 1103 Lab07: Collatz Methods
- Due: 11:59pm Monday 10/30/2017
Friday 10/27/2017 - Approximately 0.83% of total grade
- Submit to Canvas
- You may work with one partner on this lab but both partners must submit files and be physically present for Check-offs
- Lab exercises are open resource/open collaboration. You may freely discuss lab topics with other members of the class.
CODE DISTRIBUTION: lab07-code.zip
- Download the code distribution every lab
- See further setup instructions below
CHANGELOG:
- Thu Oct 26 15:02:10 CDT 2017
- The due date for the lab has been extended to Monday 10/30/2017 to account for Project 3 being due this week Wednesday.
1 Rationale
Mastering how to define methods is a critical component of writing computer programs. This lab provides an opportunity to practice defining method that pertain to the Collatz conjecture which was introduced in Lab04. The methods have a variety of parameters and return types. Especially relevant is the need to allocate an array in one method, fill it with interesting values, and return it. This lab also demonstrates how well-designed methods can be re-used in many locations which makes the total body of code shorter and easier to understand.
While there are no completely new techniques used in this lab, it combines everything discussed in the class thus far so is a good chance to consolidate the intellectual territory that should be under control at this point.
Associated Reading
Material from Eck Ch 1-4 is needed for these problems as they include methods, while() loops, for() loops, if/else, arrays, and input/output.
2 Download Lab Code and Setup
As in Lab01, download the code pack linked at the top of the page. Unzip this which will create a folder and create your files in that folder.
File | State | Notes |
---|---|---|
PARTNERS.txt | Edit | Fill in your name and the name of your partner in this text file |
TextIO.java | Provided | Allows easy input calls like TextIO.getInt() |
KTests.java | Testing | Utility routines for all tests |
junit-1103.jar | Testing | For testing, don't try to edit this one |
Problem1Tests.java | Testing | Tests for problem 1 |
Problem2Tests.java | Testing | Tests for problem 2 |
Problem3Tests.java | Testing | Tests for problem 3 |
Problem4Tests.java | Testing | Tests for problem 4 |
Steps.java | Provided | main() method for problem 1 |
Generate.java | Provided | main() method for problem 2 and 3 |
Verify.java | Provided | main() method for problem 4 |
Collatz.java | Create | Create this file and fill it with methods for all problems |
3 Overview
3.1 Write your code in Collatz.java
for all Problems
Unlike previous labs, you will create only one file for this lab,
Collatz.java
. It will contain methods that solve each of problems.
Do not modify any of the files provided. You goal is to write create
a Collatz.java
file that is compatible with the provided files like
Steps.java
and Generate.java
.
There are a series of testing files named as Problem1Tests.java
which have tests for methods required in each problem. This will
allow you to work on each problem separately.
3.2 Collatz conjecture and Collatz Sequences
Recall Lab04 introduced the Collatz Conjecture: starting from any number
- If the number is even, divide it by two.
- If the number is odd, triple it and add one.
This process always seems to converge to the number 1.
We will call a Collatz Sequence a sequence of numbers that obeys this progression. for example
6 3 10 5 16 8 4 2 1
is a Collatz sequence as starting at 6, it follows the rules of halving when even and tripling+1 when odd until 1 is reached.
In contrast the sequence
6 3 10 5 4 2 1 ^^^
is NOT a Collatz sequence as it does not triple+1 on reaching 5 and
6 3 10 5 16
is NOT a Collatz sequence as it does not end with 1.
This lab develops a series of methods to operate on Collatz sequences.
3.3 Structure of the Collatz
Class
Below is the structure the Collatz.java
file which you should
create. Each problem corresponds to one method in the file though
later problems make use of earlier methods.
public class Collatz { public static int steps(int start); // PROBLEM 1 // Given the starting number start, compute how many steps in the // Collatz sequence it takes to reach 1 from start. A step // comprises changing the current value n based on whether it is odd // or even: // // if n is odd, multiply it by 3 and add 1 // if n is even, divide it by 2 // // If steps(1) is called, it should return 0. If start is less than // 1, return -1. Otherwise, use a loop to repeatedly change the // value according to it being odd/even counting each step until it // becomes 1. Return the number of steps. public static void printArray(String idxLabel, String valLabel, int arr[]); // PROBLEM 2 // Print the array arr in two columns with labels at the top. The // output of a call like: // Collatz.printArray("INDEX","VALUE",new int[]{10, 22, 31, 15, 128, 3}); // should appear like the following // // | INDEX VALUE| // | 0 10| // | 1 22| // | 2 31| // | 3 15| // | 4 128| // | 5 3| // // Use the format specifier // "%6s %6s\n" // to prin the initial labels at the top and the format specifier // "%6d %6d\n" // to print each element public static int [] collatzArray(int start); // PROBLEM 3 // Produce an array which is filled with elements in the Collatz // sequence beginning at value start. Use the method steps() to // determine how many steps it will take to reach 1. If steps() // returns -1, the start value is invalid and null should be // returned. Allocate an array of size [steps+1] so that the start // value can be included. Use a loop to fill this array with values // in the Collatz sequence. The start value should be at array index // [0] and the final value at index [steps] should always be 1. public static boolean verify(int [] testSeq ); // PROBLEM 4 // Verify that the given testSeq is a valid Collatz sequence. If // the array is empty (length of 0) it is not a valid sequence so // return false. Otherwise use the method collatzArray() to // generate the real Collatz sequence form the starting point of // testSeq which is at index [0]. If the testSeq array has a // different length than the real sequence, it must be incorrect so // return false. Otherwise use a loop to walk through testSeq and // compare its values to those in real sequence. If any difference // is detected, return false. If all elements in the sequenc are // equal, return true. }
4 Problem 1: Collatz Steps
In Collatz.java
, define the method following method.
public static int steps(int start)
This method takes a start
number and computes how many steps of
halving or tripling+1 it takes to go from that number to 1 in a
Collatz Sequence. No printing should be done during the method, only
internal computation to eventually return an integer. The basic
approach to this method is identical to previous work with the Collatz
sequences:
- Establish a counter variable
- Enter a loop. Since the number of steps is not known ahead of time,
a
while()
loop is a good choice. The loop should continue while the sequence value is larger than 1. - In the loop, use a condition to determine if the current value is odd or even.
- For even values, halve the current value. Print a message reflecting this.
- For odd values, triple and add 1. Print a message reflecting this.
- Each time the loop completes, increase the counter
- When the loop completes, return the counter
There are two special cases to handle.
- If
start
is 1, it has already converged sosteps()
should return 0 - If
start
is 0 or negative, return -1 as Collatz Sequences only apply to positive starting points.
Recall that one can check the method interactively with DrJava's interactions pane.
Welcome to DrJava. > int count = Collatz.steps(5); > count 5 > Collatz.steps(5) 5 > Collatz.steps(3) 7 > Collatz.steps(1024) 10 > Collatz.steps(19) 20
The provided Steps
program also provides a main()
method which
drives the steps()
method.
> javac Steps.java > java Steps Enter starting number: 5 5 converges to 1 in 5 steps > java Steps Enter starting number: 7 7 converges to 1 in 16 steps > java Steps Enter starting number: 3 3 converges to 1 in 7 steps > java Steps Enter starting number: 1024 1024 converges to 1 in 10 steps
5 Problem 2: Printing Arrays Nicely
In several main()
methods, it will be useful to have a method which
prints and array in 2-column table with headers as in
I STUFF 0 1 1 2 2 3 3 4 4 5
In Collatz.java
, write the following method.
public static void printArray(String idxLabel, String valLabel, int arr[])
This method prints an integer array on the screen using the format specifier
"%6s %6s\n"
for the header and
"%6d %6d\n"
for each element. It is an easy method which should only be about 3-5 lines long.
Some demos from DrJava.
Welcome to DrJava. > Collatz.printArray("Index","Value", new int[]{99, 88, 77, 66, 5555, 4, 333}); Index Value 0 99 1 88 2 77 3 66 4 5555 5 4 6 333 > Collatz.printArray("I","STUFF", new int[]{1,2,3,4,5}); I STUFF 0 1 1 2 2 3 3 4 4 5
6 Problem 3: Generating Collatz Sequences
Define the following method in Collatz.java
.
public static int [] collatzArray(int start)
This method creates an integer array filled with a Collatz Sequence
starting from the given start
number. The basic approach is as
follows.
- If the
start
is 0 or less, there can be no Collatz Sequence starting at it. Returnnull
in this case. - Use the
steps()
method to determine how many steps it takes for thestart
to converge to 1 - Allocate an integer array that is this number of steps plus
one. The additional element is for
start
which should always be in the 0th place - Enter a loop to fill in the elements of the array with Collatz
Sequence elements. Note that in this case the number of loop
iterations is known as it was determined above using the
steps()
method and should be stored in a variable which can be used for the loop bounds. - Use the basic approach of halving when even and tripling+1 when odd.
- When the loop terminates and the array is filled with the Collatz Sequence, return it.
Demos from DrJava
Welcome to DrJava. > int [] seq = Collatz.collatzArray(3); > seq { 3, 10, 5, 16, 8, 4, 2, 1 } > Collatz.collatzArray(11) { 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 } > Collatz.collatzArray(19) { 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 } > Collatz.collatzArray(0) null > Collatz.collatzArray(-5) null
The file Generate.java
has a main()
method that drives
collatzArray()
. It also uses the printArray()
method from the
previous problem to generate nicely formatted output.
> javac Generate.java > java Generate Enter starting number: 1024 STEP VALUE 0 1024 1 512 2 256 3 128 4 64 5 32 6 16 7 8 8 4 9 2 10 1 > java Generate Enter starting number: 7 STEP VALUE 0 7 1 22 2 11 3 34 4 17 5 52 6 26 7 13 8 40 9 20 10 10 11 5 12 16 13 8 14 4 15 2 16 1
7 Problem 4: Verifying Collatz Sequences
One may wish to verify that a given sequence is in fact a Collatz Sequence. The following method does this.
public static boolean verify(int [] testSeq )
There are several approaches to this but among the easiest is
exploiting the previously written method collatzArray()
.
testSeq[0]
is the starting number for the Collatz sequence.- Use this
testSeq[0]
andcollatzArray()
to generate a true Collatz Sequence from the starting point. - Compare the lengths of
testSeq
and the true sequence: if they are unequal,testSeq
must be incorrect so returnfalse
. - If the lengths are equal, compare each element of
testSeq
and the true sequence. If any are different,testSeq
must be incorrect so returnfalse
. - If no difference are detected, return
true
.
Here are some DrJava demos.
Welcome to DrJava. > int [] arr = {5, 16, 8, 4, 2, 1}; > Collatz.verify(arr) true > int [] arr = {45, 136, 68, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}; > Collatz.verify(arr) true > int [] arr = {5, 16, 8, 3, 2, 1}; > Collatz.verify(arr) false
Verify.java
provides a main()
method which drives verify()
which
works as follows.
> javac Verify.java > java Verify Enter Collatz sequence length: 4 Enter Collatz sequence elements: 8 4 2 1 This is a Collatz sequence > java Verify Enter Collatz sequence length: 17 Enter Collatz sequence elements: 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1 This is a Collatz sequence > java Verify Enter Collatz sequence length: 5 Enter Collatz sequence elements: 3 16 8 4 2 1 This is NOT a Collatz sequence The actual sequence should be: STEP VALUE 0 3 1 10 2 5 3 16 4 8 5 4 6 2 7 1
8 Getting Credit for this Lab
8.1 Demonstrate your code to Lab Staff (40%)
You should feel free at any time to get help from lab staff as you get stuck on the exercises.
By the end of the lab, make sure to demonstrate your code to a staff member. This will ensure that you receive full credit on the lab. Staff might ask you to
- Change what is printed
- Compile and run on the command line
- Run tests in DrJava or on the command line
- Show how to zip the folder with your programs in it
Be ready to do any or all of these.
8.2 Zip and Submit (60%)
Ensure that file PARTNERS.txt
has your name and the name of your
partner in it. This fill is located with the other Java files for the
lab and can be edited with DrJava.
Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to blackboard.
On Canvas:
- Click on the Assignments section
- Click on the appropriate link for this lab
- Scroll down to "Attach a File"
- Click "Browse My Computer"
- Select you Zip file and press OK