Trial Lab
CS1020 AY2010/11 Semester 2
Date of release: 20 January 2011, Thursday
Submission deadline: 30 January 2011, Sunday 23:59hr
School of Computing, National University of Singapore

0 Introduction

The purpose of the trial lab (lab0) is to familiar yourself with the UNIX environment, vim editor and CousrMarker software. It will help you iron out any problems before taking take-home and sit-in labs. Please take note of the following issues before attempting this lab:

Trial lab is not graded. 1 attendance mark would be awarded upon (1) successful submission of your program to CourseMarker; (2) shown genuine effort in your program (regardless of the result of dynamic test).
If you have no idea about UNIX environment, CourseMarker issue or vim editor, please read this article first: Getting Started. If you still have problems with CourseMarker, you may post your queries in the IVLE forum, email cmarker@comp.nus.edu.sg, or approach the Technical Services counter at the ground floor of COM1.

This lab requires you to do 1 exercise.

1 Exercise 1: Collatz Conjecture

1.1 Task statement

There is simple yet still unresolved question in computing, known as the Collatz Conjecture. The conjecture revolves around the following computation:

Given N, a positive integer:

The Collatz Conjecture states that:

If we repeatedly apply the computation above, using the result of f(N) as the next N, the process will always reduce to the value of 1.

For example, if N is 6:

f(6) = 3 (6 is even, 6/2 = 3)
f(3) = 10 (3 is odd, 3*3+1 = 10)
f(10) = 5
f(5) = 16
f(16) = 8
f(8) = 4
f(4) = 2
f(2) = 1 (Reached!)

It is very fascinating to note that the value of N has no known relationship with the number of steps required. For example, N=6 takes 8 steps, N=27 takes 111 steps! The number of steps required to reach the value of 1 is known as the cycle length.

Write a program Collatz.java that (1) reads two positive integers i and j from command line; (2) calculate the cycle length for every number in the range [i, j] (both inclusive); (3) find the number that has the largest cycle length; (4) print out this number and its cycle length.

For example, sample run#1 shows that 6 has the largest cycle length among all the integers in the range [3, 6] and such largest cycle length is 8.

Check sample runs for input and output format; submit your program through CourseMarker. Maximum number of CouseMarker submission allowed: 200.

1.2 Sample run

Two sample runs using interactive input (user's input shown in blue; essential output shown in bold purple).

3 6
6 8

20 27
27 111

1.3 Important Notes

You will download a skeleton program Collatz.java from CourseMarker after setting up this exercise. Edit the skeleton file to formulate your solution.
Modular programming is encouraged and you may also try to apply simple OO design in this question. But don't create any additional Java class other than the one given.
CourseMarker awards correctness marks ONLY if your output adheres to the given format. Hence, do not add any other characters (such as blanks) that are not asked for in your output.
When checking the feedback from CourseMarker, focus on DYNAMIC TESTS only and ignore all other sections.

1.4 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that more practice might be needed.

30 minutes

Last update: January 19, 2011