CSCI 1103 Lab04: Definitely Indefinite Loops
- Due: 11:59pm Friday 10/06/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: lab04-code.zip
- Download the code distribution every lab
- See further setup instructions below
CHANGELOG:
Empty
Table of Contents
1 Rationale
Repeating steps is an essential part of any algorithmic process and where the real power of computing comes in. This lab will exercise use of loops to repeat a computation, both when the number of repetitions (iterations) is known ahead of time and when it is not known. Completion of the problems will give exposure to single loops and doubly nested loops to produce table-like output.
Associated Reading: Eck Chapter 3
Chapter 3.3 and 3.4 discusses the basics looping using while()
and
for()
. Chapter 3.2 is also worth considering as it describes issues
related to developing more complex programs which we are doing now.
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() |
CollatzTests.java | Testing | Tests for problem 1 |
HankelTests.java | Testing | Tests for problem 2 |
KTests.java | Testing | Utility routines for all tests |
junit-1103.jar | Testing | For testing, don't try to edit this one |
Collatz.java | Create | Create this file for Problem 1 |
Hankel.java | Create | Create this file for Problem 2 |
3 Problem 1: Collatz Sequences (TESTED)
The Collatz conjecture concerns a peculiar sequence of numbers which always seem to converge to 1. Suppose you are given a positive integer such as 6. Consider doing the following two operations repeatedly.
- If the number is even, divide it by two.
- If the number is odd, triple it and add one.
Starting with n = 6, one gets the sequence
STEP | OPERATION | N |
---|---|---|
init | 6 | |
1 | even: halve | 3 |
2 | odd: triple+1 | 10 |
3 | even: halve | 5 |
4 | odd: triple+1 | 16 |
5 | even: halve | 8 |
6 | even: halve | 4 |
7 | even: halve | 2 |
8 | even: halve | 1 |
It takes 8 steps for N=1 to converge to 1.
Starting instead with 11 the sequence runs.
STEP | OPERATION | N |
---|---|---|
1 | odd: triple+1 | 34 |
2 | even: halve | 17 |
3 | odd: triple+1 | 52 |
4 | even: halve | 26 |
5 | even: halve | 13 |
6 | odd: triple+1 | 40 |
7 | even: halve | 20 |
8 | even: halve | 10 |
9 | even: halve | 5 |
10 | odd: triple+1 | 16 |
11 | even: halve | 8 |
12 | even: halve | 4 |
13 | even: halve | 2 |
14 | even: halve | 1 |
This takes slightly longer, 14 steps to converge to 1. In general there is no known way to predict the number of steps to converge from a given starting point. It is also not known whether all (positive) starting integers converge to 1 or if there is some peculiar number which would create a cycle. All numbers that anyone has ever tried have converged but there are a lot of integers (infinite in fact, but the smallest kind of infinity [yes, there are bigger and smaller kinds of infinity, keep studying CS if you find that intriguing]).
The focus of this problem is a bit more mundane: given a starting number, generate a table similar to the those above giving each value in the Collatz sequence. It is a good use of a conditional inside of a loop for which the number of steps is not known.
3.1 Demos
> javac Collatz.java > java Collatz Start Collatz seq at: (ex: 18) 6 STEP OPERATION N 1 even: halve 3 2 odd: triple+1 10 3 even: halve 5 4 odd: triple+1 16 5 even: halve 8 6 even: halve 4 7 even: halve 2 8 even: halve 1 8 steps for 6 to converge > java Collatz Start Collatz seq at: (ex: 18) 11 STEP OPERATION N 1 odd: triple+1 34 2 even: halve 17 3 odd: triple+1 52 4 even: halve 26 5 even: halve 13 6 odd: triple+1 40 7 even: halve 20 8 even: halve 10 9 even: halve 5 10 odd: triple+1 16 11 even: halve 8 12 even: halve 4 13 even: halve 2 14 even: halve 1 14 steps for 11 to converge > java Collatz Start Collatz seq at: (ex: 18) 1024 STEP OPERATION N 1 even: halve 512 2 even: halve 256 3 even: halve 128 4 even: halve 64 5 even: halve 32 6 even: halve 16 7 even: halve 8 8 even: halve 4 9 even: halve 2 10 even: halve 1 10 steps for 1024 to converge > java Collatz Start Collatz seq at: (ex: 18) 100 STEP OPERATION N 1 even: halve 50 2 even: halve 25 3 odd: triple+1 76 4 even: halve 38 5 even: halve 19 6 odd: triple+1 58 7 even: halve 29 8 odd: triple+1 88 9 even: halve 44 10 even: halve 22 11 even: halve 11 12 odd: triple+1 34 13 even: halve 17 14 odd: triple+1 52 15 even: halve 26 16 even: halve 13 17 odd: triple+1 40 18 even: halve 20 19 even: halve 10 20 even: halve 5 21 odd: triple+1 16 22 even: halve 8 23 even: halve 4 24 even: halve 2 25 even: halve 1 25 steps for 100 to converge >
3.2 Basic Approach
Create your program in Collatz.java
.
- Prompt for a starting number and retrieve it using
TextIO.java
- Do a bit of setup to create variables for the number of steps and current sequence value
- Print a header for the table using the following statement
System.out.printf("%4s %-14s %3s\n", "STEP","OPERATION","N");
This snaky
printf()
does means the following%4s
means substitute aString
in with width 4 padding with spaces on the left if it is too short.%-14s
similarly substitutes aString
into a width 14 field. However, the-
(minus) means left justify rather than the default right justify.%3s
is identical to the first just with a width of 4, right justified.
- 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.
- The messages should use a
print()
format like the following"%4d %-14s %3d\n"
- First is the step number
- Second is the odd/even operation which is one of
"even: halve" "odd: triple+1"
- Third is the current sequence value
- Notice how the field widths of 4, -14, 3, match the header. This will align table entries nicely.
- Make sure to update the step number in loop.
- When the loop finishes, print a message like
8 steps for 6 to converge
Note that this means you will need a variable to keep track of the starting number as it appears in at the end.
Hint: If you struggle with this problem, consult the textbook. It may prove VERY helpful for this problem.
4 Problem 2: A Hankel in Time (TESTED)
A Hanekl Matrix is a matrix (2D table of values) adhering to a special pattern: every anti-diagonal (lower-left to upper right diagonal) has equal values. For example, here are several Hankel matrices:
3 by 3 1 2 3 2 3 4 3 4 5 8 by 8 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 5 6 7 8 9 10 11 12 6 7 8 9 10 11 12 13 7 8 9 10 11 12 13 14 8 9 10 11 12 13 14 15
While the pattern of Hankel matrices is more general than these examples, this problem focuses on producing tables according to the pattern above. These are tables where
- the table is always square
- the upper left value is always 1
- the first row is always
1 2 3 4 ...
- the first column is also always
1 2 3 4 ...
- each anti-diagonal has equal values
4.1 Demos
> javac Hankel.java > java Hankel Size of Hankel Matrix: (ex: 8) 3 1 2 3 2 3 4 3 4 5 > java Hankel Size of Hankel Matrix: (ex: 8) 8 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 5 6 7 8 9 10 11 12 6 7 8 9 10 11 12 13 7 8 9 10 11 12 13 14 8 9 10 11 12 13 14 15 > java Hankel Size of Hankel Matrix: (ex: 8) 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
4.2 Basic Approach
Write your code in Hankel.java
.
- Get a single integer which is the size of the table. It is the number of rows AND columns.
- As is usually the case for tables, a doubly nested loop fits the
problem well. Since the number of iterations is known ahead of time,
for()
loops are good choices here. - The outer loop has a standard 1 to size flavor to it.
- The particular iteration pattern of these nested loops is the
interesting part of this problem. Notice that the first row reads
1 2 3 4 5 ...
while the second row reads
2 3 4 5 6 ...
and the third row reads
3 4 5 6 7 ...
- Exploit this pattern starting each inner loop at the index of the row. Adjust the termination criteria for the loops appropriately for the inner loop.
- Don't overwork the loops: typical solutions are only 7-10 lines long so there isn't much code, just a bit of care to get the numbers ordered correctly.
- Use a
printf()
with "%2d " to get the table entries to line up properly.
5 Getting Credit for this Lab
5.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.
5.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