2009 Final Exam: Taylor Approximations to Transcendental Functions.

Student	Link to Taylor Applet
Chris Black	http://mail.rsgc.on.ca/~cblack/Taylor/index.html
Rothman Ng	http://mail.rsgc.on.ca/~rng/Taylor/index.html
Severin Tsuji	http://mail.rsgc.on.ca/~stsuji/Taylor/index.html
Matt Weldon	http://mail.rsgc.on.ca/~mweldon/Taylor/index.html

(C++) Quadrature. Review this summary of Numerical Integration.

You are asked to write a C++ program whose main function determines approximations to the area between f(x)=sin x and the x axis over the requested partition and number of interval. The main function will make calls to the midpoint(a,b,n) and trapezoid(a,b,n) functions to produce output matching the following screen capture.

Priority Queues: Bin Packing. A (somewhat) practical assignment based on priority queues involves assigning files to storage media. Here's the description on the website for Princeton's COS 226 course,

• 2006 version
• 2005 version

Task. Develop the project, WorstFit, and drop in this WorstFit.java driver. You are to complete the allocate(int fileSize) method that will attempt to add the sample file sizes read from the input file input20.txt, to the Disk object at the top of the maxPQ maximum heap object. If this Disk does not have sufficient free space to accomodate the request, instantiate another Disk, decreasing the available space by the amount requested and add the Disk to the maxPQ. Other input files can be taken from Princeton's ftp support site. The MaxHeapPriorityQueue class is a modification of the HeapPriorityQueue class you've been working with in the last couple of assignments. You are to submit WorstFit.java, Disk.java and MaxHeapPriorityQueue.java by the deadline. The Disk class is defined by the UML diagram below.

'In Place' Heapsort. If an array needs to be sorted, we can simply dump the values, one at a time, into our HeapPriorityQueue structure and pull them out again. For obvious reasons this is referred to as a Heapsort and it's not too difficult to see it fits in well with the other O(nlogn) sorts (Mergesort and Quicksort) The only down side of this seems to be the doubling of required memory. Page 632 outlines an alternative algorithm for an 'In Place' Heapsort (IPHS) that doesn't require the additional memory. Task. After reading page 632 and viewing the IPHS animation you are asked to develop the Heapsort class. As a starting point, create a project entitled IPHS and drop in this driver. Submit Heapsort.java by the deadline.

HeapPriorityQueue: reheapUp and reheapDown. Pages 628 through 631 in our textbook describe code for maintaining a simple DIY Priority Queue based on a non-linked Heap structure. The author asks you to complete the reheapUp() and reheapDown() methods. Task. Create a project called HeapPQTest and download this driver. Add his partially completed HeapPriorityQueue.java class file to your project. Implement efficient reheapUp(),reheapDown() and toString() methods. Add statments to the driver that will parallel his countries example on page 630, printing out the contents of the heap after Argentina has been successfully removed.

GIF Decoder. GIF (Graphics Interchange Format) files are one of the primary graphics formats for the web (along with JPG and PNG). Images that contain large areas of a common colour are particularly well-suited for its (maximum) 256-colour palette. The internal structure of the format, along with the compression algorithm were published in 1987 by Compuserve. This document provides the details of the GIF87 format. Two years later, Compuserve added animation and transparency features and published the details of the GIF89a format.

The above documents can be intimidating, so let's begin our study of the structure of here. As you can see, the file is composed of sub-blocks [Header, Screen Descriptor, Image Descriptor, and Control Extension, to name a few]. Here's a byte-level analysis of an example gif file in which the sub-blocks can be seen in more detail. The byte-level contents of the GIF file, JavaThumb.gif that appears to the right can be examined here.

Step 1. It would seem appropriate to develop classes that closely match the sub-blocks of the file. From the driver, GIFTest.java, the names of these classes and their implementation can be determined. Add the GIF file JavaThumb.gif to the your project. Each of you are asked to develop a class as assigned, implementing the public init(FileInputStream in) and toString() methods. You can get an idea of what your toString() method should return by examining the worling applet below. Here's an example of the output for JavaThumb.gif we'd like to see soon after we blend your classes together.

Step 2. Assemble and implement all student classes under the control of the text version driver, GIFTest.java.

