Description
Problem A: Collatz Conjecture
Consider the following procedure on integers:
If the number is even, divide by two (x ← x/2), otherwise multiply by three and add one (x ←
3x + 1). Repeat until the number 1 is reached.
The Collatz conjecture, also known as the 3x + 1 conjecture, states that the procedure will always reach 1
for any starting positive integer, rather than entering a loop or increasing towards infinity. Implement a
class Collatz that reads positive integers and for each integer, prints every number in the sequence produced
by the above procedure, starting with the given integer. After printing the sequence, print the number of
steps that it took to reach 1, and the largest number in the sequence. The program should read from input
file collatz.in and print to screen.
Extra Credit: Prove the Collatz Conjecture to be true, or find a counterexample. In order to receive credit,
your proof or counterexample must be accepted for publication by a reputable journal of mathematics.
Completing this extra credit will result in an automatic grade of A for this course.
Input (Collatz.in):
The input file contains multiple test cases, one per line. Each test case contains a positive integer between
1 and 10000. The input is terminated by the end of file.
Output (Standard output):
For each test case, print four lines of output. The first line contains a heading (see format in sample I/O),
followed by the Collatz sequence starting with the given integer and ending with 1, separated by single
spaces. The second line contains the number of steps taken, and the third line contains the maximum
number reached in the sequence. The fourth line should be a blank line without spaces. You must follow
the sample output format exactly to receive full credit.
Sample I/O:
See Collatz.sample.in and Collatz.sample.out for sample input and output. You have to copy
Collatz.sample.in into Collatz.in in order for it to work properly with your program. The content
of Collatz.sample.out should match exactly with what your program prints to screen.
Problem B: Factors
Implement a class Factors that reads positive integers and prints out all non-trivial factors of each integer.
The program should read from input file Factors.in and output to screen.
Extra Credit: Write your program in such a way that it runs quickly (in a few minutes) on numbers that
are products of two 100-digit prime numbers. In order to receive credit, your algorithm must be accepted
for publication by a reputable journal of mathematics or computer science. Completing this extra credit will
result in an automatic grade of A for this course.
Input (Factors.in)
The input file contains multiple data cases, each consisting of a single line containing a single positive
integer. Each integer will be between 2 and 1,000,000. End of input is terminated by end-of-file.
Output (Standard output)
For each test case, print all non-trivial factors (in ascending order) for the number given, or report that the
number is prime (if it has no non-trivial factors). A non-trivial factor of a number, n, is a number other
than 1 or n that evenly divides n. For example, 12 has the non-trivial factors 2, 3, 4, and 6. You must
follow the sample output format exactly to receive full credit.
Sample I/O
See Factors.sample.in and Factors.sample.out. You have to copy Factors.sample.in into
Factors.in for it to work properly with your program. Your output to screen must match exactly with
Factors.sample.out in order to receive full credit.
Problem C: Reverse numbers
Implement a class Reverse that reads sequences of digits, reverses each sequence, and prints out the
reversed sequence in English. The program should read from input file Reverse.in and print output to
screen.
Input (Reverse.in)
The input file contains multiple data cases, each consisting of two lines. The first line of each data case
contains a single positive integer, n. The second line contains n integers, separated by single spaces, each
guaranteed to be between 0 and 9, inclusive. End of input is determined by end-of-file.
Output (Standard output)
For each test case, print the numbers in each case in reverse order. Additionally, the numbers should be
spelled out in English (all lowercase) rather than being printed as just digits. You must follow the sample
output exactly to receive full credit.
Sample I/O
See Reverse.sample.in and Reverse.sample.out. You have to copy Reverse.sample.in into
Reverse.in for things to work properly with your program. Your output to screen must match exactly
with Reverse.sample.out in order to receive full credit.
Problem D: Caesar Cipher
Implement a class Cipher that performs a Caesar cipher (also known as a shift cipher) on a given message
in plaintext. A Caesar cipher takes as input a shift parameter k and a message in plaintext and produces as
output the message in ciphertext. In particular, each character is shifted forward by k letters, where the last
and first letter of the alphabet are considered adjacent. For instance, for k = 3, the encryption scheme is:
Plaintext: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ciphertext: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
The message “A SAMPLE PLAINTEXT” would be encrypted as “D VDPSOH SODLQWHAW”
Input (Cipher.in)
There are multiple test cases in the input file, one per line. Each line corresponds to one Caesar cipher to
perform, which contains, in order, the shift parameter k and the plaintext. The shift parameter and the
plaintext are separated by a single space. The shift parameter is an integer, where 0 ≤ k ≤ 100, and the
plaintext will contain only the characters ‘A’ – ‘Z’ (ASCII codes 65-90) and the space character (ASCII
code 32). Each word in the plaintext will be separated by a single space. Each plaintext message will
contain at most 1,000 characters, and will not contain any leading or trailing spaces (except the space
between the shift parameter and the first word of the plaintext). The input is terminated by the end of file.
Output (Standard output)
For each test case, print the ciphertext. You must follow the sample output exactly to receive full credit.
Sample I/O:
See Cipher.sample.in and Cipher.sample.out for sample input and output. You have to copy
Cipher.sample.in into Cipher.in for things to work properly with your program. Your output to
screen must match exactly with sample output in order to receive full credit.
Deliverables
Create a folder with name HW1 and put all four java files (Collatz.java, Factors.java,
Reverse.java, Cipher.java) inside the folder. Then, zip the folder into file HW1.zip. Submit
HW1.zip as an attachment using the “Add Attachments” button. Assignments that are typed into the
submission box will not be accepted. Note that the zipped folder must contain all four source files and
nothing else.
Restrictions
Your program must compile using Java 6.0 or later on the command prompt. It’s okay to develop your
program using the IDE of your choice, but the TAs will use the command prompt to compile your code and
run the programs. Your code should include a header comment with the following information: your name,
course number and date.
/*
Author:
Date:
Course: COP 3330-01
*/
You WILL lose credit if this information is not found in the beginning of each of your programs. You
should also include inline comments to describe different parts of your program.
Execution and Grading Instructions (For TAs)
1. Download HW1.zip and extract the zip file into a folder.
2. Check the source code of each program to make sure it contains header comments, inline
comments and reasonable use of variable names.
3. Copy the sample files (everyone has these) and judging files (only TAs have these) into the
directory.
4. Run the sample execution script (posted with assignment, students can do this part too).
5. Run the judge execution script (only TAs have this, useless for students since they don’t have the
judge files).
6. If all sample and judge output matches the student’s program output, give full credit for execution.
Otherwise, give partial credit base on the situation.
Points Breakdown
Total Points: 160.
1. Colltaz.java
• Execution: 30
• Documentation: 10
2. Factors.java
• Execution: 30
• Documentation: 10
3. Reverse.java
• Execution: 30
• Documentation: 10
4. Cipher.java
• Execution: 30
• Documentation: 10
