| 2012-2013 ICS4U SOFTWARE ENGINEERING TASKS |
TASK 'CHALLENGE' RATING (offered
to assist you with project management strategies) |
||
 |
Routine |
Typically some deep thinking required,
but not necessarily a lot of coding. |
 |
Hard |
Likely involves either a multiplicity
of (possibly new) concepts or algorithms. Allow time. |
 |
Buckle Up |
Start immediately, think
deeply, employ a stepwise refinement strategy and post concerns
as required. |
Jumble. I've often wondered, "What word in the English language has the most permutations that are also words?". You are asked to develop code to inform you and I, both. You'll make maximum use of the data structures and algorithms we've examined this year. To keep things reasonable, you'll restrict yourself to four-letter words.
Task.
You are free to design and implement the project as you see fit, as long as you use a java.util.TreeSet<E> for one aspect. Your documentation will include clear and full justifications for the structures and code decisions you made.
Finally, you may or may not need this but I found myself thinking about how to construct a balanced Binary Search Tree from an ordered list. A balanced tree optimizes the search time. I googled it and found some interesting suggestions here:
Create a Balanced Binary Tree from a Sorted Linked List
Manual Creation and Traversal. In this first assignment, you are to
incorporate TreeNode.java, exactly
as it appears on page 583 (get student files from Skylight),
into the development of a BST class
whose source code prototype appears below. The BST constructor
will use one statement to construct a tree with
four nodes. Complete the body of the traverse(TreeNode
node) method and use the driver
file, BSTTest.java to
test that the characters appear on the console in alphabetic order.
public class BST {
private TreeNode root;
/**
* Constructs a BST object encapsulating a binary search tree
* into 'root'. Hard codes the Character data: 'J', 'A', 'V', 'A'
* as the node values in one statement (manually).
*/
public BST() {
}
public void traverse() {
traverse(root);
}
private void traverse(TreeNode node) {
// add recursive code here so that all names are displayed to the console
}
}
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.
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.
Big Box Simulation 1:
Queue<Customer>.
An interesting ad on TV recently was a boast by Lowe's that if
a checkout line grows longer than 3 customers, they would 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 resources 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 is available.
In
this project, you are to run a one-day simulation of the checkout station,
monitoring and reporting the station's activities, and summarizing the results
at the end of the day. Here's the output from a
sample run.
Task. From the data given to you, customers (instances of the Customer class) arrive in random intervals of 1 to 4 minutes. Also, each customer is serviced in random integer intervals of 1 to 4 minutes. Obviously, the rates need to be balanced for the line length to remain manageable. If the average arrival time is larger than the average service rate, the queue will simply continue to grow. Even with balanced rates, randomness can still cause long lines.
Run a simulation for a 12-hour day (720 minutes). Here's a rough guideline for each minute of the day:
Maintain the necessary data so that at the end of the simulation, the program summarizes results for the following:
Final Recommendations,
Using the driver Simulation.java develop and submit the BigBox.java and Customer.java class files that will yield output similar to the above.
The Josephus Game A bidirectional Ring structure would be a useful container for many applications.
One such classic application is the so-called Josephus Flavius Game. A reasonable introduction to the context can be found at Cut The Knot.
Although our review of the Java Collections Framework in the previous chapter revealed the absence of a such a class, it's not hard to imagine how one could be constructed.
There is no such set of structures known as the JavaScript Collection Framework that I know of but, if there was, and it contained a Ring structure, it might look the one I demonstrate here.
Task.
Combination Lock. Since Java's LinkedList<E> class
maintains this data structure as a doubly-linked list, users can
traverse it forward and backward with the help of a ListIterator<E> object.
Create the project LockTest
and a driver that manipulates
the class, Lock,
defined by the 
UML specification below. You will need to complete the conditions
in each of the while statements in the driver for the project to work correctly.
With a correct implementation of the Lock class initialized with the combination, 21-32-34, your driver will generate the following output,
Gaskets:
Pascal's Carpet.
More secrets remain embedded within Pascal's Triangle.
Look at the Triangle again, focussing on groups of adjacent even numbers.
The resulting image should be surprisingly familiar.
Task.
Gaskets:
The Chaos Game. Familiarize yourself with this
recreational version of the Chaos Game.
Tasks.
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.
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.
 |
 |
The
Determinant of a Matrix.
Remember
the crossing pattern in the Shoelace
Formula for
determining the area of a polygon?
 |