Step 3. The live applet below reads each of three GIF files (first.gif, second.gif, and crumple.gif) and presents the details of the file in its top left panel, the palette in the bottom left panel and a decoded rendering of the image in the right panel . You are to duplicate this applet. Create a project called, GIFDecoder, and drop in this applet driver, and JavaThumb.gif in its/bin folder. It can be seen that the driver instantiates a GIF object that we must provide. Drop in the class file, GIF.java, and implement it under the control of the applet driver, GIFDecoder.java, so that the details and palette panels are populated similar to applet below. Modify your classes to set the appropriate global instance fields so that the entire class can access their values.

Step 4. In this final segment, you are to add the code below to the files previously developed classes (posted in our Subject Conference) to render the GIF image in the previewPane of your applet. Add the code below at the end of the paint() method of your GIFDecoder driver.

// draw the preview
g2D = (Graphics2D) previewPane.getGraphics();
bi = (BufferedImage) createImage(gif.getWidth(), gif.getHeight());
SampleModel sm = bi.getSampleModel();
int[] imageBuffer = gif.getImageBuffer();

DataBuffer db = new DataBufferInt(imageBuffer, imageBuffer.length);
Raster raster = Raster.createRaster(sm, db, null);
bi.setData(raster);
g2D.drawImage(bi, 0, 0, this); 
fileDefined = false;

As you can see, the only issue Eclipse has with this code fragment is access to the gif object's getImageBuffer() method. This buffer holds the decompressed image data that will be loaded into the previewPane panel. To support this process, add the following declarations to your GIF class.

// LZW decoder working tools ImageData imageData; static short[] prefix; static byte[] suffix; static byte[] pixelStack; static byte[] pixels; static int[] imageBuffer; // max decoder pixel stack size static final int MaxStackSize = 4096;

Here Eclipse indicates it wants an ImageData class. Add the inner classes, Data and its extended subclass, ImageData, that will perform the implementation of the LZW decompression. To your GIF constructor, we must instantiate the imageBuffer array, so, after npix = width * height, add the statement,

imageBuffer = new int[npix];

Now, add the GIF method(),

public int[] getImageBuffer() { return imageBuffer; }

and add the code that initiates the decryption. After the statement, image.init(in), add,

imageData = new ImageData(); imageData.init(in); Data data = imageData; while (data.data != null) { data = new Data(); data.init(in); }

Almost done! Add the following statement to GIF's toString() method to supply the GIFDecoder's details panel with further information on the GIF file.

ret += imageData.toString();

Undertake these steps on your own computer and mount the applet by the deadline so that the following links work!

Student	Link to GIFDecoder Applet
Chris Black	http://mail.rsgc.on.ca/~cblack/GIFDecoder/index.html
Rothman Ng	http://mail.rsgc.on.ca/~rng/GIFDecoder/index.html
Severin Tsuji	http://mail.rsgc.on.ca/~stsuji/GIFDecoder/index.html
Matt Weldon	http://mail.rsgc.on.ca/~mweldon/GIFDecoder/index.html

iTunes. The purpose of this assignment is to become familiar with the Java Collection Framework's HashTable <K,V> class. The applet below provides a crude rendering of my iTunes library (Listeners have not been attached to the menu items). Only five fields for each record in the library are presented in the Applet Window (name, artist, time, album and genre). Clicking on a record however results in all 27 fields being displayed in the Java Console window using System.out.println(). The data for each record is stored in a HashTable<Key,Value> with the Key composed of the concatenated name and artist fields and the entire set of fields stored as the Value in the form of a Record object.

Task. Create an iTunes project and drop in the driver, iTunes.java. No modification of this class is required. Add the Playlist.java class definition to the project. When you're ready to test, add the music.txt file to your iTunes/bin folder. Add statements and javadoc to the Playlist and inner Record classes to allow your Applet to function as above. When complete, mount your applet so that the link below works and submit your source code to handin by the deadline. Look at the source code of the above applet to see how to add the playlist parameter.

Student	Link to iTunes Applet
Chris Black	http://mail.rsgc.on.ca/~cblack/iTunes/index.html
Rothman Ng	http://mail.rsgc.on.ca/~rng/iTunes/index.html
Severin Tsuji	http://mail.rsgc.on.ca/~stsuji/iTunes/index.html
Matt Weldon	http://mail.rsgc.on.ca/~mweldon/iTunes/index.html

Be sure to open the Eclipse Run Dialog and set the Applet parameters as shown below.

TreeMap: StudentMap. By completing this assignment you will gain familiarity with java.util's TreeMap Collection.

