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 hard, employ a stepwise refinement strategy and post concerns as required.

AP Exam Prep. This year's AP Computer Science Exam will be written in the morning of Tuesday May 8th.

1. CodeBug. February 14-16. 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. Have your source code ready to go for the start of Thursday's class and we'll sample a few.

2. Gridworld UML: TBA. 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.
3. Sample GridWorld Exam Questions. With pencil and paper only, grab the kitchen timer and allow 15 minutes to answer the 5 Multiple Choice questions from the test. Take a 10 minute break and then allow yourself 50 minutes to answer the two Free Response questions.
4. Sample Exam A-1. (Sunday April 29). With pencil and paper only, grab the kitchen timer and allow 60 minutes to answer the 34 Multiple Choice questions from Sample Test A-1 that begins on page 185. Do not attempt Questions 35-40 as they refer to the previous Case Study, not GridWorld. Take a 15 minute break and then allow yourself 75 minutes to answer the Free Response Questions 1, 2, and 4 from Sample Test A-1 that starts on page 205. BRING YOUR RESPONSES TO CLASS ON TUESDAY MAY 1.
5. TBA. 2010 Free-Response Questions. Bring your responses to class on TBA for discussion and scoring detials
6. TBA. 22 FC Questions on page 17. Confirm answers yourself.

The Game of Life. John Conway introduced the world to one of the most studied algorithms within the Cellular Automata family in the October 1970 issue of Scientific American. Read Wikipedia's explanation of the simple rules for propagation. In the applet to the right, I colour-coded the cells as Birth, Survival and Death. Explore the game through either or both of the Explore links on the course page. Give yourself time to enjoy how such an elegantly simple set of rules can produce such fascinating outcomes.

Task.

1. Add a seventh column to your Fractal Framework applet entitled Life.
2. Design and implement a Drawable class called Life, modeled after this UML diagram.
3. Add menu items that include one or more random seeds and a library of a handful of known patterns that you find inspiring. Glider Guns, Puffer Trains, and Tire Tracks are my favorites.

The Collage Theorem: The RSGC Library Evergreen

Pre Task.

1. Obtain a stand-alone copy of IFS Freestyle (so codes can be saved and reloaded). Note: This is only one of six free IFS Explorer Tools. If you are the least bit inspired, click on the 5 other tools to see what each is capable of rendering. Fascinating.
2. Familiarize yourself with the tools and what can be achieved.
3. Load one or more of the .fif files to confirm loading, displaying and saving
4. Play. Does a single affine transform (AT) yield anything? Add a second (no more) and explore all the tools before adding anymore AT's. If you come up with a image that looks familiar, please show the group!
5. Here's a quick tutorial on how to make a Tree. Try it. Be sure to confirm saving and loading.

Task. Using the experience gained from the use of the IFS Freestyle application together with insight gained from reading Cut-The-Knot's description of the Collage Theorem, you are asked to render as close an approximation to the RSGC Library Evergeen Tree depicted in the photo to the right.

Here's a paper on Fractals and the Collage Theorem developed as a requirement for someone's MA in Teaching Middle School mathematics. (Keep this is mind for when your turn comes around:)

IFS: Iterated Function Systems. With the conceptual and mathematical foundations laid, you can now undertake the next stage of your Fractal Framework application to render ever-more realistic natural forms.

Task.

	IFS
	Deterministic
	Fern #1
	Fern #2 (lower)
	Leaf
	Maple Leaf
	Tree #1
	Tree #2

1. Examine my javadoc for ths IFS-related classes (IFS, IFSDeterministic, IFSRandom)
2. Java's awt.geom package contains two useful classes for this project: AffineTransform and AffineTransformOps.
3. After your L-Systems menu, add one entitled IFS.
4. Under the IFS menu, add menu items similar to those in the second column of the table to the right, starting with Deterministic.
5. 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. 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 structure could be initialized within the constructor of the Content class.
6. Provide colourful renderings of the image that make optimum use of the panel.

Social Network: TreeMap<Friend,Friend>. I have come to the conclusion that ACES are spending too much time programming and not enough time socializing. To resolve this situation, I have assigned each student a friend. Friendship is one-way. That is, if Scott is assigned to be John's friend, Scott must be friendly to John, but John is not required to reciprocate. Every student is assigned exactly one friend. Sometimes, a circle of friends occurs. For example, if Scott is assigned to John, John is assigned to Kjell, Kjell is assigned to Tuan, and Tuan is assigned to Scott, we have a circle of 4 friends containing Scott, John, Kjell, and Tuan. In the circle, we can say that Scott has a Bacon Number of 0 from John, of 1 from Kjell, of 2 from Tuan (and of 3 from himself).

