Overview
This project contains two parts. In the first part, you will implement recursive methods for drawing fractals such as the Koch curve and Sierpinski triangles. In the second part, you will implement a LargeInteger class that allows you to do arithmetic calculations whose results are very large, such as calculating large factorial numbers (e.g. 100!) and large integer powers (e.g. 187100). Some of these methods of the LargeInteger class are implemented using recursion.
Learning Goals
Implementing recursive methods to draw fractals and perform arithmetic calculations such as
Continue training yourself on using linked list to solve problems such as implementing the LargeInteger
General Information [Common]
Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty. Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies in detail and by submitting this project you have provided your virtual signature in agreement with these policies.
For some projects, it may be useful for you to write additional java files. Any java file you write MUST be placed in the provided src directory of your Eclipse project.
When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!
In the test directory, we provide several JUnit tests that we refer to as the public tests. We recommend you run the tests often and use them as starting points to test your project. In addition, some of the java files come with their own main functions. You can run them as Java applications to interact with the project.
Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your project. These tests are hidden from you. We recommend that you think about possible test cases and add new @Test cases to your public test files as part of your programming discipline. In particular, you should consider:
Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many methods only accept arguments that are in a particular range.
Does your code handle cases such as when an array or list is empty, or has reached full capacity?
More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.
Import Project into Eclipse [Common]
Begin by downloading the starter project and importing it into your workspace. It is very important that you do not rename this project as its name is used during the autograding process. If the project is renamed, your assignment will not be graded, and you will receive a zero.
The imported project may have some compilation errors, but these should not prevent you from getting started. Specif- ically, we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests. After completing your code, the compilation errors should be gone.
The project should normally contain the following root items:
src This is the source folder where all code you are submitting must go. You can change anything you want in this folder (unless otherwise specified), you can add new files, etc.
support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive changes”, and you should click on the “Yes” button.
test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.
JUnit 4 A library that is used to run the test programs.
JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.
If you are missing any of the above or if errors are present in the project (other than as specifically described below), seek help immediately so you can get started on the project right away.
1. Fractal Drawing
Fractals (https://en.wikipedia.org/wiki/Fractal) are structures or visual phenomena that exhibit self- similarity at every scale. It’s quite easy to generate visually pleasing Fractals using recursion. Before you start, review the Recursion lecture slides to make sure you understand how Fractals are generated and the pseudo-code therein. In this project, you are required to implement four Fractals: the Koch curve, Tree, the Sierpinski Triangle, and Carpet.
Go to Fractal.java, what you need to implement are clearly marked by // TODO in that file. This class is responsible for drawing the fractal shapes onto a Graphics2D object (which could be the screen or could be an image). To see the visual results, open FractalGUI.java in the support folder, and run it. This is the Graphics User Interface (GUI) that shows the fractals and provides basic controls such as changing the fractal type and number of recursions. For this program there are no public tests – the visual results in the FractalGUI window are sufficient for you to check the correctness of your implementation. When you submit your project to gradescope, the autograder will perform image comparisons of your results with reference results, and assign you a grade based on the comparisons.
1: Koch Curve. Let’s start with the drawKochCurve method. Review the lecture slides to make sure you under- stand how the Koch curve is constructed. To begin, you are given two 2D points p1 and p2. If this is the base case (indicated by recursion level 0), you simply draw a line connecting these two points. If this is not the base case, you need to compute the intermediate points p3, p4, p5 and recursively call drawKochCurve on the four subdivided segments (p1-p3, p3-p4, p4-p5, p5-p2). To make sure the recursion makes progress towards the base case, you should pass (level-1) (i.e. decrement the recursion level) to the recursive calls.
Point2D Class. The Fractal program uses Java’s Point2D class, which represents a point (x, y) in 2D. You can check the specification of this class here: https://docs.oracle.com/javase/8/docs/api/java/awt/ geom/Point2D.html You can create a point using Point2D p=new Point2D.Double(x,y); you can change its coordinates using p.setLocation and you can get its coordinates using p.getX and p.getY methods. You can also use it to compute the distance between two points.
Turtle Class. To help you compute the intermediate points on the Koch curve, we have provided you a Turtle
class, inspired by the Turtle graphics that’s well known in a children’s programming language called Logo (https:
//en.wikipedia.org/wiki/Turtle_graphics). Open Turtle.java in the support folder, you will notice that it contains just a few methods. The constructor takes a starting point and a target point. This places the turtle at the starting point, and setting its direction to go towards the target point. The move method moves the turtle for a given distance along its current direction; the getPosition method returns its current position; and the turnLeft, turnRight methods cause the turtle’s direction to change by a given amount of degrees.
With the Turtle class, it’s easy to compute the intermediate points for the Koch curve. Specifically, you first create a new Turtle object with p1 as the starting point and p2 as the target point. You calculate the distance d between the two points. Then you let the turtle move a distance of d/3. Now use the turtle’s getPosition method to obtain its current location, and that’s p3. Next, call turnLeft(60) to let the turtle turn left by 60 degrees, and move(d/3) again to move it to point p4. You can similarly find point p5. See the left picture below for illustration. Once you have
correctly implemented the Koch curve, run FractalGUI to see how it changes as you increase the recursion level (i.e. number of recursions). The pictures on the right above show the first two levels. Again, there is no public test for this program, but from the visual results it should be obvious whether your implementation is correct.
2: Tree. Now implement the fractal tree. Similar to before, you are given two 2D points p1 and p2. If this is the base case (level is 0), you simply draw a line connecting the two points. Otherwise, you need to compute the intermediate points p3, p4, p5, as show in the figure below. As before, d is the distance from p1 to p2; p3 is the point along p1-p2 but d/3 on the way, and this is where the tree starts to branch out. One branch turns 60 degrees to the left, reaching p4, and the distance between p3-p4 is 2 d. The other branch turns 15 degrees to the right, reaching p5, and the distance between p3-p5 is also 2 d. Given these, you can use the Turtle class to help you compute points p3, p4, p5, and then you should 1) draw a line from p1 to p3 (note, this segment is NOT recursion); 2) recursively call drawTree on segments p3-p4 and p3-p5 respectively (with level-1). The pictures on the right below show the
first few levels of the fractal tree. Because the tree subdivides rather slowly, to quickly see interesting details, in the draw() method we have doubled the recursion level for the “tree” case. So in the FractalGUI, each tick of the slider increments the recursion level by two for the fractal tree. If you would rather see the level increments one by one, change max_recursion_level*2 to simply max_recursion_level in the draw() method.
3: Sierpinski Triangle. The Sierpinski Triangle is a 2D fractal shape. To begin, you are given three points p1, p2, p3 that define an equilateral triangle. If this is the base case, you simply draw the triangle (by calling the drawTriangle method already provided to you). Otherwise, you split it into four equal sub-triangles (by finding the midpoints on each side of the triangle); remove the middle sub-triangle (i.e. don’t do recursion on the middle sub-triangle); and then apply recursion on each of the remaining three sub-triangles. The figure below shows the first few levels of the Sierpinski triangle. Hint: to find the midpoint between p1 and p2, you don’t need to use Turtle at all: it’s simple (p1+p2)/2, in otherwords, the x-coordinate of the midpoint is (p1.x+p2.x)/2 and the y-coordinate is (p1.y+p2.y)/2.
4: Sierpinski Carpet. The Sierpinski Carpet is a 2D fractal shape similar to the Triangle. To begin, you are given a square defined by the lower-left corner point p and the side length a. If this is the base case, you simply call drawRectangle method to draw the square. Otherwise, you split it into 9 equal-sized sub-squares, and remove the middle sub-square (so it’s no longer part of the shape); then apply recursion on each of the remaining eight sub-squares.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of