TASK 'CHALLENGE' RATING (offered to assist you with project management strategies)
	Routine	Typically some deep thinking required, but not necessarily a lot of coding.
	Hard	Likely involves either a multiplicity of (possibly new) concepts or algorithms. Allow time.
	Buckle Up	Start immediately, think deeply, employ a stepwise refinement strategy and post concerns as required.

Jumble. I've often wondered, "What word in the English language has the most permutations that are also words?". You are asked to develop code to inform you and I, both. You'll make maximum use of the data structures and algorithms we've examined this year. To keep things reasonable, you'll restrict yourself to four-letter words.

Task.

1. Create a Java project entitled Jumble.
2. JH has found the text file Words.txt consisting of over 230K English words with no restriction on length, arranged alphabetically. Write code to filter out the four-letter words into a file entitled FourLetterWords.txt. You do not need to submit this code.
3. A dictionary of these words needs to be loaded into a data structure that will enable fast searching.
4. For each word in the dictionary, all permutations of the word need to be generated and searched for their existence in the dictionary. Feel free to adapt the recursive Permutations code you developed last October.
5. The output of the project will be the word/words that has/have the most permutations that are also words, together with the sorted list of these permutations (no repeats).

You are free to design and implement the project as you see fit, as long as you use a java.util.TreeSet<E> for one aspect. Your documentation will include clear and full justifications for the structures and code decisions you made.

Finally, you may or may not need this but I found myself thinking about how to construct a balanced Binary Search Tree from an ordered list. A balanced tree optimizes the search time. I googled it and found some interesting suggestions here:

Create a Balanced Binary Tree from a Sorted Linked List

Manual Creation and Traversal. In this first assignment, you are to incorporate TreeNode.java, exactly as it appears on page 583 (get student files from Skylight), into the development of a BST class whose source code prototype appears below. The BST constructor will use one statement to construct a tree with four nodes. Complete the body of the traverse(TreeNode node) method and use the driver file, BSTTest.java to test that the characters appear on the console in alphabetic order.

public class BST {
  
  private TreeNode root;
  
  /**
   * Constructs a BST object encapsulating a binary search tree 
   * into 'root'. Hard codes the Character data: 'J', 'A', 'V', 'A'
   * as the node values in one statement (manually).
   */
  public BST() {
  }
  
  public void traverse() {
    traverse(root);
  }
  
  private void traverse(TreeNode node) {
	  // add recursive code here so that all names are displayed to the console

  }
}

AP Exam Prep. This year's AP Computer Science Exam will be written in the morning of Tuesday May 6th. This gives us 3 weeks of preparation.

1. Install the GridWorld Case Study.
   1. Unzip the GridWorldCode.zip file to a convenient folder (your Desktop, for example)
   2. Open your Eclipse Workspace and create a Project entitled GridWorld
   3. With the GridWorld project selected, go to the Build Path option and add an External Jar reference to gridworld.jar. Before closing the dialog, update the javadoc location for the jar, pointing it to the javadoc folder.
   4. With the GridWorld project still selected, import the framework folder.
   5. Select the src folder. Launch the Import feature and acquire the contents of each of the each project folders: firstProject, boxbug and critters.
2. CodeBug. April 25. In this project you are asked to develop and manipulate an instance of the CodeBug class, defined as,

   

   The CodeBug constructor will receive a String-encoded path it is expected to follow encoded as a String. For example, the CodeBug in the image to the right is just about to complete a figure 8 as a result of this instance's constructor receiving the String: 0123432107654567, where 0 means NORTH, 1 means NORTHEAST, 2 means EAST and so on. Each digit is to interpreted as a direction to face, followed by a move. Digits in the String can be repeated for extended moves in the same direction. You can assume that there is only one CodeBug is the world and it is conveniently positioned in the ActorWorld so it won't hit a boundary in completing its pattern.

   Develop documented implementations of the CodeBug class and a driver class CodeBugRunner. Your driver should include a couple of original patterns, with all but one commented out. The patterns should provide a closed loop meaning your CodeBug will return to it's starting point before repeating the pattern indefinitely. Submit the source code for the classes to handin before the start of Wednesday's class and we'll sample a few.

3. Gridworld UML: Not assigned. While consulting the Gridworld Javadoc, use the UML Drawing Applet to construct a FULL UML diagram for the Gridworld Case Study that includes all classes and interfaces. Colour the background of all classes and interfaces that are tested on the A exam in orange; those that are not tested in blue. You do not need to include the constructors and methods, this is simply an important exercise to gain an understanding of the organization of the classes and interfaces. Have your .uxf file with you at the start of our Friday class.
4. Sample Exam: April 19. With pencil and paper only, grab the kitchen timer and allow 75 minutes to answer the 40 Multiple Choice questions from Sample Test 1. Take a 15 minute break and then allow yourself 50 minutes to answer the first two Free Repsonse questions from Sample Test 1.
5. Sample Exam: April 26. AP A-1, handed out in class. Bring your results to class on April 29.
6. May 3. 2010 Free-Response Questions. Bring your responses to class on Monday May 5 for discussion and scoring details
7. May 5. 22 FC Questions on page 17. Confirm answers yourself.

Deterministic IFS: Iterated Function Systems. Each iteration of the Random IFS algorithm requires the selection and application of only one affine transformation within the code, based on an array of probabilities.

If each iteration of the IFS algorithm requires the application of ALL of affine transformation within the code, randomness is set aside and the outcome is predetermined. For this reason, this strategy is referred to as the Deterministic IFS algorithm.

