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.

IFS Deterministic: Iterated Function Systems. Each iteration of the IFS Random 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. Add a menu separator after the last IFSRandom menu item in the Barnsley menu before adding at least 4 menu items for the IFSDeterministic renderings you are about to implement (this brings the total number of entries within the Barnsley menu to 12). Visit Yale's Deterministic IFS Applet for inspiration.
2. Create a class IFSDeterminstic that extends IFS along the lines of,

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

   that will implement the invariant or Deterministic IFS algorithm described on the Yale site.
3. Implement the IFSDeterministic constructor to include the creation of the following structures as discussed in class,
   

   	AffineTransform[] transforms;
   	AffineTransformOp[] ops;
       

   and populate these references from the data contained in the code object.
4. Revisit your favourite Catalog Activity investigated this year (I used TriadicKoch to prepare the above image). Add the method,
   

   	public BufferedImage getImage()
       

   to this class that will return a full rendering of it as BufferedImage object. You'll use this image as the starting point for each of your preferred Deterministic IFS renderings.
5. 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.
6. 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 Catalog application to render (somewhat realistic) natural forms.

Task.

1. Add a second-to-last column to your Catalog application entitled, Barnsley
2. Review the IFS gallery 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 Activity class. 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 Activity {
         

   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 library of type TreeMap<String,Code> where String is the name of the IFS, thereby making retrieval from within your actionPerformed() method relatively efficient. This transforms/probability 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. Impressive results from last year's ICS4U ACES can be viewed here...

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 image 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	Hillyer: Sierpinski Sieve	Sansom Original

Task.

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 appeared content to simply remove 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 suggests the recursive application of each strategy. Koch went further. Using each of the three sides of an equilateral triangle as initiators he applied his replacement strategy (generator) repeatedly, 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 Space-filling curves or Sfcs (Pfcs for now). The realization of this assignment will result in the next menu in your Catalog devoted to a class of Sfcs that we'll attribute to Koch (there's not enough time in this course to investigate 3D Sfcs (Hilbert Cube) but I'd welcome an email from you someday linking me to your future explorations).

Triadic Koch Snowflake	Quadratic Koch Island

Task.

1. 

2. As a starting point for this project, consider Exercise P13.15 from a Java 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.
3. Add a new Koch menu to your Catalog project, to the right of Cantor as shown below,

   

4. Create a new Activity class by the name of TriadicKoch that encapsulates an ArrayList<Sprite> of size equal to the maximum depth of generation.
5. 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.
6. Using an algorithm similar to the textbook example above, employ recursive generation strategy to propagate a sequence of Sprite objects representing the outline of successive generations of the Koch Snowflake.
7. Koch's draw(BufferedImage img) method can create and fill a Polygon from the respective Sprite data.
8. Repeat the 4 steps above for the class QuadraticKoch.
9. (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.

CANTOR TERNARY SET (Part 2 of 3): Implementation. A gasket-like object can be constructed by a process that removes parts of its body. In this assignment you are asked to render the Linear Cantor Set with a strategy involving rectangles of minimal height to represent the line segment intervals.

1. Complete this Cantor Set investigation with pencil & paper. (Word, PDF)
2. Add the menu structure defined by the screen capture in Class 53 to your Catalog (Framework) project.
3. Implement a new Activity (Drawable) class entitled LinearCantor. Its constructor should receive the maximum depth, n, 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 a collection of predetermined size to house all the segments. The collection is to be fully populated before the constructor ends through a call to the 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 collection's data will be used to support an animation by your draw method).
5. Display the Cantor 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.

CANTOR (TERNARY) SET (Part 1 of 3): Analysis. The Cantor Set is an appropriate launch point for our consideration of fractal and topological dimension. A recursive (or iterative) algorithm removes an open third of each segment at each stage of propagation. For this reason, the Cantor Set is also known as the ternary or middle third Set. Here is a link to Wolfram's (Mathematica) animation of the Cantor Set and the Cantor Function.

1. 

2. 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?"

Catalog: Calculus. This submission will require a merge of your two major projects this year. The two projects will continue to cooperate with one another over the course of the year but as remain in separate entities. For guidance, refer to the 2011 ICS4U Final Exam.

Task.

Submit documented source code by Sunday February 8 as instructed.

Elective. (Status: OPEN) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: ??. Start: ??. Finish: ??)

CBC Logo. CBC logos have changed over the years. Its current kaleidoscopic image offers the analytical mind of a curious ACE the chance to explore a recursive deconstruction of the circle.

One analysis suggests the core of the image to be a simple red circle. Compass-direction based sliced partitions of the circle then appear to animate outward, proportionally, at which point a secondary partition is undertaken and the animation extends to a second level.

Task.

Elective. (Status: OPEN) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: ??. Start: ??. Finish: ??)