Task. From a TreeMap of Friend objects, determine whether two students are in the same circle of friends, and if so, state the Bacon Number of the first from the second.

1. Create a project called Network and a driver class of the same name that encapsulates a TreeMap<Friend,Friend> Collection.
2. Create an inner Friend class along the design of the UML
3. Network's main method reads in the mappings from the text file, Friends.txt, and constructs the map.
4. Implement the recursive Network method,

   /**
    * This recursive method displays the sequence of Friends 
    * from x to y and returns the corresponding Bacon Number of x -> y.
    */
    private int baconNumber (Friend x, Friend f, Friend y)
   

5. Each run of Network will randomly select two Friends (keys) x and y, from the map and either determine the Bacon Number from x to y or state that they are in a Different Circle.

Sample Input:
Mao Jiashi
Scott John
Anthony Simon
John Kjell
Tuan Scott
Matt Isaac
Simon Mao
Kjell Tuan
Jiashi Matt
Isaac Anthony


Sample Output 1:
Simon->Mao
Simon->Mao
Bacon Number: 0

Sample Output 2:
Simon->Simon
Simon->Mao->Jiashi->Matt->Isaac->Anthony->Simon
Bacon Number: 5

Sample Output 3:
Matt->Kjell
Matt->Isaac->Anthony->Simon->Mao->Jiashi->Matt
Different Circle

Sample Output 4:
Scott->Kjell
Scott->John->Kjell
Bacon Number: 1

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 resuts. Here's a worked example to assist with your development.

