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.

  1. 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.
  2. 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.
  1. 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:
    1. The string in question
    2. 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)

  2. 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:

    1. 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.
    2. 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)

  3. loopPalindromes(String pal) - This method should perform exactly like the recursive method, but should solve the problem using loops. (2pt)

  4. EXTRA CREDIT:
  5. 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)

  6. 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:
  1. KochSnowflakeFractal: This class will draw a Koch Snowflake Fractal using recursion. It should look something like:
    Iteration 0: Iteration 1:
    Iteration 2: Iteration 3:

  2. SierpinskiFractal: This class will draw a Sierpinski Fractal using recursion. It should look something like:
    Iteration 0: Iteration 1:
    Iteration 2: Iteration 3:

  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:

KochSnowflakeFractal (Total 5pts)

  1. Animator animator - This field holds the Animator object that this fractal should use. This variable should be private. (1/2pt)

  2. KochSnowflakeFractal(Animator a) [constructor] - This constructor sets the instance variable animator to the parameter a. (1/2pt)

  3. draw(int iteration, Point p1, Point p2) -
    1. 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)
    2. 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)

  1. Animator animator - This field holds the Animator object that this fractal should use. This field should be private. (1/2pt)

  2. SierpinskiFractal(Animator a) [constructor] - This constructor sets the instance variable animator to the parameter 'a'. (1/2pt)

  3. 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.
    1. 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)
    2. 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)

  1. Animator animator - This field holds the Animator object that this fractal should use. This field should be private. (1/2pt)

  2. CFractal(Animator a) [constructor] - This constructor sets the instance variable animator to the parameter a. (1/2pt)

  3. draw(int iteration, Point p1, Point p2) -
    1. 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)
    2. 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.

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: 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:

(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:

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...)