Task. The plain text file, Student.txt, contains course enrolment data for the 218 students in Grades 9 through 11. Open this file in Excel and look at its contents. Use your AccountTest application to generate 218 unique 5-digit student ID numbers, and add these String IDs to the worksheet as a new Column A. Save this modified worksheet as the new Student.txt (tab-delimited text file). Add statements to the driver, StudentMap.java, (current output depicted below) that will,

1. Instantiate a new Student object for each record in the plain text file (Student.txt). One recommendation would be to separate the Student ID from the input String (use this as the Key) and pass the balance of the String to the Student constructor as the Value. The constructor can parse the String data into its constituent parts (grade, name, courses) using String's split(delimiter) method. Maintain an efficient, internal collection of courses.
2. Permit queries to your map (database), by allowing users to submit an ID, for which your application will display the student name and the courses in which he is enrolled. For invalid IDs, display No Record Found.
3. Permit a second type of query that allows the user to submit a course code for which your application responds by displaying the names of all students enrolled in the course. For invalid course codes, display, Invalid Course Code.

TreeSet: AccountTest. There is a practical need to generate unique account numbers for clients over a range of values.

Develop the class, Account, as defined by adjacent UML diagram. Start with the driver, AccountTest.java and add statements that will generate the output contained in AccountTest.txt. You can infer from the output, the logic required.

The idea is to populate a TreeSet<Account> with the requested number Accounts constructed with unique, n-digit integers (converted to Strings).

	private boolean contains(TreeNode node, Object value)
	public boolean remove(Object value)
	private TreeNode remove(TreeNode node, Object value) {

	public TreeNode removeRoot(TreeNode root)

	public Iterator<Object> iterator() {
	  return new MyTreeSetIterator(root);
	}

This requires the creation of the private inner class with signature,

private class MyTreeSetIterator implements Iterator<Object>

that performs an inorder traversal of your BST. As recommended on page 591, you should use a Stack<TreeNode> to assist you within the MyTreeSetIterator class. Adding the following statements to your driver,

    //Remove...
    System.out.printf("Prior to the removal of J: %s.\n",bst); 
    bst.remove('J');
    System.out.printf("After to the removal of J: %s.\n",bst); 
    //Iterator...
    System.out.print("Traversal with an iterator: ");
    for (Object obj : bst)
      System.out.print(obj + " ");
    System.out.println();

will produce the following output.

Task. Create a new BST object by merging two existing ones. Review this documentation and the read pp. 586-588 where the author discusses a Do-It-Yourself BST. In particular, look at the add method on Page 588.

Adding the following lines to your BSTTest.java driver,

    // Merge and Confirm
    BST bst3 = bst.merge(bst2);
    
    System.out.printf("The merged tree is: %s.\n", bst3);
    System.out.printf("The encoded tree is: %s.\n", bst3.getCode());
 
    //Confirm encoding
    BST bst4 = new BST(bst3.getCode());
    System.out.printf("Confirming the encoding: %s.\n",bst4);

results in the following output,

  /**
   * Constructs a BST object from the parameter containing the  
   * encoded Binary Search Tree.
   * @param code the encoded binary search tree
   */
  public BST(String code) {
    this.code = code;
    root = parse();
  }

This constructor calls the iterative method parse(),

private TreeNode parse() {
	Stack<TreeNode> stk = new Stack<TreeNode>();

}

that uses a local java.util.Stack<TreeNode> object to assist with the construction of the BST. Adding the following statements to your current driver,

    // From an Encoded String
    String code = "C[/,O[M[E[/,/],/],P[/,U[T[R[/,/],/],/]]]]";
    System.out.println(code);
    BST bst2 = new BST(code);
    System.out.println(bst2.getCode());
    System.out.println(bst2);

will yield the following output.

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) {
    if (node != null) {
	  // add code here so that all names are displayed to the console
    }
  }
}

14. Plant Architecture: Bracketed L-Systems A fascinating algorithm for rendering images of plants involves perpetuating a string of coded characters that are, in turn, interpeted by a drawing pen or turtle with the help of a Stack. Two dimensional examples created by the class of 2006-7 appear at the right. Here's a 3D example. The orginal idea is credited to Astrid Lindenmayer, who proposed, in 1968, "an axiomatic theory of development" for plant structure. Hence the name L-Systems.