At each stage of the animation to the right, the entire panel is subjected to three affine transformations resulting in contraction mappings that yield the familiar Sierpinski gasket. What becomes clear is that regardless of the initial image, the final image (the attractor) remains predetermined. View the 2014 ACES IFSDeterministic Gallery below to verify this property.

Task.

1. Revisit your favourite Random IFS image created last week (Tree? Fern? Spiral?). Add the method,
   

   	public BufferedImage getIFSImage()
   

   to your IFSRandom class that will render an image to an off-screen BufferedImage object and return it. You'll use this image as the starting point for each of your preferred Deterministic IFS renderings.
2. Revisit Yale's Deterministic IFS Applet and identify three you like.
3. If necessary, add any new IFS definitions to your library, filling in any values you want for your (cumulative) probability array since you won't be needing it!
4. Extend your IFS class in creating IFSDeterministic.
5. Implement the IFSDeterministic constructor to include the creation of the following structures as discussed in class,
   

   	AffineTransform[] transforms;
   	AffineTransformOp[] ops;
   

6. The draw method of your IFSDeterministic will exploit the AffineTransformOp object to produce the expected rendering. Specifically, you'll make use of AffineTransformOp's filter method.
7. 2014 ACES IFSDeterministic Gallery...

CA	PH	WK	RM	ZR	SR	CS
	Coming Soon

Random IFS: Iterated Function Systems. With the conceptual and mathematical foundations laid, you can now undertake the final phase of this year's Fractal Framework application to render (somewhat realistic) natural forms.

Task.

1. Add a second-to-last column to your Fractal Framework applet entitled, Barnsley
2. Review the IFS gallery of offered through Yale's Random IFS Applet and Paul Bourke's site.
3. Under the Barnsley menu, add menu items that will initiate your implementation of at least 8 images that inspire you from either of the two sites (or others you may find online).
4. Add an IFS class that implements the Drawable interface. One design suggestion would be to create a Code class to encapsulate the various affine transformations, their probabilities and the colour palette. Here's a sample,

         	public class IFS extends Plane2D implements Drawable {
         

   with a constructor possibly of the form,

 	public IFS(String n, Code code, int iterations, double distance,
        		double xOffset, double yOffset)
      

5. Create a class IFSRandom that extends IFS that will implement The Random IFS Algorithm, along the lines of,

      	public IFSRandom(String n, Code code, int iterations, double distance,
           		double xOffset, double yOffset)
        

6. All IFS images could be stored in a TreeMap<String,Code> where String is the name of the IFS, thereby making retrieval relatively efficient. This transforms/probabilty data could be encoded within the constructor of the Content class. Here's a sample,

      	library.put("SierpinskiIFS", new Code(new double[][] {
   			// r,
   			{ 0.5, 0.0, 0.0, 0.5, 0.0, 0.0 },
   			{ 0.5, 0.0, 0.0, 0.5, 0.5, 0.0 },
   			{ 0.5, 0.0, 0.0, 0.5, 0.0, 0.5 } }, new double[] { 0.3333,
   			0.3333, 0.3334 }));
      

7. Adapt a colour palette to the rendering of your images and make optimum use of the panel through the distance and offset parameters. The (impressive) results are in...

CA	PH	WK	RM	ZR	SR	CS

LINDENMAYER SYSTEMS. With Koch Constructions and the concept of fractal dimension as a foundation, we can now take one step closer to our goal of rendering of natural forms. Not surprisingly, credit for this stage goes to a Hungarian biologist/botanist, Aristid Lindenmayer, who, in 1968, introduced a formalism associated with the expression of plant structures, known today as L-Systems. The grammar embodied within L-Systems lends itself readily to computer graphic rendering.

An electronic copy of a wonderful text on the subject of Lindenmayer Systems, entitled The Algorithmic Beauty of Plants (ABOP) is available for download by following the link to the left. The related Algorithmic Botany website offers additional inspiration.

The algorithm for generating these images is defined by an initiator (axiom) and one or more generators (productions) used to propagate the shape over successive generations. In this assignment, we'll use a string for the axiom and a set of production mappings to define the image. A recursive generation algorithm coupled with a character replacement strategy of your choice (see String methods) by their production mappings grows the image. Finally each generation is drawn with a virtual pen (similar to a plotting device) on a JPanel in response to characters in the encoded String. Here is a table containing some of the images you'll be rendering, together with some original curves developed by former ACES. See Framework.html to view the animated renderings.

Figure 1.9 a)	Figure 1.9 b)	Figure 1.9 c)	Figure 1.9 d)
Gettings Original	Tsuji Original	Black Original	Weldon Original
Ng Original	Anderson Original	Houlding Original	W. Knowles Original
Mahjour Original	Ringwood Original	Ruscica Original	Sansom Original

Task.

1. Add a new menu to the immediate right of Koch, entitled Lindenmayer.
2. Under the Lindenmayer menu, add the same menu items that appear in Framework.html. Consult pages 8-10 of the ABOP handout for details of the Koch Snowflake, the Koch Island and Figures 1.7, 1.8, and 1.9 onward.
3. Create a new Drawable class with the name of LSystem (LSystem documentation). The animation strategy will be to render the image as a plotting device would, one segment at a time.
4. Create a Turtle class that encapsulates the properties of the drawing pen manipulated by LSystem's draw() method (Turtle documentation).
5. (Optional) Feel free to incude an L-System of your own design/creation or even one you've googled. Alternatively, how about an origami version?
6. Submit your updated Framework source code to handin and have your web page updated by the deadline.

