Senior Research 2007-2008 "Warmup" Programming Assignments - YOU ONLY NEED TO DO #1,2
Implement the following warmup problems in both Java and C. These warmup programs cover:
general algorithms, single and double dimension arrays, singly linked lists, and binary trees.
Java tutorials from Sun, another
sample java tutorial,
and the following C tutorials:
C Language Tutorial,
C Programming,
C Programming Tutorial,
Programming in C, and
stdio.h
- The 3n + 1 problem
(Sample starter in C - part 1,
C - part 2,
C - part 3,
and
Java version - part 1,
Java - part 2,
Java - part 3,
sample infile)
- Consider the following algorithm to generate a sequence of numbers. Start with an integer n.
If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat
this process with the new value of n, terminating when n = 1. For example,
the following sequence of numbers will be generated for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
- It is conjectured that this algorithm will terminate at n = 1 for every integer n.
This conjecture holds for all integers up to at least n = 1,000,000.
- For an input n, the cycle-length of n is the number of numbers
generated up to and including the 1. In the example above, the cycle length of
22 is 16.
- Part 1 - input 1 number from the keyboard, print the cycle for numbers from the starting value to 1. Also print the cycle length:
Enter value: 22
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Cycle length= 16
- Part 2 - Given any two numbers i and j, you are to determine the
maximum cycle length over all the numbers between i and j, including
both endpoints. Read in two values from the keyboard, print the cycle lenths from val1 to val2. Print the max cycle length:
Enter 2 values: 1 10
1
Cycle length for 1= 1
2 1
Cycle length for 2= 2
3 10 5 16 8 4 2 1
Cycle length for 3= 8
4 2 1
Cycle length for 4= 3
5 16 8 4 2 1
Cycle length for 5= 6
6 3 10 5 16 8 4 2 1
Cycle length for 6= 9
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Cycle length for 7= 17
8 4 2 1
Cycle length for 8= 4
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Cycle length for 9= 20
10 5 16 8 4 2 1
Cycle length for 10= 7
Max sequence cycle= 20
- Part 3 - read in from a text file a series of pairs of values. Compute the max cycle length for each pair of values.
- Input: The input consists of a series of pair of integers i and j, one
pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
- Output: For each pair of input integers i and j, output i, j
in the same order they appeared in the input and then the maximum cycle length
for integers between and including i and j. These three numbers
should be separated by one space, with all three numbers on one line and with
one line of output for each line of input.
Sample Input Sample Output
1 10 1 10 20
100 200 100 200 125
201 210 201 210 89
900 1000 900 1000 174
- (One dimensional arrays): Tally Lab, parts 1 and 2:
C shell - part 1,
Java shell,
sample tally data file,
-------------------------------------------------------------------------------
- (Two dimensional arrays): Implement Conway's Game of Life,
(also see this
simulation and experiment with various life forms
)
- (Linked lists):
Given in the shell programs: Print list, Add first, and RemoveNth - recursive version (removes the nth item in a linked list, item 0 is the first)
Complete:
- RemoveNth - non recursive version
- Add last - add a value to the end of the linked list (the null end)
- (Binary trees): Given in the shell programs: Print InOrder, Insert into Ordered Binary Tree,
Read a file of words into a String array
Complete:
- Insert words (strings) into an ordered binary tree.
- Print the words in order (from the binary tree)