In this in-class exercise, you are asked to supply the code necessary to reproduce the images described on Page 25, using the driver Garden.java. Add the missing code to produce the graphic at the top right. An original plant of your own design would be most welcome.

Severin Tsuji	Chris Black	Matt Weldon	Rothman Ng

L-Systems. A fascinating class of fractals that challenges the conventional notion of dimension caused quite a stir at the beginning of the 20th Century. The Quadratic Koch Island pictured to the right was one such monster (as they were dubbed) from that time. The iterative algorithm for generating these images is defined by an initiator (axiom) and one or more generators (production rules) used to propagate the shape over successive generations. In this assignment, we'll use Strings to define the axiom and the set of production rules for the image. Iterative replacement of the production rules within the axiom grows the image. The object is rendered on a JPanel through the manipulation of a Graphics2D commands characters in the encoded String as drawing instructions.

Task. Create a project entitled, LSystems and drop in the driver, LSystems.java. Familiarize yourself with the documentation for the project. There are three areas of the code that require your attention: the body of the constructor for both the Monster and Cage classes, as well the paintComponent() method of the Cage class. In the Cage constructor, provide instantiation code for the 11 monsters defined in Figures 1.7 to 1.9 found on pp. 9-10 of the handout, commenting out all but Figure 1.7 a). Also, feel free to add a monster of your own design/creation or one you've googled. Submit your updated LSystems.java to handin by the deadline. Here are Rothman's efforts...

Figure 1.9 a)	Figure 1.9 b)	Figure 1.9 c)	Figure 1.9 d)
Tsuji Original	Black Original	Weldon Original	Ng Original

Supermarket. (There are specialized languages for running simulations. We can employ Java to get a feel for the value of this kind of exercise.) As an expert in the field of Operations Research, the manager of Freda's Fine Foods (an instance of a Supermarket Class) has asked for your help in determining whether the anticipated benefit of a planned sale will be offset by customer dissatisfaction with longer than normal delays due to lineups.

A check-out line is a FIFO structure, modelled by a queue (LinkedList<E>) object. 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 line lengths 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.

Task. Run a simulation for a 12-hour day (720 minutes). For each minute of the day:

• If the next customer arrives,
• Say so
• Enqueue (add) the customer
• Schedule the arrival of the next customer;
• If service was completed for the last customer,
• Say so
• Dequeue (remove) next customer to be serviced (if there is one)
• Determine customer's service completion time (random integer from 1 to 4 added to the current time).

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

• The maximum number of customers in the queue at any time.
• The maximum wait time any one customer experiences.
• The planned sale is expected to reduce the arrival time interval from 1-to-4 minutes to 1-to-3 minutes. Determine the results of a) and b) under this reduced timeframe.

Output should look similar to the following,

Run the simulation 10 times for each arrival interval and use the data to complete this Excel workbook. Submit the workbook along with your code.

Final Recommendations,

• Don't concern yourself with the Statistics until the servicing of customers has been completed.
• When the store closes, there may be customers in the queue.
• Develop your logic over a shorter day.
• Use of constants for the upper bound of the arrival and servicing interval will make it easy to change later.

Using the driver SupermarketTest.java develop and submit the Supermarket.java and Customer.java class files that will yield output similar to the above along with a completed Supemarket.xls file with your recommendation for whether the sale should take place.

Reverse Polish Notation. In this assignment, you are to evaluate a simple arithmetic expression, supplied in postfix notation (also called Reverse Polish Notation). For example, consider the standard infix notation, 2*(3+4). Written as an RPN expression, it would appear as 234+*.

Task. Develop the class, Expression, that can be used with the driver, ExpressionTest.java to generate the output below.

Algorithm to Evaluate RPN Expressions (taken from C++, An Introduction to Data Structures, Larry Nyhoff)

/**
* Receive: An RPN expression
* Return: The value of the RPN expression
* Note: Uses a stack to store operands.
*/
1. Initialize an empty stack
2. Repeat the following until the end of the expression is encountered:
   a. Get the next token (constant, variable, arithmetic operator) in the RPN expression
  b. If the token is an operand, push it onto the stack. If it is an operator, then do the following:
   i. Pop the two values off the stack. (if the stack does not contain two items, an error due to a malformed RPN expression has occurred and the evaluation is terminated.)
   ii. Apply the operator to these two values.
   iii. Push the resulting value back onto the stack.
3. When the end of the expression is encountered, its value is on top of the stack (and, in fact, must be the only value in the stack).

