Problem Solving Assignment 4
Part 1 Due: Thursday of week 8 (2/26/2009) at 11:59pm
Point total: 25 points
UPDATE (2/19): I added more discussion of the C
fractal and the Koch Snowflake fractal to the bottom of the webpage.
UPDATE (2/16): I forgot that you need to have
the code for the Animator class in order to compile your fractals.
Oops! I have now linked to it in the section below that describes the
Animator class. It's here.
UPDATE (2/16): The name of the Palindrome
class is now "Palindromes" and the names of the methods are now
"recursivePalindromes" and "loopPalindromes". The tester code and the
webpage did not match up before, so now they do.
We have seen in lecture and readings how recursion can be useful. When there is a big
problem that needs to be solved, splitting it up into smaller versions of that same problem
until it is at it's simplest case can be a lot quicker and more efficient.
In the first part of this assignment, you will be determining
whether or not a string of characters is a palindrome. A palindrome
is a word, phrase,
number or other sequence of units that can be read the same way in
either direction. Here are some
examples of interesting palindromes. For the purpose of this
assignment, you will not be required to take into account white space
or punctuation, so if you have a phrase that is a palindrome you
should test it without white space or punctuation. For example, if you
wanted to use "A man, a plan, a canal, Panama" you should send your
program "amanaplanacanalpanama". If you want to take on the challenge
and modify your code to accept white space and punctuation, there is
extra credit available if you do it correctly.
You will then write the same function, but this time using
loops. Both code should perform exactly the same.
The second part of the assignment will be a little more appealing to
the eye and entertaining. It will also involve recursion, but you will
be creating fractals. The graphics have already been written for you
so that you can play with your code and see direct results, but you
will have to write the recursion code that actually draws the
fractals.
This homework requires skills with recursion and loops.
- Palindromes -- This class will allow the user to input any
string, and it will determine if it is a palindrome. It will either
use looping or recursion, based on what the user specifies.
- Fractal -- These classes will draw a Koch Snowflake
Fractal, Sierpinski Fractal and a C Fractal. It will use recursion and
graphics, the main graphics are given to you through the tester, but
there are some that you will have to write that will be explained
below.
Details
You must put a comment at the top of your code that specifies your:
real name, login name, email address, and PID. You must also include a
two-to-four sentence description of the program. Use a multi-line
comment (/* */). YOU MUST DO THIS FOR EVERY JAVA
FILE!
Comments Comments in the style detailed in the book ARE required.
Your code must be properly commented to receive full credit.
Comments and good style are worth (2pt).
Part 1 - Palindromes
This class will determine whether a string is a palindrome or not using two different methods.
- main() - This is the main method that will
call the other methods to determine if the user has input a palindrome. This
program will take 2 command-line parameters:
- The string in question
- Whether they want loop or recursion to solve the problem
If there are fewer than 2 command-line parameters given, the program
should print the following message, and then exit:
USAGE: java Palindromes (String) (Loop|Recursion)
If there are more than 2 command-line parameters given, the extras will
be ignored and the program continues like normal. Depending on what choice
the user makes (looping or recursion), this method should call the appropriate
method.
The output should look like the following:
> java Palindromes "racecar" Recursion
> This is a palindrome!
> java Palindromes "racecar" Loop
> This is a palindrome!
> java Palindromes "monkey" Recursion
> This is not a palindrome!
> java Palindromes "monkey" Loop
> This is not a palindrome!
NOTE: It should not matter whether the characters are capitalized. For
example, Racecar is a palindrome. Keep in mind though, R != r, so you
might have to modify the input.
(2pts)
- recursivePalindromes(String pal) - This
method will use recursion to determine whether pal is a palindrome or not.
The string
class may be helpful for this assignment. Remeber strings can be used like
arrays, they have a charAt
method that will returns the character at any position in the string, and they
have a substring method that will return a string that is only a portion of
the original string.
The technique you should use in this method is:
-
Base Case: If you reach a string that is either 1 character long or
empty, then the rest of the letters must have matched up, therefore you can
return true.
- Recursive Case:
- Check to see if the first and last letters of the string are equal.
- If they are, send recursivePalindromes the string with those two letters cut
off.
- For example:
recursivePalindromes("racecar")
if(r==r)
recursivePalindromes("aceca")
else
false
etc
The return type for this method is a boolean;
true if it is a palindrome
false if it isn't.
(NOTE: Remember that a palindrome
means the first and last letters are the same, the second and second
to last letters are the same, and so on. If a string is zero or one characters
long, it is considered a palindrome.) (4pt)
- loopPalindromes(String pal) - This
method should perform exactly like the recursive method, but should solve the problem using loops.
(2pt)
EXTRA CREDIT:
- White Space - There are many ways to ignore white space, you can either include it in your palindrome methods as you are checking, or you can write a method that removes all of the white space from the phrase to that all that is left is one long string.
(1pt EXTRA CREDIT)
- Punctuation - There are also many ways to ignore
punctuation. You can use whichever method you like, as long as it works. Creating new methods is ok, including it in your already written methods is also ok.
(2pts EXTRA CREDIT)
Part 2 - Fractals
There are three classes to this part:
- KochSnowflakeFractal: This class will draw a Koch Snowflake
Fractal using recursion. It should look something like:
|
Iteration 0:
|
Iteration 1:
|
|
|
|
Iteration 2:
|
Iteration 3:
|
|
|
- SierpinskiFractal: This class will draw a Sierpinski Fractal using
recursion. It should look something like:
|
Iteration 0:
|
Iteration 1:
|
|
|
|
Iteration 2:
|
Iteration 3:
|
|
|
- CFractal: This class will draw a C Fractal using recursion. It
should look something like:
|
Iteration 0:
|
Iteration 1:
|
|
|
|
Iteration 2:
|
Iteration 3:
|
|
|
Important methods that will be used:
-
The Animator class has two methods:
sleep(int milliseconds) -- Pauses for the amount
specified. Used so that the process of drawing lines can be seen.
drawLine(Point p1, Point p2) -- Draws a solid
line from point p1 to point p2.
NOTE: You do not need to write the Animator class, but you will need the
source code for it in order to compile your fractals. The source code
for Animator.java can be found here.
-
The Point
class has 3 important parts that will be used in this
assignment:
Class Field - x -- This is the x
coordinate where the point is located in the pane.
Class Field - y -- This is the y coordinate where the
point is located in the pane.
Point(int x, int y)
(constructor) -- This is the constructor that creates a new point at
the x and y coordinates specified.
- NOTE: In each class, java.awt.* needs to
be imported.
KochSnowflakeFractal (Total 5pts)
-
Animator animator - This field holds the
Animator object that this fractal should use. This variable
should be private.
(1/2pt)
- KochSnowflakeFractal(Animator a) [constructor] -
This constructor sets the instance variable animator to the
parameter a.
(1/2pt)
-
draw(int iteration, Point p1, Point p2) -
- Base Case: If
this is the last iteration of the recursive call, then a line needs to be drawn
from p1 to p2, and the animator should sleep for 20 milliseconds so that the
line can be seen being drawn. Then it should return to the previous
iteration.
(1pt)
-
Recursive Case: If this is not the last iteration, then the next points
that need to be drawn need to be determined and the recursive calls need to be
made. See
above for an example of iteration 1, to get an idea of what
lines are being drawn.
For this fractal, four lines need to be drawn between each set of points:
- left -- The x-value of this new point should be the sum of (double
the x-value of p1) and (the x-value of p2), then that sum divided
by 3.
The y-value of this new point should be the sum of (double the
y-value of p1) and (the y-value of p2), then that sum divided by 3.
- right -- The x-value of this new point should be the sum of
(the x-value of p1) and (double the x-value of p2), then that sum divided by
3.
The y-value of this new point should be the sum of (the y-value
of p1) and (double the y-value of p2), then that sum divided by
3.
- mid -- The x-value of this new point should be the average
of the x-values of p1 and p2.
The y-value of this new point
should be the average of the y-values of p1 and p2.
- tip -- The x-value of this new point should be the sum of
(the x-value of mid) and (the difference of (the y-value of right) and (the
y-value of left)).
The y-value of this new
point should be the difference of (the y-value of mid) and
(the difference of (the x-value of right) and (the x-value of left)).
Then four recursive calls should be based on the 4 points that were just
created.
- The first call is from p1 to left.
- The second call is from left to tip.
- The third call is from tip to right.
- The fourth call is from right to p2.
The four calls that are being drawn are:
in order from left to right.
More on how to draw the Koch fractal is described below.
(NOTE: Remember on recursive calls you should decrement the iteration
number because one iteration was just taken care of, otherwise you will end up
in an infinite loop)
Once the recursive calls have been made, this method should return, which
will return to the previous iterations call.
This method has no return value.
(4pts)
SierpinskiFractal (Total 5pts)
-
Animator animator - This field holds the
Animator object that this fractal should use. This field
should be private.
(1/2pt)
- SierpinskiFractal(Animator a) [constructor] - This
constructor sets the instance variable animator to the parameter
'a'.
(1/2pt)
-
draw(int iteration, Point p1, Point p2, Point p3) -
This method should draw the Sierpinski triangle of depth
iteration, where p1 is the bottom-left point of the
triangle, p2 is the top point of the triangle, and
p3 is the bottom-right point of the triangle.
- Base Case: If this is a 0-depth Sierpinski triangle,
then this method should simply draw the triangle (i.e. draw lines from
p1->p2->p3->p1). After drawing all three lines, this method should
tell its Animator object to sleep for 20 milliseconds.
(1pt)
- Recursive Case: If this
is not a 0-depth Sierpinski triangle, then you should draw three new
Sierpinski triangles of depth iteration-1. The three points
of each of those triangles need to be determined. See the above examples to get an idea of what triangles
are being drawn. There are three triangles that need to be drawn. The
new points that determine these triangles are the midpoints between the input points.
Three points you will need to calculate are:
- midL -- The midpoint between p1 and p2.
- midR -- The midpoint between p2 and p3.
- bottom -- The midpoint between p1 and p3.
The three new Sierpinski triangles are:
- The triangle using the points (midL, p2, midR).
- The triangle using the points (p1, midL, bottom).
- The triangle using the points (bottom, midR, p3).
Once the recursive calls have been made, this method should
return, which will return to the previous iterations call.
This method has no return value. (4pts)
CFractal (Total 5pts)
-
Animator animator - This field holds the
Animator object that this fractal should use. This field
should be private.
(1/2pt)
- CFractal(Animator a) [constructor] - This
constructor sets the instance variable animator to the parameter
a.
(1/2pt)
-
draw(int iteration, Point p1, Point p2) -
- Base Case: If this is a 0-depth C fractal,
then this method should draw a line from p1 to p2 and sleep for 50
milliseconds. Then it should return to the previous iteration.
(1pt)
- Recursive Case: If this is not a 0-depth C fractal,
then this method should make 2 recursive calls.
See the above images for a reference to what should be drawn.
A useful reference point is:
- newP -- The x-value of this new point should be the sum of
(the sum of the x-values of p1 and p2) and (the difference of the
y-values of p1 and p2), then that sum divided by two.
The y-value of this new point should be the
sum of (the sum of the y-values of p1 and p2) and (the difference of
the x-values of p2 and p1), then that sum divided by two.
The 2 recursive calls should be:
- The points p1 and newP
- The points newP and p2
Once the recursive calls have been made, this method should return.
This method has no return value.
(4pts)
Testing/Grading
We will have a testing program for both Part 1 and Part 2 of this assignment.
The testing code for Part 1 can be copied from here. But please be sure to try any other
test cases that you can think of.
The tester for part 2 will allow you to write your fractals one at a
time, and you can test them individully without having to write them
all at once. You can run the testing program for Part 2 by typing the
following commands on ieng6:
testPSA4part2 {none|SierpinskiFractal.class} {none|KochSnowflakeFractal.class} {none|CFractal.class}
So for example, if you have only completed your
SierpinskiFractal and not the other two, then you could test it by typing:
testPSA4part2 SierpinskiFractal.class none none
The tester will load a GUI application that will allow you to run your
fractal at different iteration depths. You should begin testing your
fractal with small iteration depths (i.e. 0, 1, 2) and then once those
are successful, you can work your way up to larger ones.
The larger the iteration depth you give, the longer it will take for
your fractal to run. This time will grow exponentially as you
increase the iteration depth.
-
For the Sierpinski Triangle fractal, iteration depths beyond
8 will take a VERY long time.
-
For the Koch Snowflake fractal, iteration depths beyond
4 will take a VERY long time.
-
For the C fractal, iteration depths beyond
10 will take a VERY long time.
Turning in your homework
On ieng6 somewhere under your home directory you need to make a folder
called PSA4. All of your files for this assignment must go in
this folder.
Due Thursday Week 8
The files you need to turn in are:
- Palindromes.java - Both of your methods and your main should be included.
- KochSnowflakeFractal.java - Your implementation of the Koch snowflake.
- SierpinskiFractal.java - Your implementation of the Sierpinski triangle.
- CFractal.java - Your implementation of the C Fractal.
You should put this file into a folder named PSA4, then cd
into that folder and run the command bundleP4.
(You will NOT need bookClasses for either part of this assignment)
More about the Koch Snowflake
The Koch Snowflake is probably the most complicated of the 3 fractals
you will have to write, but only because of the geometry
involved. This section will hopefully make that part easier to grasp.
The Koch Snowflake is actually just three copies of the Koch
fractal, linked together. Your code should just draw the Koch
fractal, and the animator will call it 3 times to draw the Koch
Snowflake.
|
|
| The Koch fractal |
The Koch snowflake |
Consider the following image, which illustrates one iteration of the
Koch fractal.
It is drawn at a
slant just to make it more apparent that the baseline of the Koch
fractal will not always be "flat", or parallel to the x-axis. In
general, the two points p1 and p2 can be any two
points in the 2-D plane. Your code must be prepared to draw the Koch
fractal between ANY two points.
In the image above, we have drawn some intermediate points that
will help to make the recursive calls when drawing the Koch
fractal. The first two points to consider are L and
R. If you take the line between p1 and p2
and divide it into three equal-length line segments, then the points
L and R represent the ends of the middle segment.
Once you have calculated L and R, you will want to
find the differences in their x-values and y-values. In this picture,
I have drawn those in blue and labelled them
dx and dy. These values will become important for
later calculations.
Next you will want to calculate the point M, which is the
exact midpoint between p1 and p2.
The last step is to calculate the point T, which is the
tip of the pointed edge of the Koch fractal. To find T, you
will combine the value you got for point M, and the values
you got for dx and dy.
Notice in the drawing that the difference in x-values between
L and R is exactly the same as the difference in
y-values between M and T. Similarly, the difference
in y-values between L and R is exactly the same as
the difference in x-values between M and T.
So, once you have the values of M, dx, and
dy, you can easily compute the value of T.
Once you have computed all of these intermediate points, you must make
your recursive calls to draw the full Koch fractal. The recursive calls you should make are:
- koch(p1,L)
- koch(L,T)
- koch(T,R)
- koch(R,p2)
(You should NOT make a recursive call on koch(L,R), even though I drew that line in the figure).
Remember that only in the case when iterations==0 should you
actually draw any lines. The recursive case does nothing but make the
recursive calls.
More on the C Fractal
Here's some help with the geometry of the C fractal. Consider the
diagram below:
The inputs to this call to the C fractal would be the points
p1 and p2.
The first step is to compute the mid point between p1 and
p2, call it M.
The next useful values to have are the difference in the x-values
of M and p2 (call it dx), and the
difference in the y-values between M and p2 (call it
dy). The values of dx and dy are drawn on
the diagram in blue.
The last point we need to calculate is T, which we can
find using the values of M, dx, and dy.
Notice from the diagram that the difference in x-values between
T and M is equal to dy. Also, the
difference in y-values between T and M is dx.
Now that we have these points, we can make the recursive calls. The
recursive calls you should make are:
- cfractal(p1,T)
- cfractal(T,p2)
NOTE that the order in which you pass the points to the recursive call
makes a BIG difference! Also, only the base case should draw any
lines. The recursive case just makes the recursive calls, and does
nothing else.
(HINT: something you should keep in mind is, will dx be
positive or negative? What about dy? Does it matter? Will your
code work for every case? Hmm...)