Senior Research 2006-2007 "Warmup" Programming Assignments

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.

See new features of Java 1.5 and the following C tutorials: C Language Tutorial, C Programming, C Programming Tutorial, Programming in C, and stdio.h

1. The 3n + 1 problem
   (Sample starter in C, and Java version, 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. 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.

   • 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
     

2. (One dimensional arrays): Tally Lab: C shell, Java shell, sample tally data file,

3. (Two dimensional arrays): Implement Conway's Game of Life, (also see this simulation and experiment with various life forms )
   Shell programs, etc
   • Java: Life shell, Individual.java
   • C: lifeCShell.c
   • Sample starter boards: board.txt, board2.txt, board3.txt,

4. (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)
   Shells:
   • Linked list Java shell, Linked list Node class
   • Linked list C shell

5. (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)
   Shells:
   • Java: BinaryNode.java, BinaryNodeWord.java, BinaryTree.java, ReadFile.java, wordfile.txt
   • C: binarytree.c, filereader1.c