Last Updated: 2017-09-29 Fri 16:02

CSCI 1103 Lab04: Definitely Indefinite Loops

CODE DISTRIBUTION: lab04-code.zip

  • Download the code distribution every lab
  • See further setup instructions below

CHANGELOG:

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 a String in with width 4 padding with spaces on the left if it is too short.
    • %-14s similarly substitutes a String 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

Author: Chris Kauffman (kauffman@cs.gmu.edu)
Date: 2017-09-29 Fri 16:02