Combination Lock I. 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.

A correct implementation of the Lock class instantiated with the combination 21-32-34, will generate the following output,

Combination Lock II. Visualization of Combination Entry. The goal of Part II of the Combination Lock project is to present an accurate rotation of the dial of your Dudley lock as required for any user-requested combination.

In the animation above right aI single clockwise rotation of the dial is presented to give you an idea of the semi-realistic outcome you're aiming to achieve. To accomplish this, I downloaded an image of the Dudley lock (below) and cut out the dial only as a square with a transparent background (right).

Dial.gif (120 x 120)	DudleyLock.jpg (300 x 300)

With the background BufferedImage of the lock drawn first, the draw() method of the Activity can apply a sequence of 1° rotations (AffineTransformation) to the dial before drawing over top of the background.

Task.

Calculus Project: Expression 'Language'. Of all the assignments you've been asked to complete over the past couple of years, you'll likely remember this as one of the most satisfying. As could be expected of a comprehensive project, it attempts to tie together some of the most important concepts within the co-disciplines of mathematics and computer science. For years to come, you will marvel at what you are about to accomplish. Finally, since your exam will expect that you extend this work in some new direction, you are encouraged to develop efficient and well-documented code.

The first step in writing IMAGE-Algebra&Geometry many years ago was a three-month investment in developing a customized language before an interpreter could be undertaken. At the root of every language there are a set of tokens (vocabulary) upon which is based a set of rules for assembling the tokens (grammar). Similarly, your first step in developing an application to manipulate mathematical expressions is to develop an unambiguous language for the expressions you expect to interpret. There are different ways to define grammars. The eXtensible Markup Language (XML) is in widespread use today. Backus Naur Form (BNF) is common within the computer science community (Example: ASCIIMathML Syntax). We'll use the intuitive 'railway diagram' strategy.

Based on your understanding of secondary school level mathematical expressions, reduce the terminology into a vocabulary (consider these) and, from there, engineer a recursive grammar by completing an unambiguous sequence of railway diagrams that will embrace the broadest range of mathematical expressions you have encountered to this point. Here's how your grammar will begin...

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

1. 1.  

   2. 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. 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,

   1. 1. 

         
         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!)

 

5. (DAY 4) Elective. (Status: OPEN) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: ??. Start: ??. Finish: ??)
   
   Gauss-Seidel. An interesting iterative strategy for solving a system of equations is referred to as the Gauss-Seidel method. Essentially, one simply picks a random solution and, through a repetitive feedback process, the output converges to the solution (under certain circumstances).
   
   Task.

   1. Research the Gauss-Seidel technique for solving systems of equations.
   2. Add methods to your Matrix2D class that enables users to efficiently exploit the Gauss-Seidel technique for solving a system of 3 equations in three unknowns.
   3. Add statements to your Matrix2DTest driver class to exercise your enhancements.
   4. Prepare instructional material on the technique and be prepared to teach it to your classmates.
   5. One month will be allotted from the date of commitment to submit exemplary, working source code.

Animation2D: 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. In the example below, a subject was sourced on the internet and an approximation developed with the tools developed in previous exercises that required the use of all four affine transformations (rotation, reflection, scaling and translation).

Static Clip Art Image Found Online	Animation2D Simulation	Menu Item

With your Matrix2D and Transform2D tools in place, you are ready to implement an animation based on matrix transformations, built on transformations. Before you do, let's look at the way previous ACES undertook the project in recent years. Add this driver to your Catalog Project and review and execute the 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 called 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. Considering your vast exposure to gaming animation, I know you'll take your effort to a whole new level.

