Question 1: Linked Lists Create an IntLinkedList class, much like the one presented in class. It should implement a linked list that will hold values of type int. It should use an IntNode class to implement the nodes in the linked list. The linked list must have the following methods: ? A constructor with no parameters which creates an empty list. ?

void add(int data) adds data to the front of the list. ?

A constructor IntLinkedList(int[ ]) which will create a linked list containing the same values as the int[ ] array, and in the same order. ?

void remove(int index) remove one node from the list, at the specified index, starting at 0. If the index is invalid, remove nothing. ?

String toString() return a String containing the integer values, in the order they appear in the list, with << >> surrounding them, and commas separating them. There should not be a comma after the last integer. (For example, <<12,9,18>> not <<12,9,18,>>.) ?

boolean empty() returns true if the list is empty, and false otherwise. ?

IntLinkedList clone() return a deep copy of the linked list, with a new set of nodes. The data should be in the same order as the data in the original list. For full marks, your code must be efficient, and must not go through the nodes of any list more than once

Question 2: Recursion with Linked Lists

Add the following methods to the linked list class created above. These problems must be solved using recursion where indicated. ? Add an instance method void add(IntNode) which will add an existing node to the front of a linked list. It should not create a new node. This will not be recursive. This method should be used by the split method, below. ?

Define an instance method void split(IntLinkedList odds, IntLinkedList evens) which will remove all of the nodes from a linked list, and add them to two other lists, odds and evens, depending on whether or not the integer values in the nodes are odd or even. The odds and evens lists must already exist. (Methods do not normally modify their parameters, but in this case the method is expected to modify the odds and evens lists.) This method must not create any new nodes. The existing nodes must be used. The integer values do not have to appear in the same order in the new lists. This method must be recursive. For example:

> IntLinkedList test = new IntLinkedList(new int[]{1,4,6,3,5,0,2,3,7,6,3,4,5});

> IntLinkedList a = new IntLinkedList(), b = new IntLinkedList();

> test.split(a,b); > test <<>> > a <<5,3,7,3,5,3,1>> > b <<4,6,2,0,6,4>> ?

Define a method int frequency(int key) which will count and return the number of times that the value key appears in a linked list. This should be a simple non-recursive method containing only a single statement that calls the recursive method below. ?

Define a recursive method static int frequency(IntNode next, int key) which will find and return the number of times that the value key appears in the linked list that begins with the node referred to by next. Note that this is a static method because it uses the parameter next, and must never use top. This method must be recursive. It should process only one node in each recursive call, and must contain no loops.

Question 3: Fractal Tree

Write a program, using recursion, that draws a tree in the StdDraw window, as shown. This tree is a shape called a fractal. Fractals are shapes that have a recursive structure. In this example, every line has two other lines sprouting from it, at two different angles. Then, each of those lines has two smaller lines sprouting from it, and this process continues recursively until you reach the leaves. Download TestQuestion3.java, and StdDraw.java. Define a class A5Q3.java that has one method: public static void drawTree(double startX, double startY, double length, double theta, int depth). drawTree should draw a tree that has depth levels of branches. The main branch should be a line starting at StdDraw coordinate (startX , startY). The line should have the given length and be drawn at an angle given by theta radians. If youve forgotten, that means that the other end of the line will be at StdDraw coordinate (startX+length*Math.sin(theta), startY+length*Math.cos(theta)). The StdDraw command to draw a line from(x1,y1) to (x2,y2) is StdDraw.line(x1,y1,x2,y2). Then there should be two smaller trees, with depth-1 levels, that branch out from the end of this line. One should go a random amount to the left, and one should go a random amount to the right. (In the example above, random amounts from 0 to PI/6 were used. Try different values to see what kinds of trees you get.) The branches should get shorter as you move up the tree. (In the example above, each branch is 10% shorter than the next lower one. Try your own values.) At the end of the smallest lines, at the top of the tree, draw small green circles to represent the leaves, using StdDraw.filledCircle(x,y,radius).To control colours, use StdDraw.setPenColor(Color), where Color is a class defined in java.awt.Color (look up its description online).