KOCH CONSTRUCTIONS: Triadic Koch Snowflake and Quadratic Koch Island. With a preliminary understanding of the Cantor Set we are ready to undertake a related set of fascinating structures attributed to Helmut Koch that continued to challenge the conventional notion of dimension well into the 20th Century. Whereas Cantor simply removed the middle third of a line segment, Koch proposed that it be replaced by two segments of equal length.

Cantor	Koch

The bridge from Cantor to Koch can be inferred from the graphic below left, that also highlights the recursive application of each strategy. Koch went further. Using each of the three sides of an equilateral triangle (initiator) and recursively applied his replacement strategy (generator) to produce the perimeter of his classic Koch Snowflake (below right).

Cantor → Koch	Koch Snowflake

Now it gets really interesting. Koch's replacement proposal opened the door to a variety of generators, one of which led to the Quadratic Koch Island depicted below.

Island Initiator and Generator	Quadratic Koch Island

The iconic Triadic Koch Snowflake and Quadratic Koch Island belong to the set of plane-filling curves or PFCs. The realization of this assignment will result in a third menu in your Fractal Framework devoted to a class of PFCs that we'll refer to as Koch Constructions (there's not enough time in this course to investigate 3D space-filling curves (SFCs) but I'd welcome an email from you someday linking me to your future explorations). Rather than simply considerthe perimeter, our first investigation of the Snowflake and Island images will focus on the full area of the structures as depicted below.

Triadic Koch Snowflake	Quadratic Koch Island

Task.

1. As a starting point for this project, consider Exercise P13.15 from last year's text book. Create a project called Koch and drop in the classes, Koch.java, KochComponent.java and KochLine.java. Execute the project and digest the author's design.
2. Create a new Drawable class by the name of TriadicKoch that encapsulates an ArrayList<Sprite> of size equal to the maximum depth of generation.
3. A call to Sprite's createData() method (or some similar call) can create an equilateral triangle as a generation 0 starting point. Subsequently it can be rotated and scaled into position through appropriate Matrix2D transformation calls.
4. Using an algorithm similar to Horstmann's Koch example above, employ recursive generation strategy to propagate a sequence of Sprite objects representing the outline of successive generations the the Koch Snowflake.
5. Koch's draw(BufferedImage img) method can create and fill a Polygon from the respective Sprite data.
6. Repeat the 4 steps above for the class QuadraticKoch.
7. (Optional) Design your own generator, implement it, name it, and add it to your menu.

CANTOR SETS (Part 3 of 3): Triadic and Quadric Cantor Strategies. Look at the gif animations below. Execute Framework.jar to see them live. Your previous experience with the Linear Cantor Set would suggest that a recursive removal algorithm could be undertaken to generate these 2D Cantor Sets as well. Although we don't have the time to pursue an investigation of the 3D Cantor Set this year, it may be something you may wish to investigate in the future.

Triadic Cantor (depth=7)	Quadric Cantor (depth=6)

Task.

1. Under the Cantor Sets menu, and another item entitled, Triadic.
2. Implement a new Drawable class entitled TriadicCantor. Its constructor should receive Framework's appDimen object so it knows the dimensions of the BufferedImage it will be drawing to. It will also receive the maximum depth of removal. The animated gif to the right presents a depth of 7. Your constructor should generate a entire collection of subsets to be 'removed' prior to finishing. In this way the draw() method will simply access the require number of levels on each call.
3. Modify Content's current object to point to an instance of the TriadicCantor. This will make it appear when the applet launches.
4. Repeat Steps 2 and 3 by implementing the class QuadricCantor.
5. A premium will be reserved for code that is efficient, clear and well documented. One of the ways this can be accomplished is to make maximum use of the Polygon class and any of the JCF data structures we've studied.
6. The original triangle has an area. With each recursive stage, area is removed. Two interesting questions to ask yourself then is, "How much area remains at each stage of the deconstruction?", and "Eventually, is all the area removed or is there a limit?". After a few weeks of Calculus you'll be able to formulate a mathematical answer to these questions. Let me know when you get there and we'll discuss it.

CANTOR TERNARY SET (Part 2 of 3): Implementation