Cramer's Rule.
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,
MODELING IN R2: 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 one or mor Sprite objects to the coordinates for the next frame within the updateScene() method. The loop in the run() method will then call the paintPanel() method in which you can retrieve your Sprite's updated coordinates to populate a Polygon object. This polygon object can be added to the scene through a call to Graphic2D's draw() method.
Here's the full Javadoc. I've created a very elementary example to the right. Considering your vast exposure to gaming animation, I know you'll take your effort to a whole new level.
Note. The classes in this project reflect a strong hierarchical design. I would expect your code to capitalize on the strength of this design; writing 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 R2: 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 R2: 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:
| J. Hinton | R. Beatty |
 |
 |
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
Maze Generation and Traversal. We're going to devote the next few classes to a group investigation of mazes: their generation algorithm and solution. This is another classic example of depth-first searching, similar to the recursive flood(x,y) method of last week's PaintBucket activity. In addition to exploring this algorithm, I want to draw your attention to the Processing language. This relatively new Java/C hybrid offers some amazing opportunities and, given your skills, you'll catch on very quickly. A subset of the Processing language provides the programming foundation for the Arduino platform.
Day 1 (Orientation with Interaction)
Day 2 (Porting Processing code into your Recursive Framework for maze generation)
Day 3 (Developing recursive traversal code for your maze)
This author provides a very good explanation of the thinking behind recursive strategy to solve the maze (and so many similar problems).
Reverse Polish Notation (RPN) Evaluator. The next enhancement to your Framework project 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.
Bracket Matching. The example
method on page 480 offers an iterative solution to confirm whether a String consists of correctly matched parentheses. It would be more impressive if
it were recursive.
Task.
Paint Bucket. 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 a region by implementing a depth-first recursive search for a border colour, painting pixels as you go. This is not how it's done in general but, for small areas, it serves as a useful introduction to depth-first recursive searching. For your regions, you can use one of the standard Graphics2D Shape classes ( ie, Rectangle2D, Ellipse2D, Arc2D, etc.) to create an interesting outline of your own design using piecewise Shape objects. Keep your outline small since the system stack has to store many return addresses to manage the depth of recursion.
Task.
Finally, don't forget to update your home page prior to submitting your source code.
Permutations. A binary decision tree designed to order three unique elements yields 3! or 6 leaves. The leaves can be interpreted as all possible permutations of the original elements and can easily be extended to n unique elements. In this exercise you will
display all permutations of the characters of a given input string.
Task. As the first entry into your Framework project, display all permutations of a string submitted by a user. For the string "ABC" the output shoud read,
BCA CBA CAB ACB BAC ABCInsight into a recursive design. For the string "ABC" there are 3! or 6 permutations. These appear as leaves in the tree below. At each recursive level with decreasing n, a loop is engaged that swaps the last character in the string with all others and swapping them back upon its return.
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. Create a project called Framework and
drop in this source code.
Tasks.
Towers of Hanoi. Legend has it that a Brahman monk
was charged with the task of moving 64 golden disks (of increasing
diameter from top to bottom) from one post to another
post. The two stipulations placed on the task were that only one disk
could be moved at a time, and no disk of greater diameter could rest on top
of one
with
of
lesser
diameter.
A third post is always available for temporary placement. Task.
You are display the moves necessary to complete the task. Code
the recursive method below into your NumericalMethods class,
/********************************************************************* * This method displays the specific moves necessary to move n rings * * from the source post to the destination post using a temporary * * post. The big-O of this task is O(?) * * @param n the number of disks * * @param src the name of the source post * * @param dst the name of the destination post * * @param tmp the name of the temporary post * *********************************************************************/ public static void showMoves(int n, char src, char dst, char tmp)
Add statements to your RecursiveClassics driver that will solicit
the number of disks to be moved and a subsequent call the showMoves method as
follows,
showMoves(n,'A','B','C');
For n=3, your output should read,
Move A to B Move A to C Move B to C Move A to B Move C to A Move C to B Move A to B
Binomial Theorem. A deep understanding
of
the
Binomial
Theorem
will
prove
useful to you in the months and years ahead. You'll undertake a computational
investigation
of the Binomial Theorem
in this two-part project. Note: For
our
purposes,
we'll
favour recursive strategies
over
iterative implementations strictly for the experience. Here's a reasonably
compact
definition of the Binomial Theorem,
 |
(BT-1) |
Application of (1) yields familiar binomial expansions,
 |
(BT-2) |
Part 1. Combinatorics. Consider the following definition from the field of Combinatorics,
 |