2. (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 solveSytemmethod (it will simply call cramersRule for now) statements at the end of your Matrix2DTest driver to confirm your resuts.

3. (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 typed as follows,)

   

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

BRACKETED LINDENMAYER SYSTEMS. You are now ready to undertake the rendering of primitive plantlike structures similar to the approximation of the tumbleweed to the right.

To facilitate the branching characteristics inherent in plants, L-System productions introduce brackets. Your rendering method will interpret the open bracket '[' as a command to preserve the current drawing state (position, heading, and possibly colour and line thickness), to be restored on the encounter with the next close bracket ']'. In this way, your drawing algorithm can 'return' to a node and continue drawing in another direction. A Stack<Turtle> is a perfect collection for this purpose.

Task.

1. Under the new menu, Bracketed L-Systems, include menu items corresponding to Figures 1.24a through f as found on page 25 of the Algorithmic Beauty of Plants. Reference: ICS4U Framework Applet.
2. Without creating a new class, enhance your LSystems draw method to accommodate the additional characters, [ and ] which are designed to preserve and restore the state of the Turtle object
3. Feel free to experiment with colour, thickness, scale, and position in your rendering of these structures to portray as much realism as you can.
4. Submit your updated Framework source code to handin and have your web page updated by the deadline.

ACES Garden
Photo From Metro News Feb 16, 2012. p. 20

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

Task.

1. Add a new menu to the immediate right of Koch Constructions, entitled L-Systems.
2. Under the L-Systems menu, add menu items for the Koch Snowflake, the Koch Island and each of the images found in Figures 1.7, 1.8, and 1.9 on pages 8-10 of the ABOP download. See Framework.html.
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.

Extra Credit. In response to the interest in an independent project for extra credit, I have assembled five images below for your consideration. If you find an image intriguing you are invited to contact me to work out the specifications and timeline of a possible project.

Dragon Curve: Tesselation	Dragon Curve: Morphology	Sierpinski Zoom
Newton's Method: f(z)= z5-1	2D Barcode: Data Matrix	?

KOCH CONSTRUCTIONS: Tilings (Tesselations). We'll use this short week for a particularly creative enhancement to our Framework.

Attempts to cover a plane with shapes is both a fascinating and practical application of geometry. The decorative arts are a rich source of examples of tiling the Euclidean Plane from the ancients to the more modern (Gaudi, Escher). Indeed, one of the greatest geometers of the 20th Century, H. S. M. "Donald" Coxeter, spent most of his career at the University of Toronto (1907-2003) in which he explored tilings of the Hyperbolic Plane among other pursuits. TVO's: The Man Who Saved Geometry:

Understandably, shapes that possess symmetrical properties lend themselves easily to tiling. This author highlights four types of symmetries in the plane. By simply translating squares and hexagons, the plane can be completely covered. Triangles require glide reflections (reflection & translation) to accomplish the same feat.

Task.

1. Launch this Framework applet and study the four tilings under the Koch menu.
2. Add menu items entitled Snowflake Tiling and Island Tiling under the Koch menu of your Framework.
3. Rotational symmetry is inherent within your Triadic Koch Snowflake (6-fold) and Quadratic Koch Island (4-fold) sprites. Exploit this characteristicthrough the use of your Transform2D classes to present a tiling of the entire plane for each selection.
4. We can never be sure where our interests will lead us. One or more of you may be interested in further investigations combining your coding skills with geometry and topology. One such classic twinning is the Four-Colour Theorem.

Snowflake Tiling	Island Tiling	Départments Français?

Fractal Framework: Web Support. Complete the web support content for each of your Framework entries up to and including the Triadic Snowflake and Quadratic Island algorithms. Remember, this is a body of work you will want to proudly reflect on in the years to come. The focus of your content should be to explain using your mathematics skills, not merely casually summarize in words. Your readers want to learn! To assist with the Triadic Snowflake, consider completing and summarizing the table to the right for the perimeter and area of the Snowflake.

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. 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. Your constructor should generate a entire collection of subsets to be 'removed' prior to finishing. This wil lbe accomplished through the call, deconstruct(triangle,1) to this recursive method.
3. The animated gif (above, left) presents a depth of 7. The draw() method will simply render the triangles at each level from your container on each pass.
4. (Optional) Modify Content's current object to point to an instance of the TriadicCantor. This will make it appear when the applet launches.
5. Repeat Steps 2 and 3 by implementing the class QuadricCantor.
6. A premium will be reserved for code that is efficient, clear and well documented. Make maximum use of the Polygon class and any of the JCF data structures we've studied.
7. 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.
8. Complete steps similar to 1 through 6 for the QuadricCantor rendering.

CANTOR TERNARY SET (Part 2 of 3): Implementation

1. Add a new menu to the immediate right of Gaskets, entitled Cantor Sets.
2. 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 of removal. The animated gif to the right presents a depth of 5.
3. Modify Content's current object to point to an instance of the LinearCantor. This will make it appear when the applet launches.
4. After consulting a number of online references for the Cantor Set give careful thought to the design of the data structure to house the intervals (Model) and the manner in which you will render the Model (View) (clear separation of Model and View is critical to effective implementation). You are strongly encouraged to add your Transform2DTest project to Framework's Build Path. Your Point2D, Matrix2D and Transform2D classes are terrific support for this and upcoming projects.
5. Display the Set to depth of at least 5 removals.
6. A premium will be reserved for code that is efficient, clear and well documented.

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. On your ICS4U home page that contains your Fractal Framework Applet, code an HTML table similar to the one below (do not simply add this graphic) that presents a quantitative analysis of the stages of the Cantor propagation. W3Schools: Images, Tables
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 or is there a limit?"

Note: A premium will be placed on the inclusion of graphics of properly formatted mathematics captured from Word's Equation Editor or some such typesetter.

groups of adjacent even numbers

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 Number segment.
4. Update your home page.
5. Submit your source code to handin by the deadline under the Subject: Pascal's Carpet.

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 (after Pascal's Numbers) to The Chaos Game
3. Design and implement the Drawable class, ChaosGame, that, after three mouse clicks from the user, will display a 100,000+ points according to the conditions of the Chaos Game.
4. Remount your Framework applet.
5. Submit your source code to handin by the deadline under the Subject Line: The Chaos Game.

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. Complete the body of PascalsNumbers' draw() method to display the required number of rows onto its img object.
2. Generate the values using the most efficient Big-O strategy you can implement.
3. Configure the font, the line spacing, and the number of rows to fill the available space.
4. The elements of the Triangle are appear centered horizontally as the example to the right demonstrates. Use the FontMetrics class to assist you with this. Here's an online example.
5. Finally, add Framework to your home page as an applet. Submit your source code to handin.

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.

Matrix2D Enhancements. Important enhancements to your Matrix2D class are required to support future investigations of the Collage Theorem and, ultimately, IFS Codes. These include the concepts of the determinant and inverse of a matrix and their application to solving systems of equations.

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.

   

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. Create the project, Animation2D, and add this driver. Configure your build path to include your Transform2D classes to access Transform2D, Matrix2D, Point2DList, and Point2D. This is the best of both worlds, since we're only keeping 'one set of books', so to speak. Look over the driver code. The general idea is to transform a Sprite object(s) 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 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. In this second instalment, you are asked to created a project called Transform2DTest, using the driver, Transform2DTest.java. Add the class file Point2DList.java and implement the supporting Point2D. Configure your Transform2D project to refer to your Matrix2D class found within your Matrix2DTest Project, as I will when I evaluate your work. Note that this is a far safer project design as you are not maintaining two or more versions of the class.

Task. 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 following 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... 2010-2011 2009-2010 2008-2009 2007-2008 2006-2007

M. Lapinsky	K. Pladsen	S. Knowles
T. Nguyen	J. Wilson

PART 1. Matrix2D. 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.

Notes

1. 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.
2. Make every attempt to maximize the use of a minimal set of methods.
3. Minimize the dependency of your code on direct references to the only instance field, matrix.

Reverse Polish Notation (RPN) Evaluator. The next enhancement to your Recursion Framework requires the application of your recursive skills to the evaluation of arithmetic expressions expressed in postfix, rather than the common infix form, we are accustomed to. The animated gif to the right demonstrates the evaluation of the postfix expression, 235*+.

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 Recursion Framework 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. Develop, document, and deploy your Recursion Framework by the deadline.

Big Box Simulation 1: Queue<Customer>. An interesting ad on TV these days is a boast by Lowe's that if a checkout line grows longer than 3 customers, they'll open a new one. As an expert in the field of Management Science, you have been contracted to determine how realistic this claim is. With the holiday season approaching, a few store managers are worried that they may not have the staff to honour this initiative.

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 isavailable.

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: Develop your logic over a shorter day, then expand it to a full day (720+ minutes)
• 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.

Recursive Parentheses 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,

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,

Sudoku. One of the most popular pastimes TTC riders engage in is solving a Sudoku puzzle. Since your recursive skills are rapidly improving, wouldn't it be a crowning achievement to code a Sudoku-solver? An animated gif of my row-major solution appears below right (similar to the technique introduced last year to demonstrate the sorting algorithms). The first few thousand images (4209 in total) develop the solution slowly (giving you an opportunity to witness the backtracking you'd expect from trial and error) but, as you'd suspect from an algorithm with exponential Big-O, it finishes up pretty quickly.

Sudoku Example	Animated Solution

Task.

1. Add a Drawable class to your Recursion Framework by the name of Sudoku. This class encapsulates a starting model of the Sudoku game to right, as in,
   byte [][] model = {{5,3,0,0,7,0,0,0,0},{6,0,0,...
   where 0's are used to represent empty places in the board.
2. Since the goal is to animate your presentation after the recursive solution is discovered, you'll need a data structure to hold the frames, as in,
   ArrayList <byte[][]> solution;
3. Your Sudoku constructor should add the starting model to the solution list prior to calling your recursive solver method, solve(x,y), where (x,y) starts at (0,0).
4. To keep the solve(int x,int y) method as lean as possible, I suggest the inclusion of some supportive helper methods, similar to,

   

5. For the recursive solve(int x,int y) method, the basis condition and inductive stages must be determined. For the former, it should be appreciated that the puzzle would be solved if 9 rows were correct. For the inductive segment, it should be realized that for unfilled entries (0) the potential for all ten digits being inserted must be enabled to ensure that the existing row, column and Box entries to that point are unique. New insertions should trigger a saving of the model for later replay. If a repetition is found, the cell entry should be set back to 0 and backtracking should occur.
6. Once the puzzle is solved, the draw() method can simply replay the saved frames from solution.

Maze Generation and Traversal. We're going to devote this week to a group investigation of mazes: their generation algorithm and solution. This is a classic example of depth-searching as you were introduced to in last week's recursive floodfill project. In addition to exploring this algorithm, I want to draw your attention to the Processing language. This new Java/C hybrid offers some amazing opportunities and, with your skills, you'll catch on very quickly. A subset of the Processing language forms the backbone of our new Grade 11 Arduino hardware course.

Day 1 (Orientation of Maze Generation and Traversal concepts with interactive examples)

1. Maze Generation Tutorial
2. Create the Eclipse Project, Sketch, and add the source code for the Sketch classes from here.
3. Install the Processing language on your laptop
4. From the File>Examples menu, load a few and run them
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. 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.
8. With minor modifications, the Cell, Rand, and Maze classes can be inserted into your RecursiveFramework class.
9. Insert the Sketch class into RecursiveFramework, renaming the former to MazeWorks.
10. 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).

11. 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.
12. This author provides a very good explanation of the thinking behind recursive strategy to solve the maze (and so many similar problems).
13. 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
14. If you're still unsure and you want to look at the structure of the code for a solution look here.
15. Develop and mount your solution.

Flood Fill. The Paint Bucket tool of many graphics applications is used to fill the interior of a bounded region with a given colour. Typically, the algorithm identifies the colour of the pixel at the mouse click and then follows a linear path to any pixel with a different colour. This 'different' colour, it assumes, is the border colour, which is continues to seek out in all directions as the perimeter of the region to be 'flooded'.

In this assignment you are to flood fill a region by implementing a 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 an interesting recursive exercise. For your regions, you can use one of the standard Graphics2D Shape classes ( ie, Rectangle2D, Ellipse2D, Arc2D, etc.) and a piecewise Shape of your own original design.

Task.

1. Add menu items to your Recursive Framework project similar to the image to the right.
2. Under the Flood Fill menu, add the items as shown to the right.
3. Implement the Drawable class, FloodFill , whose constructor accepts an integer parameter indicating which submenu item was selected to be outlined and filled.
4. After drawing the requested outline, FloodFill's draw(BufferedImage img) method could assign to a class BufferedImage variable the value of img prior to calling its recursive flood(x,y) method to fill the interior of the shape. The initial x and y values are any point known to be in the interior of the region.

Include an Ellipse (Ellipse2D.Double), the Shamrock (multiple Arc2D.Double paths) and any other piecewise Shape your imagination can whip up. Again, keep your outlines small since the system stack has to store many return addresses to manage the depth of your recursion. Also, don't forget to update your home page prior to submitting your source code.

Recursion Framework. Since many of the investigations ahead of us are graphic, a dual graphic framework (application/applet) that would permit your users to select from your various undertakings would make a impressive portfolio for the years ahead. Using last year's Framework Project as a model (I returned it to you recently), create a new project called RecursionFramework. Here's a rough UML design to refresh your memory.

Tasks.

1. Review the UML diagram above for the Framework code, renaming it RecursionFramework of course.
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 500 in the Parameters Tab of the Run Configuration dialog.
5. Finally, review the code, familiarizing yourself with all aspects.

Pascal's Numbers. Create an inner class called PascalsNumbers and implement its UML above. Complete the body of PascalsNumbers' draw() method to display the required number of rows onto its img object. To get an idea of what you're trying to achieve, check out the Pascal's Triangle activity found under the Gaskets menu of Reuben Sagman's Fractal Framework applet. Generate the values using the exponentially-inefficient recursive techniques discussed in class this week (simply for practice) and be sure to enable the characters to line up in columns. Finally, add RecursionFramework to your home page as both an executable jar and an applet to confirm. Submit your source code to handin.

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 (unless we did so last year), 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 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 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, φ. In class last Wednesday 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,

(GR-1)

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 it 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 for the Golden Ratio.

(GR-2)

The limit of both of these sequences is φ.

Task. Develop a java project called GoldenRatio, the output of which will allow the viewer to confirm that both sequences (1) and (2) converge on φ. You will maximize your use of recursive methods, but beyond that, the design of the classes and methods are yours to decide based on our efforts last year. Beyond the correct answer, my evaluation of your submission will focus on the elements of good programming: class and method design, efficient implementation, strong documentation and highly intuitive output. 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.

Palindrome. A palindrome is a String of characters that reads the same forwards as backwards. Words like racecar and Madam are palindromes. A phrase like "Madam, in Eden, I'm Adam" is also a palindrome if we eliminate the punctuation and spaces. Your task is to develop software that will verify whether or not an entered phrase is palindromic. Run the executable jar file Palindrome.jar I've created as a model for your own implementation.

Project Expectations

1. Name the project, Palindrome, and create a driver by the same name that uses JOptionPane's showInputDialog and showMessageDialog methods to communicate with your users.
2. Create the class, Phrase, that encapsulates the String entered for testing by the user, and implements methods required by the adjacent UML.
3. The purpose of the preProcess method is to remove punctuation and whitespace from the entered String.
4. The reverse method is to be recursive.
5. You are expected to make good use of the available methods offered by the String class.
6. Full documentation is expected.
7. Attach Palindrome.java and Phrase.java to an email to handin by the deadline.

Fibonacci.

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?

Improved Power Method. The complexity of versions 1 and 2 of the power function below (iteratively and recursively) is O(n). Can we do better? Consider the following strategy,

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

Power. 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 non-recursively as,

Defined recursively, we 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 inductive substitution expression and a basis or stopping condition.

1. Develop the Java method public int power(int x, int n) that determines the value of xⁿ, iteratively, and returns the value of the expression. What is the Big-O of this implementation?
2. Develop a second version of public int power(int x, int n) that determines the value of xⁿ, recursively, and returns the value of the expression. What is the Big-O of this implementation?
3. Develop a third version of public int pow2(int n) that computes the value of 2ⁿ with a running time of O(1).