CoSc 200 Laboratory #11
Sums, Reversals, and Triangles

Objective: To gain experience with recursion.

This week's assignment has two parts. In the first part, you will write both iterative and recursive approaches to sum a bunch of numbers and to reverse a string. In the second part, you will write a program that will allow a user to create, move, and remove a fractal image recursively.

Download the starter files from this folder or from this zip file.

Sums and Reversals

In order to sum a bunch of numbers, we can add the first number to the second number to the third number and so forth. That is an iterative approach. We can also add the first number to the sum of the rest of the numbers. That is a recursive approach.

In order to reverse a string, we can put the first character at the end, put the second character next to the end, put the third character third from the end, and so forth. That is an iterative approach. We can also place the first character at the end of the reversal of the rest of the string. That is a recursive approach.

Your task is to turn the above ideas into code and provide suitable tests for your methods. The file SumAndReverse.java provides a start.

Triangle Doodle

When we doodle, those of us who are less than gifted artistically often resort to making simple geometric patterns on the backs of our notebooks, envelopes, napkins or whatever. One of the all-time favorites is to draw smaller and smaller copies of a single shape inside of another. For example, one can take a shape like a triangle or rectangle and then divide it up into smaller shapes (perhaps by drawing lines between midpoints of adjacent sides) and then divide each of the new regions and so on until all you have is a big blob of ink on the paper.

Fortunately, Java's drawing resolution is good enough that if we get it to do this kind of doodling, we can produce things quite a bit more interesting than a big blob. For example, repeatedly dividing triangles into smaller triangles can lead to a picture like that shown above.

The boundary of a triangle doodle is determined by three points (1, 2, and 3 in the figure below). These three points determine three midpoints (A, B, and C in the figure). A triangle doodle (usually called Sierpinski's Gasket) consists of three smaller triangle doodles, each of whose boundaries are determined by one of the original points and the two nearest midpoints (the three smaller doodles in the figure are formed by 1, B, C; 2, A, C; and 3, B, C. Once a triangle doodle is small enough, it consists of the three triangles formed by an original point and the two nearest midpoints (see the green triangle doodle in the figure).

By this definition, the "central" triangle formed by sides from the three "outer" triangles is actually outside of the triangle doodle! Only the area inside of the three "outer" triangles is considered to be inside of the triangle doodle. (In particular, the interior of the triangle formed by A, B, and C is considered to be outside of the triangle doodle). This discussion is important for determining whether a triangle doodle contains the point at which a mouse is pressed.

This demo creates triangle doodles based upon three points provided by the user and allows a user to move a triangle doodle by pressing inside the triangle doodle and dragging the mouse.

In order to replicate the demo version, you will need to use or implement the following classes and interface:

TriangleDoodler is the controller class and full source code is provided in the handout. You should not need to change this file, although you may want to comment out parts of it as you incrementally implement the other classes.

TriangleDoodleInterface provides the signatures of the three methods which must be included in the other two classes. There is also a constant MINSIZE. If any side length of a triangle doodle is less than MINSIZE, the triangle doodle consists of three triangles. Again, you should not modify this file, although you may want to comment out parts of it as you incrementally implement the other classes.

Triangle implements the TriangleDoodleInterface. It is the class that corresponds to a single triangle in a triangle doodle. Hence, it is the base case for the recursive construction of a triangle doodle. The starter file contains a fully implemented private method that returns whether two points are on the same side of a line determined by another pair of points. You will use this method in order to determine whether a point is inside of a triangle. For example, a point P is inside the triangle ABC in the figure if and only if the following three conditions hold:
1. P and A are on the same side of the line formed by B and C,
2. P and B are on the same side of the line formed by A and C, and
3. P and C are on the same side of the line formed by A and B.
Visually, a triangle consists of three lines; however, it may be useful to add the three vertices to the list of triangle properties.
TriangleDoodle implements the TriangleDoodleInterface. It is the class that corresponds to a full triangle doodle. There is no starter file for this one. Before you start to implement, ask yourself what methods and properties a triangle doodle should have.

Grading Point Allocations

Note that 19 of the 20 points are for "correctness." For this lab, "correctness" means appropriate recursive or iterative algorithms and reasonable syntax and semantic style as well as appropriate functioning from the user's perspective.

Value Feature

Syntax Style (1 pt total)

1
Descriptive comments

Correctness (19 pts total)

1
Iterative sum

1
Recursive sum

1
Iterative reverse

1
Recursive reverse

3
Tests for the sum and reverse methods

3
Triangle doodle creation

3
Triangle doodle movement when press is inside

3
Triangle doodle non-movement when press is outside

3
Triangle doodle removal from canvas

Submitting Your Work

As with previous lab assignments, you should submit your".java" files through Blackboard. You can either add these files separately before you submit, or you can first zip together these files into a single ".zip" file and submit this single ".zip" file.

Submission Deadline: 3:00pm on Tuesday, April 11. Note that once you submit, it is impossible to submit a revision.

Resubmission and Late Submission Deadline: 9:00am on Tuesday, April 18. A 5 point penalty will be assessed for a resubmission or late submission. These should be submitted to Lab03Late.

Ecstasy is happiness added to ecstacy!

Value	Feature
	Syntax Style (1 pt total)
1	Descriptive comments
	Correctness (19 pts total)
1	Iterative sum
1	Recursive sum
1	Iterative reverse
1	Recursive reverse
3	Tests for the sum and reverse methods
3	Triangle doodle creation
3	Triangle doodle movement when press is inside
3	Triangle doodle non-movement when press is outside
3	Triangle doodle removal from canvas