Task.

Submission. Attach documented source files for your entire Catalog project, the .gif files for the animation and your .mov file, to an email to handin with the Subject: Animation2D by the deadline.

Animation2D: Part 2. Transform2D. In the second instalment of the Animation2D project, you will explore matrix-based transformations in R².

Task.

Animation2D: 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 this year's ACES. Check out more samples from ACES of previous years: Select a year... 2013-2014 2012-2013 2011-2012 2010-2011 2009-2010 2008-2009 2007-2008 2006-2007

G. Bateman (Bateman.mov)	S. Boyd	R. Friesen
T. Garrow	T. Hillyer (Hillyer.mov)	R. Solway (Solway.mov)
	P. Wright

Task.

Reverse Polish Notation (RPN) Evaluator. The next enhancement to your Catalog catalog requires the application of your recursive skills to the evaluation of arithmetic expressions expressed in postfix (operators follow their operands) 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<Integer> to track your progress. The end result of the project will be to animate the collection of intermediate Stack<Integer> objects to offer the viewer a frame-by-frame animation of the stack sequence

Task.

Elective. (Status: CLOSED) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: SB. Start: November 23. Finish: January 25)

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.

Task.

1. 

2. 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.
3. Once the puzzle is solved, the draw() method can simply replay the saved frames from solution.
4. One month will be allotted from the date of commitment to submit exemplary, working Catalog source code and, if you can, the animated gif, Sudoku.gif.

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

Elective. (Status: OPEN) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: ??. Start: ??. Finish: ??)

Puzzle 3. Sliding Tiles. I'm somewhat reluctant to offer this Project because it is difficult and success can be elusive. On the other hand, underestimating the talent and motivation of my ACES has never proven wise. So, accept the challenge at your own peril and know, beforehand, that my successful pursuit robbed me of no less than four hours of enjoyment of a sunny and warm October Saturday afternoon. The first five moves of one session has been captured in the animated gif to the right.

Task. Modify Puzzle2 to yield tiles that slide into the adjacent blank slot when clicked, reflecting a more realistic representation of the mechanics of the actual puzzle.

Note. The sliding interval in the animation to the right is longer than the one I set in for the creation of the gif. It must have something to do with browser-specific settings...

Elective. (Status: CLOSED) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: . Start: October 22. Finish: December 31)

Fibonacci Spiral. Review Wikipedia's description of the Fibonacci spiral which approximates the Golden spiral.

Task.

Catalog: File Menu: Open | Exit. For this weekend's Puzzle2 segment you may prefer to open images for puzzling other than the latest image in Content panel. These can be images you have previously generated and saved, or from some other source altogether.

Add the File Menu as it appears to the right. Add the Catalog field,

private static File file;

In your actionPerformed (ActionEvent ev) handler add the following code,

if ("Open".equals(command)) {
	try {
		if (openImage() == JFileChooser.APPROVE_OPTION) {
			content.current = new LoadImage(file);
			content.createNewImage();
			content.repaint();
		}
	} catch (FileNotFoundException e) {
		// TODO Auto-generated catch block
		e.printStackTrace();
	}
}

else if ("Exit".equals(command)) {
	dispose();
	System.exit(0); // calling the method is a must
}...

The Open command requires the following supporting method,

private int openImage() throws FileNotFoundException {
	String filePath = new File("").getAbsolutePath();
	JFileChooser chooser = new JFileChooser(filePath);
	FileNameExtensionFilter filter = new FileNameExtensionFilter(
		"Catalog Files", "png");
	chooser.setFileFilter(filter);
	int returnVal = chooser.showOpenDialog(this);
	if (returnVal == JFileChooser.APPROVE_OPTION) {
		file = chooser.getSelectedFile();
	} else
		System.out.println("Open cancelled.");
	return returnVal;
	}

public class LoadImage extends Activity {

	File file;

	public LoadImage(File file) {
		super(Color.black, Color.white, "LoadImage");
		this.file = file;
	}

	public void draw(BufferedImage bi) {
		super.draw(bi);
		Graphics2D g2D = (Graphics2D) bi.createGraphics();
		BufferedImage img = null;
		try {
			img = ImageIO.read(new File(file.getName()));
		} catch (IOException e) {
		}

		g2D.drawImage(img, 0, 0, null);
	}
}