1. Rename the previous Gaskets menu to Pascal.
2. Add a new menu to the immediate right of Pascal, entitled Cantor.
3. Implement a new Drawable class entitled LinearCantor. Its constructor should receive Framework's appDimen object so it knows the dimensions of the BufferedImage it will be drawing to. It will also receive the maximum depth, d, of removal. The animated gif to the right presents a depth of 5.
4. Since the total number of segments can be determined beforehand from the depth, the constructor can instantiate an array of precise size to house all the segments. The array will be populated before the constructor ends through a call to the (forward) recursive method propagate(Point2D segment, int d) where segment is the original length and d is 1 (just as we have a number of times before, the array's data will be used to support an animation by your draw method).
5. Display the Set to depth of at least 5 generations.
6. A premium will be reserved for code that is efficient, clear, and well documented.

Feel free to execute this version of Framework.jar to see the results for this and the future Cantor fractals.

1. You are asked to research the Cantor Set using as many references as you require to explain the propagation process in your own words and identify one or more of its remarkable properties.
2. The table below presets a quantitative analysis of the stages of the Cantor propagation. Based on your research be able to explain the table to the class when asked.
3. State the Fractal (Hausdorff) dimension of the Cantor Set accompanied by an explanation.

   

4. The original line segment has a length. With each recursive stage, length is removed. The interesting question to ask yourself then is, "Eventually, is all the length removed?"

Big Box Simulation 1: Queue<Customer>

A checkout line is a FIFO structure, we'll model with a Queue <Customer> object. For the sake of this first version of our BBS we'll assume that only one checkout station is available.

In this project, you are to run a one-day simulation of the checkout station, monitoring and reporting the station's activities, and summarizing the results at the end of the day. Here's the output from a sample run.

Task. From the data given to you, customers (instances of the Customer class) arrive in random intervals of 1 to 4 minutes. Also, each customer is serviced in random integer intervals of 1 to 4 minutes. Obviously, the rates need to be balanced for the line length to remain manageable. If the average arrival time is larger than the average service rate, the queue will simply continue to grow. Even with balanced rates, randomness can still cause long lines.

Run a simulation for a 12-hour day (720 minutes). Here's a rough guideline for each minute of the day:

• If the next customer arrives,
• Say so
• Add a new customer to the queue (with a customer number, his/her arrival time, and a randomly assigned service completion time)
• Schedule the arrival time for the next customer
• If the service is completed for the current customer (at the front of the queue),
• Say so
• Assign the finish time (optional)
• Remove (deque) the customer from the queue
• Adjust cumulative statistics

Maintain the necessary data so that at the end of the simulation, the program summarizes results for the following:

• Number of customers successfully served
• The customer number that experienced the maximum wait time and report this value.
• The average wait in line for served customers.
• The number of customers serviced after closing time.
• The maximum number of customers in the queue at any time.

Final Recommendations,

• Don't concern yourself with publishing the statistics until the servicing of customers has been completed.
• When the store closes, there may be customers in the queue.
• Tip: You may want to develop your logic over a shorter day, then expand it to a full day (720+ minutes) when you're satisfied
• You will be asked to adjust some of the parameters later, so design accordingly.

Using the driver Simulation.java develop and submit the BigBox.java and Customer.java class files that will yield output similar to the above.

The Josephus Game A bidirectional Ring structure would be a useful container for many applications. One such classic application is the so-called Josephus Flavius Game. A reasonable introduction to the context can be found at Cut The Knot.

Although our review of the Java Collections Framework in the previous chapter revealed the absence of a such a class, it's not hard to imagine how one could be constructed.

There is no such set of structures known as the JavaScript Collection Framework that I know of but, if there was, and it contained a Ring structure, it might look the one I demonstrate here.

Task.

1. Create a project called JosephusGame and add this driver.
2. Add the text files 20names.txt to the project.
3. Implement the Josephus class as specified by this UML diagram that maintains a LinkedList<E> that emulates the behaviour of a Ring (circular list).
4. The output of the project yields the order of the names eliminated.

Combination Lock. Since Java's LinkedList<E> class maintains this data structure as a doubly-linked list, users can traverse it forward and backward with the help of a ListIterator<E> object. Create the project LockTest and a driver that manipulates the class, Lock, defined by the UML specification below. You will need to complete the conditions in each of the while statements in the driver for the project to work correctly.

With a correct implementation of the Lock class initialized with the combination, 21-32-34, your driver will generate the following output,

Gaskets: The Chaos Game. Familiarize yourself with this recreational version of the Chaos Game.

Tasks.

1. Familiarize yourself with MouseDemo.jar and its source code. The UML above gives you some idea of the enhancements for this mouse accommodation.
2. Add a new JMenuItem within the Gaskets menu (after Pascal's Carpet) entitled The Chaos Game
3. Design and implement the Drawable class, ChaosGame, that, after three mouse clicks from the user, will display 100,000 points according to the conditions of the Chaos Game.
4. For added interest, map a colour (red, green, blue) to each point when rendering.
5. Remount your Framework applet.
6. Submit your source code to handin by the deadline under the Subject Line: The Chaos Game.

Gaskets: Pascal's Carpet. More secrets remain embedded within Pascal's Triangle. Look at the Triangle again, focussing on groups of adjacent even numbers. The resulting image should be surprisingly familiar.

Task.

1. Under the Gaskets menu, add another item entitled Pascal's Carpet.
2. Add the Drawable class entitled PascalsCarpet whose draw() method plots a pixel for only the odd terms. Since you are plotting only pixels you can generate as many rows of Pascal's Triangle as the height of your applet. Be careful to maintain no worse than an O(n²) algorithm.
3. Your triangle should fill the entire panel as an equilateral triangle as you did in your Pascal's Numbers segment.
4. Update your home page.
5. Submit your source code to handin by the deadline under the Subject: Pascal's Carpet.

Gaskets: Pascal's Numbers. You explored Pascal's Triangle earlier in the course so it won't be too difficult to adapt its generation again as a basis for exploring the first of a number of new Fractal algorithms over the next few months.

Task.

1. Add a new menu to your Framework applet entitled, Gaskets. The first entry under this menu is the item, Pascal's Numbers. See UML above.
2. Complete the body of PascalsNumbers' draw() method to display the required number of rows onto its img object.
3. Generate the values using the most efficient Big-O strategy you can implement.
4. Configure the font, the line spacing, and the number of rows to fill the available space.
5. The elements of the Triangle are toappear centered horizontally as the example to the right demonstrates. Use the FontMetrics class to assist you with this. Here's an online example.
6. Submit your source code to handin and update your home page.

Matrix2D Enhancements

1. (DAY 1) The Determinant of a Matrix.
   1. Remember the crossing pattern in the Shoelace Formula for determining the area of a polygon?
   2. Another crossing pattern enables the determinaton of the Cross Product of a two vectors. (F = qv × B)
   3. Finally, here's the crossing pattern associated with the evaluation of the determinant of a 3 × 3 matrix.
   4. Unfortunately, this pattern is not scalable and this is the wrong way to find the determinant of a 4 × 4 matrix.
   5. A recursive technique attributed to Laplace (you'll hear much more about his contribution to mathematics next year) is the preferred method for us,

       

   6. Implement the above definition through the method public double getDeterminant() to be added to your Matrix2D class. Generalize your design so that the determinant of a square matrix of any dimension could be found using the supporting methods highlighted in red in the Explorer view below ( coFactor, determinant, and minor). Add statements at the end of your Matrix2DTest driver to confirm your results. Here's a worked example to assist with your development. 2012-2013: Add the driver DeterminantTest.java to your Animation2D project to yield results similar to this. This will require you implement the DAY 1 methods below.

   

2. To make things clearer, I've colour-coded an Explorer view of the methods that need to be implemented at each stage of the project.
   
3. (DAY 2) Cramer's Rule.
   1. One method for solving a relatively simple system of n equations with as many unknowns acknowledges Gabriel Cramer (1704-1752) for a computationally-friendly algorithm. Here's a description,
      1. Consider a system represented in the matrix form, Ax=b, where A is the n × n coefficient matrix, x is the variable column vector with n elements and b is the right-side column vector with n elements.
      2. Let A_c be the matrix obtained by replacing column c with b.
      3. Let the determinant of A be represented as D.
      4. Let the determinant of A_c be represented as D_c
      5. Cramer's Rule defines the solution to the system as,

         

         
         where D ≠ 0.
   2. Add the method public double [] cramersRule( double [] b ) to your Matrix2D class that returns the solution x to the system Ax=b , where A is this Matrix2D object. You are to make maximum use of existing Matrix2D resources and keep the rest of your code as tight and efficient as possible. Add a call to Matrix2D's solveSytem method (it will simply call cramersRule for now) statements at the end of your Matrix2DTest driver to solve and display the solution to the system in i. above.

4. (DAY 3) The Inverse of a Matrix. Just as a (multiplicative) inverse exists for all real numbers, x, (except 0), so, too, does the inverse of a square matrix A (det A≠0). The inverse of A can be defined as,
   

   

   where adj A is the adjoint of A. The adjoint of A is the matrix obtained by transposing the matrix of cofactors of A. Implement the blue DAY 3 methods above, as follows,
   1. the transpose() method reflects the element in the main diagonal. That is, the element at row r, column c is exchanged with the element at row c, column r. NOTE. This would be a perfect opportunity to practice the technique of swapping elements without the use of a third variable.
   2. the scalarMultiple(double k) method simply multiplys each element of the matrix by the scalar parameter.
   3. the adjoint() method simply returns a new Matrix2D object populated with the coFactors of A that have been transposed.
   4. if the previous 3 methods are implemented as recommended, the inverse() method can return its result in a single expression as follows,

   

   Add statements to your Matrix2DTest driver to test your inverse() method (make sure to check that the determinant is not 0 beforehand!)

MODELING IN R²: PART 3. Animation2D. In this final instalment, we integrate the foundation classes you have developed over the previous two projects to demonstrate the applicability of matrix-defined transformations to simple, but compelling, two-dimensional animations.

Task. Add this driver to your Animation2D Project. Review the driver code. The general idea is to transform one or more Sprite objects to the coordinates for the next frame within the updateScene() method. The loop in the run() method will then call the paintPanel() method in which you can retrieve your Sprite's updated coordinates to populate a Polygon object. This polygon object can be added to the scene through a call to Graphic2D's draw() method.

Here's the full Javadoc. I've created a very elementary example to the right. Considering your vast exposure to gaming animation, I know you'll take your effort to a whole new level.

Note. The classes in this project reflect a strong hierarchical design. I would expect your code to capitalize on the strength of this design; writing clean, tight, efficient carefully-crafted statements that fully exploit the cascading nature of the respective class methods.

Submission. Attach your Animation2D and Sprite classes (and any other previous classes that have been enhanced) to an email to handin with the Subject: Animation2D by the deadline.

MODELING IN R²: PART 2. Transform2D

Task.

1. Add the driver, Transform2DTest.java. to your Animation2D project and review the code.
2. Also add the class file Point2DList.java and review this code.
3. Write the two class files, Transform2D.java and Point2D.java, that will work seamlessly with the other existing classes to produce this output. I have prepared the documentation that will guide your effort.

Please attach the separate class files: Transform2D and Point2D, to an email to handin with the Subject: Transform2D by the deadline.

MODELING IN R²: PART 1. Matrix2D. In this 3-part project you are introduced to the matrix algebra of transformational geometry leading to a creative graphic animation. Below are the submissions of last years' ACES. Check out more samples from ACES of previous years: Select a year... 2012-2013 2011-2012 2010-2011 2009-2010 2008-2009 2007-2008 2006-2007

C. Anderson	P. Houlding	W. Knowles
R. Mahjour	Z. Ringwood	S. Ruscica
	C. Sansom

Task.

1. Create an Eclipse project entitled Animation2D and drop in the driver Matrix2DTest.java.
2. Develop a set of cascading set of constructors and required methods for the class, Matrix2D that can be used with the driver Matrix2DTest.java to produce this output.
3. Develop a UML class diagram for the Matrix2D class, save it as a .gif to the image folder of your FC Web Publishing area, and reference it in the class javadoc. Make every attempt to maximize the use of a minimal set of methods. Minimize the dependency of your code on direct references to the only instance field, matrix.

Maze Generation and Traversal. We're going to devote the next few classes to a group investigation of mazes: their generation algorithm and solution. This is another classic example of depth-first searching, similar to the recursive flood(x,y) method of last week's PaintBucket activity. In addition to exploring this algorithm, I want to draw your attention to the Processing language. This relatively new Java/C hybrid offers some amazing opportunities and, given your skills, you'll catch on very quickly. The Arduino and Processing languages share the same pedigree, that of the Wiring language.

Day 1 (Orientation with Interaction)

1. Visit the Processing site and explore a few examples from the Play with Examples link.
2. Install the Processing language on your laptop.
3. From the File>Examples menu, explore a few more examples.
4. Create the Eclipse Project, Sketch, and add the source code for the four Sketch classes: Cell.java, Maze.java, Rand.java and the driver, Sketch.java.
5. Read how to make Eclipse Processing-Aware and made the modifications to the Build Path of your Sketch project. Execute the Sketch project.

Day 2 (Porting Processing code into your Recursive Framework for maze generation)

6. Execute the DFS:Generate activity in Recursion.jar to see what we're going after today.
7. Maze Generation Tutorial
8. Review the source code for the four classes that make up the Sketch Project. Get to the point where you understand most of it. Do your best to identify the calls to methods that appear to be inherited from Processing's PApplet class hierarchy.
9. With MINOR modifications, the Cell, Rand, and Maze classes can be inserted into your Framework project.
10. Insert the Sketch class into Framework, renaming the former to MazeWorks.
11. Establish menu items that correspond with the Maze menu in Recursion.jar, placing a call to
    MazeWorks(height, width, which) on a Thread.

Day 3 (Developing recursive traversal code for your maze)

12. Spend some time with the Generation and Traversal activity presented here. You may wish to deselect the Show Gen option to focus on the solution rather than the generation.
13. This author provides a very good explanation of the thinking behind recursive strategy to solve the maze (and so many similar problems).
14. Add the recursive method private boolean traverseMaze(Cell cell) to your MazeWorks class that will record the path taken from the start to the end. The order the cells are visited (set to yellow) and backtracked (set to gray) can be logged in a class variable of the type: ArrayList<Cell>. Since maze generation and maze traversal are similar, but not identical, activities feel free to new add instance fields to your Cell and MazeWorks classes as well as accessor and modifier methods to accommodate traversal. Here's what your aiming for: Recursion.jar
15. If you're still unsure and you want to look at the structure of the code for a solution look here.
16. Develop and mount your solution.

To assist with the evaluation, you will maintain a Stack<Double> to track your progress. The end result of the project will be to animate the collection of intermediate Stack<Double> objects to offer the viewer a play-by-play version of the complete evaluation.

Task.

1. Test drive the project here. Test a variety of postfix expressions. I maintained a collection of Stack<Integer> so the answers might not be accurate. Yours will maintain a Stack<Double>.
2. Examine the samples below. These are offered only for your understanding. You are not required to produce console output.
3. Add a Drawable class to your Framework project by the name of RPNEvaluator and add appropriate menu strategy.
4. The evaluation of the postfix expression will be carried out within RPNEvaluator's recursive private void evaluate(int c) method that uses the explicit parameter c as a cursor it advances through the expression. As it processes the expression, it manipulates a Stack<Double> object, pushing and popping Double objects as required. All changes to this Stack<Double> are to be recorded in the larger collection for final playback.
5. For simplicity, assume each operand is a single-digit integer.
6. Develop, document, and deploy your Framework applet by the deadline.

Bracket Matching. The example method on page 480 offers an iterative solution to confirm whether a String consists of correctly matched parentheses. It would be more impressive if it were recursive.

Task.

1. Create a project called BracketTest and drop in this driver.
2. The class contains an instance field of type, Stack<Character> that can be exploited from within the recursive matchParens(Strin expr, int i) method.
3. The predicate methods, isOpenBracket(char ch) and isCloseBracket(char ch) can be used to write cleaner, more readable code within your matchParens method.
4. Output should appear as follows,

Paint Bucket.

In this assignment you are to flood a region by implementing a depth-first recursive search for a border colour, painting pixels as you go. This is not how it's done in general but, for small areas, it serves as a useful introduction to depth-first recursive searching. For your regions, you can use one of the standard Graphics2D Shape classes ( ie, Rectangle2D, Ellipse2D, Arc2D, etc.) to create an interesting outline of your own design using piecewise Shape objects. Keep your outline small since the system stack has to store many return addresses to manage the depth of recursion.

Task.

1. Under the Studies menu, after the Permutations menu item, add Paint Bucket.
2. Implement the Drawable class, PaintBucket.
3. After rendering your hollow design, PaintBucket's draw(BufferedImage img) method assigns img to a class BufferedImage variable prior to calling its recursive flood(x,y) method to fill the interior of the shape. The initial x and y values are the pixel coordinates of any point known to be in the interior of the region.

Finally, don't forget to update your home page prior to submitting your source code.

Directory Listing. Nested or 'hierarchical' structures are all around us. Also referred to as tree structures, these organizational arrangements are inherently recursive. Three examples appear below. In each of these, the level of indentation reflects the parent-child relationship.

Eclipse: Package Explorer	Becker: RobotSE	XML Catalog

Task.

1. Create a standalone application entitled, Finder.
2. With the familiarity gained from our review of Java's System and File classes, demonstrate a depth-first recursive traversal of a folder (selected by the user) on your laptop that results in the display of the files in that folder to the Console. Your display should indent 2 spaces for each sub-level.
3. Once completed, adapt the Finder class to fit within your Framework application/applet, adding a new menu item under Permutations as a launch point.
4. Remount your applet.
5. Finally, recursion is about seeing the world in patterns and harnessing its power. If you get a chance, watch the HBO video entitled Temple Grandin. The movie profiles an autistic woman whose ability to think in patterns and images results in improvements in the treatment of livestock of all things.

Permutations. A binary decision tree designed to order three unique elements yields 3! or 6 leaves. The leaves can be interpreted as all possible permutations of the original elements and can easily be extended to n unique elements. In this exercise you will display all permutations of the characters of a given input string.

Task. As the first entry into your Framework project, display all permutations of a string submitted by a user. For the string "ABC" the output should read,

BCA
CBA
CAB
ACB
BAC
ABC

Framework.

Tasks.

1. Review the UML diagram above for the Framework code.
2. Generate the javadoc and review the pages.
3. Run the code as an application, selecting the only menu item available, and then close the window.
4. Repeat the execution, this time launching it as an applet (make sure to set the width and height to 600 in the Parameters Tab of the Run Configuration dialog.
5. Finally, review the code, familiarizing yourself with all aspects.

Towers of Hanoi. Legend has it that a Brahman monk was charged with the task of moving 64 golden disks (of increasing diameter from top to bottom) from one post to another post. The two stipulations placed on the task were that only one disk could be moved at a time, and no disk of greater diameter could rest on top of one with of lesser diameter. A third post is always available for temporary placement. Task. You are display the moves necessary to complete the task. Code the recursive method below into your NumericalMethods class,

/*********************************************************************
 * This method displays the specific moves necessary to move n rings *
 * from the source post to the destination post using a temporary    *
 * post. The big-O of this task is O(?)                              *
 * @param n the number of disks                                      *
 * @param src the name of the source post                            *
 * @param dst the name of the destination post                       *
 * @param tmp the name of the temporary post                         *
 *********************************************************************/
 public static void showMoves(int n, char src, char dst, char tmp)

Add statements to your RecursiveClassics driver that will solicit the number of disks to be moved and a subsequent call the showMoves method as follows,

showMoves(n,'A','B','C');

For n=3, your output should read,

  Move A to B
  Move A to C
  Move B to C
  Move A to B
  Move C to A
  Move C to B
  Move A to B

Binomial Theorem. A deep understanding of the Binomial Theorem will prove useful to you in the months and years ahead. You'll undertake a computational investigation of the Binomial Theorem in this two-part project. Note: For our purposes, we'll favour recursive strategies over iterative implementations strictly for the experience. Here's a reasonably compact definition of the Binomial Theorem,

(BT-1)

Application of (1) yields familiar binomial expansions,

(BT-2)

Part 1. Combinatorics. Consider the following definition from the field of Combinatorics,

(BT-3)

The left side of (3) is read as n choose r and represents the number of combinations of n one can make, choosing r items at a time (the last two expressions are different ways of expressing the same concept). As can be seen, the determination of this integer result relies on factorials. For example, assuming 5 students show up for class and I need to choose 2 students to go down to Bloor and pickup the sushi order I placed for lunch. How many ways can the pair of students be chosen? There are 10 such combinations as can be seen below.

(BT-4)

1. Create a project called, BinomialTheorem that exercises the methods in your static NumericalMethods class below. Create a static NumericalMethods class and add the following methods,

/***************************************************************************
* This method determines the value of n!, recursively                      *
* Precondition: n>=0                                                       *
* Postcondition: the method returns the value of n!                        *
* @param n the whole number for which the factorial is to be determined    *
****************************************************************************
public static int factorial(int n)

/****************************************************************************
* This method returns the number of combinations that can be expected given *
* n items, taken r at a time. This does not need to be recursive.           *
* Precondition: n>=0, 0<=r<=n                                               *
* Postcondition: the method returns the value of nCr                        *
* @param n the number of items from which combinations are taken, n>=0      *
* @param r the number of items taken, 0<=r<=n                               *
*****************************************************************************
public static int choose(int n, int r)

2. Now you will display Pascal's Triangle. Add the non-recursive method below to your BinomialTheorem driver,
   

   /**********************************************************************
   * This  method displays a number of rows of Pascal's Triangle         *
   * Precondition: rows>0                                                *
   * Postcondition: the method displays the requested number of rows of  *
   *                Pascal's Triangle. It relies on the choose method    *
   * @param rows the number of rows to be displayed                      *
   ***********************************************************************
   public static void pascalsTriangle(int rows)
   

Finally, indicate the Big-O of each of the three methods above in their respective javadoc comment.

Part 2. Probabilities. In Part 1, each element in Pascal's Triangle was determined through the use of the non-recursive definition in BT-3.

1. Using pencil and paper, develop a recursive piecewise definition for pascal(n,r) (the term in Pascal's Triangle at the n'th row, r'th column).
2. Implement your definition from a. through the following method, add it to your static NumericalMethods class. Add the Big-O of this method to the javadoc comment.

   /**********************************************************************
   * This method recursively determines the element of Pascal's Triangle *
   * in the nth row, rth column.                                         *
   * Precondition: n>=0, 0<=r<=n                                         *
   * Postcondition: the method return the element of Pascal's Triangle   *
   *                in the nth row, rth column                           *
   * @param n the row number                                             *
   * @param r the column number                                          *
   ***********************************************************************
   public static int pascal(int n, int r)
   

3. To complete this initial look at the Binomial Theorem, add the following two methods to your BinomialTheorem driver and include code soliciting appropriate input from the user.

/***************************************************************************
* This method returns the String representation of the r'th term of the    *
* Binomial Theorem of (a+b)^n                                              *
* Precondition: a, b the String equivalents of the binomial's terms        *
*	              n>=0, 0<=r<=n                                        *
* Postcondition:the method returns the String representation of the r'th   *
*	              term of the expansion of (a+b)^n.                    *
* @param a the first term in the binomial (a+b)                            *
* @param b the second term in the binomial (a+b)                           *
* @param n the degree of the binomial expansion                            *
* @param r the required term in the binomial expansion, 0<=r<=n            *
****************************************************************************
public String binomialTerm (String a, String b, int n, int r)


/***************************************************************************
* This method returns the full binomial expansion of (a+b)^n as a String   *
* Precondition: a, b the String equivalents of the binomial's terms, n>=0  *
* Postcondition:the method returns the String representation of the        *
*                expansion of (a+b)^n                                      *
* @param a the first term in the binomial (a+b)                            *
* @param b the second term in the binomial (a+b)                           *
* @param n the degree of the binomial expansion                            *
****************************************************************************
public String binomialExpansion (String a, String b, int n)

The Golden Ratio (φ) from a Continued Fraction. A compelling topic in pure mathematics is Continued Fractions. The essential idea is that the deeper the evaluation of these expressions, the better the approximation is to the ultimate irrational target, or what we prefer to call in Calculus, the limit. The programmatic evaluation of these expressions is a good fit with your understanding of recursive methods. Here is one example of the continued fraction leading to the Golden Ratio.

(GR-2)

The limit of both (GR-2) and (GR-1) is φ.

Task. To your Recursive Project, implement the class GoldenRatio, the output of which will allow the viewer to confirm that both sequences (GR-1) and (GR-2) converge on φ. Maximize your use of recursive methods. Beyond the correct answer, evaluation of your submission will focus on the elements of good programming: method design, efficient implementation, clearly-labelled output and strong documentation. Finally, keep in mind the following,

1. Both strategies incorporate recursion to determine their n'th approximations to the Golden Ratio.
2. The n'th approximation of each strategy are identical (i.e. grFib(1) and grCF(1) are 1, grFib(2) and grCF(2) are 2, and so on...)
3. Recursive methods are elegantly (and deceptively) simple.

The Golden Ratio (φ) from the Fibonacci Rectangle. In class we investigated the relationship between the sequence defined by the quotients of successive terms of the Fibonacci sequence and the Golden Ratio, φ. This can be expressed as the process,

(GR-1)

Fibonacci Rectangle	Square Construction with Compass and Straightedge

Task.

1. Explain where to look on the graphic above left to confirm (GR-1).
2. The animation above right demonstrates the technique for construcing a square using only a compass and straightedge. In your Sketchbook, use this procedure to duplicate the Fibonacci Rectangle above left.

Fibonacci Sequence.

1. The first two terms of the Fibonacci sequence are defined as t₁=t₂=1. All remaining terms are defined as the sum of the previous 2 terms.

2. Develop the Java method public int fib (int n) that iteratively determines and returns the nth term of the fibonacci sequence. What is the Big-O of this implementation?
3. Write a piecewise definition of the nth term of the fibonacci sequence, t_n, in a recursive style similar (1) below. Develop the Java method public int fib (int n) that exercises this definition. What is the Big-O of this implementation?
4. Is there a way to determine t_n in O(1) without using a lookup table?

Powers. It is virtually impossible to provide practical programming solutions to a variety of complex problems without recursion. As such, it is an indispensable programming strategy. Having said this, you'll have to decide when it's warranted. Successful implementation of a recursive solution depends on your ability to define a recursive solution on paper. For example, the power function, xⁿ can be defined iteratively (non-recursively) as,

Defined recursively, we could write,

(P-1)

From (1), the implementation is straightforward. Successful recursive solutions arise from the programmer being able to express a definition similar to (1) for each new problem, that includes both the general recursive substitution expression and a basis or stopping condition.

Tasks.

1. Create the project, Powers. Implement the methods described below and supply statements in the main method to test them. Include your suggestion for the Big-O of each algorithm in the comment preceding each method.
2. Develop the Java method public int powerIterative(int x, int n) that determines and returns the value of xⁿ, iteratively. What is the Big-O of this implementation?
3. Develop a second version of public int powerRecursive(int x, int n) that determines and returns the value of xⁿ, recursively. What is the Big-O of this implementation?
4. Develop a third version of public int pow2(int n) that computes the value of 2ⁿ with a running time of O(1).
5. Improved Power Algorithm. Can the Big-O of the iterative and recursive power algorithms above be improved? Identify a pattern from the following examples,

   

   1. Explain this algorithm.
   2. What is the Big-O of this algorithm?
   3. Write down the piecewise definition of the algorithm
   4. Code the algorithm into the method public int powerImproved(int x, int n)

Perfect Powers.

1. Develop an inductive expression for perfect cubes, C_n+1, in a manner similar to our in-class development of the formulas for the perfect triangles, T_n+1 and the perfect squares, S_n+1 .
2. Looking at the three inductive formulas you have engineered, again, identify the role play by Pascal's Triangle.
3. Use this observation to propose and confirm (by example) inductive formulas for perfect fourths and fifths.
4. (New) What does the algebra of the perfect fourths formula suggest about the geometry of the fourth dimension?
5. Rewrite your inductive expression for the perfect cubes, C_n+1 in Step 1 as a piecewise recursive function suitable for coding.