Homework 1: Conditionals and Loops
Goals
The goal of this assignment is to write five short Java programs
to gain practice with expressions, loops and conditionals (Sections 1.2 and 1.3 of the textbook).
Part I: Boolean and integer variables
- Write a program Ordered.java
that reads in three integer command-line arguments,
x, y, and z.
- Define a boolean variable isOrdered whose
value is true if the three values are either in
strictly ascending order (x < y < z) or
in strictly descending order (x > y > z),
and false otherwise.
- Print out the variable
isOrdered using System.out.println(isOrdered).
- Be sure to include a file header!
Sample Interactions:
% java Ordered 10 17 49
true
% java Ordered 49 17 10
true
% java Ordered 10 49 17
false
Part II: Type conversion and Conditionals
Background: Several different formats are used to represent color. For
example, the primary format for LCD displays, digital cameras, and web pages,
known as the
RGB format, specifies the level of red (R), green (G), and blue (B)
on an integer scale from 0 to 255. The primary format for publishing books and
magazines, known as the
CMYK format, specifies the level of cyan (C), magenta
(M), yellow (Y), and black (K) on a real scale from 0.0 to 1.0.
- Write a program
RGBtoCMYK.java that converts RGB to CMYK. Read three
integers red, green, and blue (between 0
and 255, inclusive) from the command line.
- Print the equivalent CMYK values using these formulas:
- Hint. Math.max(x, y) returns the maximum of x and y.
Sample Interaction:
% java RGBtoCMYK 75 0 130 // indigo
cyan = 0.423076923076923
magenta = 1.0
yellow = 0.0
black = 0.4901960784313726
- Note: If all three red, green, and blue values are 0, the resulting
color is black, so you should output 0.0, 0.0, 0.0 and 1.0 for the
cyan, magenta, yellow and black values, respectively.
- Be sure to include a file header.
Part III: Euclid's Algorithm
- Write a program GCD.java that takes two positive (non-zero)
integers a and b as command-line arguments.
- Use a while loop to compute the greatest common divisor (GCD) of a
and b via Euclid's Algorithm. (The GCD of two positive integers
is the largest integer that evenly divides both of them.)
-
Euclid's algorithm works by repeated subtraction: if b is larger
than a, subtract a from b.
- Otherwise subtract b from a.
- Repeat this process until one of the two numbers is zero; the other
number is the GCD.
- The key observation is that, if an integer d
evenly divides both a and b, it must also evenly divide a - b. Note that this formulation of Euclid's algorithm differs
slightly from the version in exercise 1.3.28 in the book.
- Be sure to include a file header.
Sample Interactions:
% java GCD 3 5
The GCD of 3 and 5 is 1.
% java GCD 8 12
The GCD of 8 and 12 is 4.
% java GCD 7 14
The GCD of 7 and 14 is 7.
% java GCD 546 822
The GCD of 546 and 822 is 6.
Part IV: Checkerboard
- Write a program Checkerboard.java that takes an integer command-line argument
N.
- Use two nested for loops to print
an N-by-N "checkerboard" pattern like the one below:
a total of N2 asterisks, where each row
has 2N characters (alternating between asterisks and spaces).
- Each line should start and end with the |
character (Shift-\). These are in addition to the 2N characters in
the step above.
- Be sure to include a file header.
Sample Interactions:
% java Checkerboard 4 % java Checkerboard 5
|* * * * | |* * * * * |
| * * * *| | * * * * *|
|* * * * | |* * * * * |
| * * * *| | * * * * *|
|* * * * * |
|
Part V: A drunkard's walk
Background:
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?
- Write a program RandomWalker.java that takes an integer command-line
argument N.
- Simulate the motion of a random walker for N
steps. After each step, print the location of the random walker, treating
the lamp post as the origin (0, 0).
- Also, print the square of the final distance from the origin.
- Be sure to include a file header.
Sample Interactions:
% java RandomWalker 10 % java RandomWalker 20
(0, -1) (0, 1)
(0, 0) (-1, 1)
(0, 1) (-1, 2)
(0, 2) (0, 2)
(-1, 2) (1, 2)
(-2, 2) (1, 3)
(-2, 1) (0, 3)
(-1, 1) (-1, 3)
(-2, 1) (-2, 3)
(-3, 1) (-3, 3)
squared distance = 10 (-3, 2)
(-4, 2)
(-4, 1)
(-3, 1)
(-3, 0)
(-4, 0)
(-4, -1)
(-3, -1)
(-3, -2)
(-3, -3)
squared distance = 18
If you're stuck: First, think about what variables you need to maintain.
You certainly need to read in and store the command-line argument
N.
You also need to store the current location (
x,
y) of the random walker.
What should be the type of the variables
x and
y?
What should be their initial values?
To choose a random direction, consider using the idiom from Section 1.2 to
generate a random integer in a given range.
Part VI: A drunken throng
Background: Now consider a bar at closing time. Instead of
a single drunkard, there are suddenly many staggering around. It's
hard to predict where any single one will end up, but it's useful to
know if any patterns emerge such as how far away they tend to be
from the bar when they all vomit 30 minutes later. (Street cleaners
find this sort of information useful.) The simplest way — and
in many cases the only way — of detecting aggregate patterns
in random processes is to simulate many individual cases and see
what emerges.
- Write a program RandomWalkers.java that takes two integer
command-line arguments N and T.
- In each of T independent experiments,
simulate a random walk of N steps and compute the squared distance.
- Output the mean squared distance (the average of the T squared distances).
- Be sure to include a file header.
Sample Interactions:
% java RandomWalkers 100 10000 % java RandomWalkers 400 2000
mean squared distance = 101.446 mean squared distance = 383.12
% java RandomWalkers 100 10000 % java RandomWalkers 800 5000
mean squared distance = 99.1674 mean squared distance = 811.8264
% java RandomWalkers 200 1000 % java RandomWalkers 1600 100000
mean squared distance = 195.75 mean squared distance = 1600.13064
As N increases, we expect the random walker to end up further and
further away from the origin. But how much further?
- Use RandomWalkers to formulate a hypothesis as to how the mean
squared distance grows as a function of N.
- Use a variety of values for T (as shown above) for testing the program, but for this analysis,
use T = 100,000 trials to get a sufficiently accurate estimate.
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. It is named for the 19th century biologist
Robert Brown; the fact that Dr. Brown has no sense of direction is
completely coincidental.
If you're stuck: To get started, copy RandomWalker.java to a file RandomWalkers.java.
Now, think about what additional variables you need to maintain.
You certainly need to read in and store the command-line arguments N
and T.
In addition to the current location (x, y) of the random walker, you
need an accumulator variable, say totalSquaredDist, that stores the total
sum of squared distances so far.
Nest the loop inside an outer loop that repeats T times and add code
to update totalSquaredDist after each time through the outer loop.
Part VII: Submit
- Download readme_loops.txt, open it in DrJava, and answer the questions.
- Use the "Submission and Scores" link course sidebar to submit
task hw01.
- Log in with your PennKey.
- Upload Ordered.java, RGBtoCMYK.java, GCD.java,
Checkerboard.java, RandomWalker.java
and RandomWalkers.java and readme_loops.txt
using the provided form.
- Click "Submit" to submit your homework. Save the submission
receipt as your proof of submission.
- Remember: Your file names should match the required exactly,
file names including
capitalization. Make sure you submit
the .java files, NOT the .class files.