Catalog: Cosmetic Enhancements.

Centering. A convenience for your users is to have your application appear in the center of the screen at launch. Study and add the following method to your Catalog class and a call from the constructor if you wish.

private void centerFrame() {
	// Center the JFrame on the screen...
	GraphicsConfiguration gc = getGraphicsConfiguration();
	Rectangle rect = gc.getBounds();
	setLocation((rect.width - appDimen.width) / 2,
		(rect.height - appDimen.height) / 2);
}

Gradient Fills. In the screen capture to the right I designed and applied a simple Gradient Fill to the background of my About panel. The code I used appears below,

	Rectangle bounds = new Rectangle(0, 0, width, height);
	Point2D start = new Point2D.Float(0, 0);
	Point2D end = new Point2D.Float(bounds.width, bounds.height);
	float[] dist = { 0.0f, 0.3f, 1.0f };
	Color[] colors = { Color.RED, Color.WHITE, Color.BLUE };
	LinearGradientPaint p = new LinearGradientPaint(start, end, dist,
			colors);
	g.setPaint(p);
	g.fill(bounds);

Antialiasing. Compare the quality of the text in the two About panels below. The one on the right had antialiasing enabled with the statement below,

	g.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING,
		RenderingHints.VALUE_TEXT_ANTIALIAS_ON);

No Antialiasing	Antialiasing enabled

Puzzle 1. Creation. The 15 Puzzle has an intriquing history that makes interesting reading. The goal of this two-part project is to provide users the option of transforming any active Catalog panel into a sliding puzzle. A U of T lab assignment on the activity presents the math in rigorous detail.

Try your hand at the game.

Part 1. Mathematical Underpinning: Permutations and Parity. The object of the puzzle is to slide a random permutation of the tiles into the proper sequence moving one tile at a time.

Since not all randomly-generated permutations are solvable the designer has a challenge. A random, brute-force strategy would be to perform some minimum number of tile swaps, stopping at the first one after which is deemed solvable. Alternatively, a deterministic algorithm would perform a predetermined number of swaps in which the empty square trades places with an immediate neighbour. In this way, no matter how many swaps are made, the puzzle is always solvable (simply by reversing the sequence of swaps).

Task.

Puzzle 2. Solution. The animation below left simulates the slides an average player might undertake in solving the puzzle.

Task.

Elective. (Status: CLOSED) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment.  (Programmer: RS. Start: September 29. Finish: October 29)

Antiphon's Process of Exhaustion. Calculus' central concept is the notion of a limit. This project conveys the idea of a limit through geometric animation. Antiphon (5th Century BC) is credited with the demonstrating that if the number of sides of a regular polygon is allowed to increase without bound, the polygon approaches circular properties. We say the circle is the limiting bevahiour of this process. This exercise has become known as the Process (or Method) of Exhaustion. Stated loosely algebraically, if we let `P_n` be an `n`-sided regular polygon, and `C` be the circle,

`C=lim_{n\to \infty}P_n`

Task.

Mandelbrot. In this project you are asked to port your JavaScript code for the Mandelbrot Set over to Java.

Task.

Elective. (Status: CLOSED) The first ACE to commit to this Project in an email to me can use a successful implementation of this task to improve his mark on either a previous or future assignment. (Programmer: TG. Start: September 26. Finish: October 26)

Robots: Towers of Hanoi. For those longing for the simpler days of such Robot classics as SaveThePlanet and CampusCleanUp comes the retro project: RobotTowers.

RobotTowers: Start	RobotTowers: Mid-Completion

Task.

You have one month from the date of commitment to submit exemplary, working source code.

Parity of a Permutation. Shuffling a given set of elements is meant to generate a permutation of the set. As we've discovered this week, a permutation of a set can be classified as having either even or odd parity, with both occuring in equal number across the collection of all `n!` possible permutations of a set of `n` distinct elements.

The purpose of this assignment is to demonstrate a single random shuffle of a set of elements and identify its parity as either even or odd. Before you begin, you may want to confirm manually that the parity of the permutation arising from a shuffle of the first 9 natural numbers above right is odd.

