"Warmup" Programming Assignments

Here are the warmup problems:

1. The 3n + 1 problem (program number for judge submission: 100),
   (Sample starter in C, and also Java version)
   (Also, see these shell versions if you need more help: C and Java version)
   • 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. Minesweeper (program number for judge submission: 10189),
   (Sample starter in C (dynamic allocation) and starter in C (static allocation)
   Also see these shell versions if you need more help: C and Java version
3. The goal of the game is to find where all the mines are located within a M x N field.
4. The game shows a number in a square which tells you how many mines there are
   adjacent to that square. Each square has at most eight adjacent squares. The
   4 x 4 field on the left contains two mines, each represented by a "*" character.
   If we represent the same field by the hint numbers described above, we end up
   with the field on the right.

             * . . .           * 1 0 0
   	  . . . .           2 2 1 0
   	  . * . .           1 * 1 0 
             . . . . 	    1 1 1 0
   

5. Input: The input will consist of an arbitrary number of fields. The first
   line of each field contains two integers n and m (both are
   greater than 0 and less than or equal to 100) which stand for the number of rows
   and columns of the field. Each of the next n lines contains exactly m
   characters representing the field.
6. Safe squares are denoted by "." and mine squares by "*". The first field line where
   n = m = 0 represents the end of the input and should not be processed.

7. Output: For each field, print the message Field #x: on the line alone,
   where x stands for the number of the field starting from 1. The next n
   lines should contain the field with the "." characters replaced by the number of mines
   adjacent to that square. There must be an empty line between field outputs.

             Sample input    Sample output
   	  4 4              Field #1
   	  * . . .           * 1 0 0
   	  . . . .           2 2 1 0
   	  . * . .           1 * 1 0 
             . . . . 	    1 1 1 0
   	  
   	  3 5              Field #2
   	  * * . . .           * * 1 0 0
   	  . . . . .           3 3 2 0 0
   	  . * . . .           1 * 1 0 0 
             
   	  0 0
   
     In your ouput and input, you don't need to put spaces between the characters.
   
    

8. Parse a simple language. Write a program to accept or reject strings in the language with the following production rules.
   • L -> (L)L
     L -> [L]L
     L -> lambda
     (lambda means the empty string)
   • Examples:
     • () accepts
     • ()) rejects
     • ([]) accepts
     • ([)] rejects
     • ([(([]))]) accepts
     • empty string accepts