MODELING IN R²: PART 3. Animation2D . In this final instalment, we integrate the foundation classes you have developed over the last 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 only your Animation2D and Sprite classes and a video of your animation (you could use CamStudio) to an email to handin with the Subject: Animation2D by the deadline. I will use your supporting classes submitted earlier. Here are some samples from previous years: Select one... 2008-2009 2007-2008 2006-2007

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.

MyMap (Java in-class). Create the generic class, MyMap<K,V>, that encapsulates a LinkedList<Node> (Node is a private inner class) it uses as a map. Your class will provide implementations of the first six methods listed in Figure 19-18 on page 488. Test with the driver MyMapTest.java. Here's a video of the run.

MySet (Java in-class). Create the generic class, MySet<E>, that encapsulates a LinkedList<E> it uses as a set. Your class will provide implementations of the first five methods listed in Figure 19-15 on page 485. Test with the driver, mySetTest.java.

Zellers' Congruence (Java Powercode). Code and confirm the algorithm for Zeller's Congruence (look halfway down) .

MyQueue (Java in-class). Create the generic class, MyQueue<E>, that encapsulates a LinkedList<E> it uses as a queue. Your class will provide implementations of the four methods listed in Figure 19-12 on page 481. Write the driver, myQueueTest.java that will exercise the four methods.

Bracket Matching (Java-in class). Create a project entitled Brackets and download the file Brackets.java as the driver. Using the existing predicate methods, complete the body of the recursive method,

so the output yields,

Algorithm. The approach involves a push of the open (left) brackets onto a Stack as they are encountered. An occurrence of a close (right) brackets signals a pop (if possible) the top element from the Stack and a comparison to confirm it is a match. If it is, keep processing. The brackets match if the end of the String is encountered and there a no elements on the Stack.

Run Length Encoding. Now that we have a good understanding of the internal machinery required to manage a linearly-linked list and experience with manipulating the JCF's generic LinkedList<E> class, we can put our skill to work in the context of an interesting algorithm.

GIF files are particularly well-suited for compressing Clip Art graphics because these images typically contain regions of pixels of the same colour. Similarly DNA sequences contain runs of the same protein. This opens the possibility of implementing a compression algorithm to shorten our String. (Using linked lists is not all that practical in the general case since the pointer to the next node in the list alone, requires as additional 8 bytes)

Task. Using the driver, RLETest.java, develop the class, RLE.java, that accepts a String of characters with numerous repeating characters and compresses it into a LinkedList<Byte> structure using a simple Run Length Encoding strategy defined as follows,

• If the run length is in the interval from [2,127], add two Bytes to the LinkedList: the run count, followed by the byte value of the character, or,
• If the run length is 1, add a single Byte to your LinkedList with a value equal to the negative of the byte value of the character.

RLE's decode() method will use a ListIterator<E> to navigate the list in reproducing the original producing the original String. Sample Run.

(Java) 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 object. Using the driver, LockTest.java, develop the class file Lock.java, defined by the UML specification below.

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

7. (C++) Credit Card Validation: Check Digits. Read this page on Credit Card Validation - Check Digits. Develop the C++ program, verify.cpp, whose .exe can be run at the command prompt, accepting a credit card number as a command line parameter. The program will echo the card number and confirm whether it is a valid VISA number or not.

6. (C++) Address MUNG. Explore C++'s String handling capabilities. Read this page on Address MUNGing. Using one of the example MUNGs or one of your own design, develop the C++ program, mung.cpp, that first displays an explanation of your MUNG strategy, then solicits a MUNGed email address from the user, edits out the MUNG, and finishes by displaying the true email address.

4. (C++) One-Line Animation. Develop the C++ program, animate.cpp, using loops, one or more characters from the Extended ASCII table (128-255) and the \r escape sequence to create an interesting one-line animation.

2. (C++) Days. Write a C++ program, days.cpp, that calculates the number of hours of your life that you have spent sleeping. Assume that you sleep 8 hours each night. To simplify the problem, assume that there are always 30 days in each month, and 365 days in each year. Restrict yourself to arithmetic expressions and assignment statements for your determinations. Do not use conditional statements. The program output should look similar to,

Enter your birthdate (using numbers for months)

Month: 9
Day: 27
Year: 1990

Enter today's date (using numbers for months)

Month: 9
Day: 12
Year: 2007

You have been alive for 6190 days.
You have slept for 49520 hours.