Task.

Three Recursive Classics. Given what lies ahead for students with your academic ability, it is appropriate to confront some of the classic recursive problems in our field at this time. Whereas countless internet sites offer ready-to-go solutions to these gems, conquering these problems on your own rewards you with a sense of scholastic satisfaction unlike few others. More importantly, undertaking deep analysis of simple problems builds the essential problem-solving Catalog you'll need to tackle more advanced challenges that lay ahead for which solutions may not be readily available.

We have determined from previous efforts that a successful recursive solution to a problem defined as a function of n, lies in the discovery of a two-part, piecewise solution consisting of the base case (typically, but not limited to, n=1) and the inductive case (a simpler problem expressed in terms of n-1). For each of the problems below, challenge yourself to find this piecewise solution with pencil and paper. Once you do, your coded solution will likely yield the correct result on the first run. Create a project entitled, RecursiveClassics, and drop in this driver.

1. The Euclidean Algorithm (pp. 90-92). At the very least, all natural numbers share a common factor of 1. Euclid discovered the property that the greatest common divisor of two integers a and b, gcd(a,b), not both of which are zero, is the largest positive integer that divides both a and b. The Euclidean algorithm for finding this greatest common denominator of a and b is as follows:

Divide a and b to obtain the integer quotient q and the remainder r, so that a=qb+r (if r=0, gcd(a,b)=b). Then gcd(a,b)=gcd(b,r). Replace a and b with b and r and repeat this procedure. Because the remainders are decreasing, eventually a remainder of 0 will result. The last nonzero remainder is gcd(a,b). For example,

	1260 = 198⋅6+72		GCD(1260,198) = GCD(198,72)
	 198 = 72⋅2+54		              = GCD(72,54)
	  72 = 54⋅1+18		              = GCD(54,18)
	  54 = 18⋅3+0		              = 18	
  

Develop the driver class RecursiveClassics that will solicit any two natural numbers (use JOptionPane's showInputDialog method). A call to your gcd(a,b) method will return the greatest common divisor of the two parameters. Finally, suggest the likely Big-O of the Euclidean algorithm method before researching the answer. PLace the answer in javadoc comment of the method.

2. Towers of Hanoi (pp. 564-565). 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

3. Permutations (p. 557). Last week we reviewed how the leaves of a binary decision tree could contain each of the permutations of a set consisting of 3 unique elements. We confirmed that a set of 3 unique elements yielded 3! or 6 leaves. In this exercise you will display all permutations of the characters of a given String.

Task. Read the author's description of his algorithm and study his code. Once confirmed, add this code to your RecursiveClassics driver (adding the static keyword to method headers) as well as the comment below, or one in your own words.

/*********************************************************************
 * This method displays all permutations of the StringBuffer str     *
 * The big-O of this task is O(?)                                    *
 * @param str the String whose permutations are to be displayed      *
 * @param n the length of the substring of str under consideration   *
 *********************************************************************/
 public static void permutations(StringBuffer str, int n)

For the string "ABC", the output should read,

BCA
CBA
CAB
ACB
BAC
ABC

4. Base Conversion. The adajcent algorithm demonstrates a technique for converting a non-negative decimal (Base 10) integer to its binary (Base 2) equivalent.

Task.

Implement the technique as a recursive method that accepts a number and the target base. Return to the RecursiveClassics project from earlier in the year and incorporate the style of the sample code below to demonstrate conversion from decimal to ternary (Base 3).

	public static void main(String args[]) {
		int number = 6;
		int base = 2;
		
		System.out.printf("%d(10) = %s(%d).\n", number, convert(number,base), base);
	}

	/**
	 * Implements a recursive approach to base conversion
	 * 
	 * @param num  the number to convert
	 * @param base the target base
	 * @return the converted number
	 */
	private static String convert(int num,int base) {
		...
	}

Perfect Powers. This is a fairly straightforward coding task once you've organized your thinking. To add additional value to the effort, refresh your strong HTML skills by placing your responses to questions 2 and 5 in the opening javadoc of the class.

Review. Create the project, Review. Using the references cited, review and (where requested) implement documented code for each of the following. Have your solutions ready for presentation and discussion on September 8-10.