COS 126

Conditionals and Loops
Programming Assignment

Due: 11:55pm

The goal of this assignment is to write five short Java programs to gain practice with loops, conditionals, and arrays.

  1. Bits. Write a program Bits.java that takes a command-line argument N and uses a while loop to compute the number of times you need to divide N by 2 until it is strictly less than 1. Print out an error message if the integer N is negative.
    % java Bits 0                     % java Bits 8
    0                                 4
    
    % java Bits 1                     % java Bits 16
    1                                 5
    
    % java Bits 2                     % java Bits 1000
    2                                 10
    
    % java Bits 4                     % java Bits -23
    3                                 Illegal input
    

    Remark: This computes the number of bits in the binary representation of N, which also equals 1 + floor(log2 N) when N is positive. This quantity arises in information theory and the analysis of algorithms.


  2. Checkerboard. Write a program Checkerboard.java that takes a command-line argument N, and prints out an N-by-N checkerboard pattern with alternating spaces and asterisks, like the following patterns. Use two nested for loops.
    % java Checkerboard 4             % java Checkerboard 5
    * * * *                           * * * * * 
     * * * *                           * * * * *
    * * * *                           * * * * * 
     * * * *                           * * * * *
                                      * * * * * 
    


    Random walk in the plane

  3. A drunkard's walk. A drunkard begins walking aimlessly, starting at a lamp post. At each time step, the drunkard forgets where he or she is, and takes one step at random, either north, east, south, or west, with probability 25%. How far will the drunkard be from the lamp post after N steps?

    Remark: this process is a discrete version of a natural phenomenon known as Brownian motion. It serves as a scientific model for an astonishing range of physical processes from the dispersion of ink flowing in water, to the formation of polymer chains in chemistry, to cascades of neurons firing in the brain.


  4. Dice and the Gaussian distribution. Write a program TenDice.java that takes a command-line argument N, and flips 10 fair dice, N times. Use an array to tabulate the number of times each possible total (between 10 and 60) occurs. Then print out a text histogram of the results, as illustrated below.
    % java TenDice 1000
    10: 
    11: 
    12: 
    13: 
    14: 
    15: 
    16: 
    17: 
    18: *
    19: ****
    20: 
    21: ***
    22: ******
    23: ********
    24: ****************
    25: *************
    26: **********
    27: *********************************
    28: ****************************************
    29: *********************************
    30: ***************************************************
    31: *****************************************************************
    32: ********************************************************
    33: **************************************************************************************
    34: ***********************************************************
    35: *********************************************************************
    36: ***********************************************************************************
    37: **************************************************************
    38: *****************************************************************
    39: ***************************************
    40: *****************************************************
    41: ************************************
    42: ****************************
    43: ************************
    44: ************************
    45: *********
    46: ***********
    47: *******
    48: ***
    49: **
    50: 
    51: 
    52: *
    53: 
    54: 
    55: 
    56: 
    57: 
    58: 
    59: 
    60: 
    
    Remark: a classic result from probability theory asserts that the shape of the resulting histogram is well-approximated by the ubiquitous bell curve (Gaussian distribution).


Submission. Submit the files Bits.java, Checkerboard.java, RandomWalker.java, RandomWalkers.java, TenDice.java and a readme.txt file documenting your work.