Sierpinski's Carpet (left), Sierpinski's Triangle (right)
public static int f(int n) {
if (n < 2) return n;
else if (n % 2 == 0) return f(n-2) + f(n/2);
else return f(n-1) + f(n-2) + f(n-3);
}
public static int mystery(int a, int b) {
if (a < b) {
return 0;
} else {
return 1 + mystery(a - b, b);
}
}
public static double powerA(double x, int n) {
if (n == 1)
return x;
return x * powerA(x, n-1);
}
What is the runtime complexity of powerA using big O notation as a function of n? Explain your answer by showing how 38 is computed with this method.
public static double powerB(double x, int n)
{
if (n == 1)
return x;
else if (n % 2 == 1)
return x * powerB(x, n-1);
else
return powerB(x, n/2) * powerB(x, n/2);
}
What is the runtime complexity of powerB in big O notation as a function of n? Explain your answer by showing how 38 is computed with this method.
public static double powerC(double x, int n) {
if (n == 1)
return x;
else if (n % 2 == 1)
return x * powerC(x, n-1);
else {
double result = powerC(x, n/2);
return result * result;
}
}
What is the runtime complexity of powerC in big O notation as a function of n? Explain your answer by showing how 38 is computed with this method.
For example, if the integer is 15121, then this method should return 10.
0000,0001,0010,0100,0101,1000,1001,1010
For this problem, your method needs to return only the number of such strings, not the strings themselves.
HINT: The number of such strings is the number of strings that start with a 0 plus the number of strings that start with 10.
(Does this method look familiar?)
public class SinglyLinkedList<E extends Comparable<E>>
{
private Node<E> head;
/**
* Removes the first occurrence of the specified element, if the
* element is in the list.
*/
public void remove(E element)
{
// TO BE COMPLETED
}
private static class Node<E>
{
private E data;
private Node<E> next;
private Node(E dataValue)
{
data = dataValue;
next = null;
}
}
}
Use recursion to implement the method remove that
removes the first occurrence of the specified element in this
list.
If the element is not in the list, the list is unchanged.
You should not declare any additional fields, and your solution should
not use loops.
HINT: You will need a helper method here. The helper method will be the method that is recursive. The helper method should have two parameters, a reference to a node in the list where you'll start searching and the element you're looking for. The helper method should return a reference to that same portion of the list that you searched once the element is removed (if found).
A fractal is an image that is self-similar. This means that smaller portions of the image look just like the overall image itself. Fractals can be drawn easily using recursion. The Polish mathematician Sierpinski is famous for describing a number of fractals. Two of these fractals are shown below.
Sierpinski's Carpet (left), Sierpinski's Triangle (right)
In the picture on the left, start with a square region. Divide this region up into 9 smaller equal size squares (think of a tic-tac-toe board) and draw a filled in square in the middle square. Repeat this process on each of the remaining 8 squares recursively.
In the picture on the right, start with a triangular region. Draw an upside-down triangle by connecting the midpoints of the three sides of the triangular region. This creates three new triangular regions not counting the middle upside-down triangle. Repeat this process on the three new triangular regions recursively.
You will complete two Java programs that draw these fractals in Java applets. An applet is simply a Java program that you can embed in a webpage (although you won't do that here).
Download the following project file to get started: Fractals.zip
This project file contains four Java classes:
FractalMaker1.java - a class that creates a Java applet to
display the Sierpinski Carpet to a given order.
FractalPanel1.java - a class that creates a drawing panel
that contains the Sierpinski Carpet, drawn recursively.
FractalMaker2.java - a class that creates a Java applet to
display the Sierpinski Triangle to a given order.
FractalPanel2.java - a class that creates a drawing panel
that contains the Sierpinski Triangle, drawn recursively.
The order of a fractal is the number of repetive layers the fractal has.
The code to create the applet is given for you. You need to complete the drawFractal methods in the FractalPanel1 and FractalPanel2 classes. Your implementation MUST be recursive for full credit.
Basics of DrawingEach fractal panel has a field named page which is a reference to the drawing panel that you can draw on to create your fractal. The panel is 400 pixels X 400 pixels. The origin (0,0) is at the TOP LEFT corner of the drawing panel. The x coordinate increases as you go from left to right. The y coordinate increases as you go from TOP to BOTTOM.
To draw a line, you call the drawLine method as follows:
page.drawLine(x1, y1, x2, y2)In the method call above, x1 and y1 are the x and y coordinates of one end of the line, and x2 and y2 are the x and y coordinates of the other end of the line. These values are all expressed in pixels.
To draw a filled-in rectangle, you call the fillRect method as follows:
page.fillRect(x, y, width, height)In the method call above, x and y are the coordinates of the TOP LEFT corner of the rectangle (in pixels), and width and height give the size of the rectangle in pixels.
In each application, each time the user clicks the Increase or Decrease button, the order of the fractal increases or decreases (as long as it does not go out of range), and the fractal is redrawn. This is performed by the paintComponent method which calls the drawFractal method that you must complete in both examples. Remember that your drawFractal method must be recursive.
Here are examples of the applet output for each fractal for orders 1, 2 and 3. In the pictures below, the black region is the drawing panel (400 X 400) where the origin (0,0) is at the top level of the black box.
Sierpinski Carpets of order 1, 2 and 3 (left to right)
Sierpinski Triangles of order 1, 2 and 3 (left to right)
For the Sierpinski Carpet, the initial call to drawFractal has parameters consisting of the top left coordinates of the initial square at (50,50) and the width and height of the square being 300 pixels each. For the Sierpinski Triangle, the initial call to drawFractal has parameters consisting of the coordinates of the initial triangular area with a top corner at (200, 50), left corner at (50, 350) and right corner at (350, 350).
The fractal makers both specify extends JApplet and implements ActionListener. In a plain ASCII text file, explain what each of these code phrases mean specifically in the context of this application. If the class extends JApplet, what does this allow the programmer to do? Give an example in the code where this is illustrated. If the class implements ActionListener, what must the programmer do? Give an example in the code where this is illustrated.
Be sure to document all of the code that you write to explain what you are doing. Use appropriate Java style (indentation, variable names, etc.) to make your code as readable as possible.
Your submitted zip file should include the complete Java program and your text file with the explanation of extends JApplet and implements ActionListener as used in this application.
See the course website for instructions on how to hand in your program and the policy for late submissions.