(BT-3) |
The left side of (3) is read as n choose r and represents the number of combinations of n one can make, choosing r items at a time (the last two expressions are different ways of expressing the same concept). As can be seen, the determination of this integer result relies on factorials. For example, assuming 5 students show up for class and I need to choose 2 students to go down to Bloor and pickup the sushi order I placed for lunch. How many ways can the pair of students be chosen? There are 10 such combinations as can be seen below.
 |
(BT-4) |
BinomialTheorem that exercises the
methods in your static NumericalMethods class below. Create
a static NumericalMethods class
and add the following methods, /*************************************************************************** * This method determines the value of n!, recursively * * Precondition: n>=0 * * Postcondition: the method returns the value of n! * * @param n the whole number for which the factorial is to be determined * **************************************************************************** public static int factorial(int n) /**************************************************************************** * This method returns the number of combinations that can be expected given * * n items, taken r at a time. This does not need to be recursive. * * Precondition: n>=0, 0<=r<=n * * Postcondition: the method returns the value of nCr * * @param n the number of items from which combinations are taken, n>=0 * * @param r the number of items taken, 0<=r<=n * ***************************************************************************** public static int choose(int n, int r)
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.
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)
/*************************************************************************** * This method returns the String representation of the r'th term of the * * Binomial Theorem of (a+b)^n * * Precondition: a, b the String equivalents of the binomial's terms * * n>=0, 0<=r<=n * * Postcondition:the method returns the String representation of the r'th * * term of the expansion of (a+b)^n. * * @param a the first term in the binomial (a+b) * * @param b the second term in the binomial (a+b) * * @param n the degree of the binomial expansion * * @param r the required term in the binomial expansion, 0<=r<=n * **************************************************************************** public String binomialTerm (String a, String b, int n, int r) /*************************************************************************** * This method returns the full binomial expansion of (a+b)^n as a String * * Precondition: a, b the String equivalents of the binomial's terms, n>=0 * * Postcondition:the method returns the String representation of the * * expansion of (a+b)^n * * @param a the first term in the binomial (a+b) * * @param b the second term in the binomial (a+b) * * @param n the degree of the binomial expansion * **************************************************************************** public String binomialExpansion (String a, String b, int n)
The Golden Ratio (φ) from a Continued Fraction. A compelling topic in pure mathematics
is Continued
Fractions. The essential idea is that the deeper the
evaluation of these expressions, the better the approximation is to
the ultimate irrational target, or what we prefer to call in Calculus, the limit.
The programmatic evaluation of these expressions is a good fit with your understanding
of recursive methods. Here is one example of the continued fraction leading to the
Golden Ratio.
 |
(GR-2) |
The limit of both (GR-2) and (GR-1) is φ.
Task. To your Recursive Project, implement the class GoldenRatio, the output of which will allow the viewer to confirm that both sequences (GR-1) and (GR-2) converge on φ. Maximize your use of recursive methods. Beyond the correct answer, evaluation of your submission will focus on the elements of good programming: method design, efficient implementation, clearly-labelled output and strong documentation. Finally, keep in mind the following,
The Golden Ratio (φ) from the Fibonacci Rectangle. In class we investigated
the relationship between the sequence defined by the quotients of successive
terms of the Fibonacci sequence
and the Golden Ratio, φ. This can be expressed as the process,
 |
(GR-1) |
| Fibonacci Rectangle | Square Construction with Compass and Straightedge |
|---|---|
 |
 |
Task.
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?public
int fib (int n) that
exercises this definition. What is the Big-O
of this
implementation?
Powers. It is virtually impossible to provide practical
programming solutions to a variety of complex problems without recursion.
As such, it is an indispensable programming
strategy.
Having said this, you'll have to decide when it's warranted.
Successful implementation of a recursive solution depends on your ability to
define a recursive solution on paper.
For example, the power function, xn can be defined iteratively (non-recursively) as,
Defined recursively, we could write,
 |
(P-1) |
From (1), the implementation is straightforward. Successful recursive solutions arise from the programmer being able to express a definition similar to (1) for each new problem, that includes both the general recursive substitution expression and a basis or stopping condition.
Tasks.
public int powerIterative(int x, int n) that
determines and returns the value of xn, iteratively. What is the Big-O of this implementation?public int powerRecursive(int x,
int n) that determines and returns the value of xn, recursively. What is the Big-O of this implementation?public int pow2(int n) that computes the value of 2n with
a running time of O(1).