Instructions

1. The examination is open book/notes.  You are allowed to consult any written materials available under the sun that was published or posted before the start of the exam, except code from your current Comp201 classmates.  If your code is based on materials that we did not provide you, just give us the appropriate references.
2. You are not allowed to discuss the exam in any way with anybody beside the instructors
of this course (i..e. Nguyen and Wong, but not the labbies) .
3. Do not post your questions on the newsgroup.  E-mail both of us, dxnguyen@rice.edu and swong@rice.edu, your questions instead. We will reply to you directly, and if deemed necessary, we will forward our reply to the newsgroup as well.  We will check our e-mail as often as we can to catch and respond to your questions
4. Write your code in the most object-oriented way possible, that is with the fewest number of control statements and no checking of the states and class types of the objects involved in any way.
5. We expect correct Java syntax that compiles without error.
6. You have 3 hours to do the regular questions on the exam.
7. Submission instruction: you must submit your exam in two ways.
   •  a hard copy with all answers in typewritten form, except perhaps diagrams (if any) which can be hand-drawn.  Be sure to print your name and sign the honor pledge.  You do not need to print out the supplied code unless you have modified it.
   • Zip your work together with your honor pledge (included in the provided code) and upload to the usual upload page under "Exam2". 
8. The deadline for submission is  Monday, April 5 2004 @ 10:00 AM.

• Download the provided code: Comp201Ex2.zip, which contains all the exam materials in a directory called Comp201Ex2.

• Put all the code for each problem in its respective subdirectory, e.g. Problem1, Problem2, etc.

• Your code is required to pass the supplied test code!

• Zip up the entire Comp210Ex2 directory including the filled-out Honor Code file and hand it in using the usual upload page.

PRINT THIS PAGE AND ALL YOUR CODE, WRITE AND SIGN YOUR HONOR PLEDGE AND BRING IT TO CLASS ON THE DUE DATE.

Problem 1: An Anonymous Frog (25 pts total)

Take the frog example in the State Design Pattern lecture and convert the code to use (an) anonymous inner class(es). Your code must meet the following criteria:

1. (2 pts) Be in the frog package and called BetterFrog
2. (5 pts) Must implement IFrog and have identical behavior as Frog including its State design pattern.
3. (3 pts) BetterFrog may contain only the public methods specified by IFrog.
4. (5 pts) Be completely contained within the single public class BetterFrog. Nested and inner classes comply with this directive.
5. (5 pts) Use a minimum of passed input variables.
6. (5 pts) Use a minimum number of named classes of any sort.

The IFrog is in the supplied code which includes the test code your BetterFrog must pass.

Suggestion: Write and test your best initial attempt at the problem. Then carefully review your code and ask if you can modify it to better meet the above criteria, especially #5 and #6. Modify your code and review it again. Repeat this process until your code is perfect!

Problem 2: Lists of Lists (20 pts total)

Consider an IList whose first (if it has one) is an IList. That is, consider a list that contains lists.  Below is an example of such a list.

((a , b, c), (), (d, e))

Write an IListAlgo visitor, called CountAll,  that will count all the elements in all the contained lists of a list of lists. An Integer object should be returned. For example, for the above list, Integer(5) should be returned.

Your code must conform to the following specifications:

1. Be in the listFW.visitor package.
2. Be a singleton
3. Have no non-static fields
4. May use either forward or reverse accumulation
5. Any helpers must be implemented using anonymous inner classes. No external, nested or named inner classes allowed.

The listFW package has been supplied, including the test code that your code is required to pass.

Extra-Credit:  5 points extra-credit will be given to a tail recursive visitor.

Problem 3: The Model-View-Controller Design Pattern (25 pts total)

In general, the user interface of a system is a variant with respect to the actual computing process that goes on behind it. Examples of this are the "skins" on various software audio/video players and the configurable "look-and-feels" found in Linux and other systems. Likewise, the actual processing code can vary independently from the user interface, such as the different implementations of Mozilla on different operating system platform which all have the same user interface.

To decouple the "model" (where the actual processing takes place) and the "view" (the user interface), we employ what is called the "Model-View-Controller" or "MVC" design pattern. This design pattern uses "adapter" objects to connect the model and the view together, creating an indirection layer between them which enables them to vary separately. These adapters are part of the Adapter design pattern (for additional, optional reading, see the Java Resources web page). The adapters "translate" calls to their methods to method calls on their target objects, which may be quite different.

The job of the "controller" is to instantiate all the pieces of the application and tie them all together into a fully operational system. Since the view only talks to its adapters and the model only talks to its adapters, neither the model nor the view know anything about each other. The controller is the only object that knows about all the objects in the system. The controller does not do any processing of its own however. All it does is to set up the communications between the model and the view (after instantiating them and their adapters).

Consider the follow simplified MVC system (full documentation here, click here to see the demo):

The view above (MyView) does not ever talk directly to the model (MyModel). They are not even in the same package. Instead, the view has specified that when it talks to the model, it wants to see a very particular interface, namely, IModelAdapter. IModelAdapter has the one method, getResponseTo, that the view needs to communicate with the rest of the system. Since IModelAdapter is part of the view's specification, it is located in the view package. Likewise, the model has an interface which it has specified to communicate with the view, IViewAdapter which contains the method the model needs, display.

Notice that the method on IModelAdapter does not correspond, at least in name, to any method actually on MyModel. This is because the specifications of the view are determined independently from the specifications of the model, based solely on the needs of the view, not what is supplied by the model. Likewise the same is true looking the other way, we see that the method of IViewAdapter is not the same as any of the methods on MyView.

This is where the controller, AppController, comes in. Since the view and the model are decoupled and thus know nothing about each other's methods, the controller is the one piece of the system charged with actually knowing all this information. The controller thus represents the particular configuration of the system that pairs this particular view with this particular model. If we switch models or views, we would need to write a new controller. But that's all that would change. Any particular model or view is independent of the corresponding view or model that it attached to in the end.

The controller's job is to create the proper instances of adapters needed to connect that specific model and view together. Anonymous inner classes are beautiful tools for this job because they enable the controller to create a "custom" one-time-use class (instance actually) that is perfect for attaching a particular model to a particular view. For instance, above, the view wants to call the IModelAdapte.getResponseTo method. MyView has no idea that the model wants to take the given string and construct a silly quote from it. The view only knows that it is supposed to give the model the text from a text field and put whatever comes back up on a text area. The controller, on the other hand, knows what the model is trying to do and what the view is trying to do. Thus the controller can create an anonymous inner class instance of IModelAdapter whose getResponseTo method calls the MyModel.getQuoteFrom method and returns its result. Similarly, it can construct an IViewAdapter instance that calls the appropriate method on the MyView object. Once the two adapters are instantiated, the controller can install them into their respective model or view objects. Since both MyView and MyModel take their respective adapters in their constructors, the instantiation of the model's (or view's) adapter and the model (or view) can be written in a single line of code.

In the code that is provided, you must write 3 missing sections of code to complete its functionality (all clearly marked in the code itself).

You may not modify any sections of code other than what is clearly specified.

1. (5 pts) In MyView.initialize(): Add an ActionListener to _btn so that when it is clicked, it calls _modelAdapt's one method using the text field's text as its input. The return value should be used to set the text area's text. Only a single Java statement is required. Any method declared should have only a single line of code. You may add modifiers as necessary to the local variables.
2. (10 pts) In AppController.init(): Instantiate the MyView object _view with a title for its frame, and an IModelAdapter whose sole method calls the model's getQuoteFrom method with the supplied input.
3. (10 pts) In AppController.init(): Instantiate the MyModel object _model with an IViewAdapter whose one method will set the view's bottom label to the given string.

Problem 4: Selection Sorting a LRStruct (15 pts total)

Consider a LRStruct filled with Integers. How can we sort the values in the LRStruct without creating a new list? That is, can we write an algorithm on a LRStruct that will mutate the list so that all the Integers will end up in order?

Let's examine the following "selection sort" algorithm:

1. When the list is empty, you are done. Return the list.
2. When the list is non-empty:
   1. Remove the minimum element of the list.
   2. Insert the minimum into the front of the list
   3. Sort the rest the as-yet unsorted list.
   4. Return the whole, now sorted, list.

Convince yourself that this will indeed sort the list.

We already have an visitor that removes the minimum value in a LRStruct of Integers: .RemMinLRS

Write an IAlgo visitor called lrs.visitor.SelectionSortLRS that uses the above algorithm.

The lrs package, including RemMinLRS and the test code that your code is required to pass has been provided.

Problem 5: Insertion Sorting a LRStruct (15 pts total)

Let's consider another technique for sorting a list, called "insertion sort":

1. When the list is empty, you are done. Return the list.
2. When the list is non-empty:
   1. Sort the rest of the list first.
   2. Remove the first element of the list.
   3. Do an ordered insertion of the just-removed first into what was the rest of the list.
   4. Return the whole, now sorted, list.

Convince yourself that this will indeed sort the list.

We already have an visitor that does an ordered insertion into a LRStruct of Integers: .InsertInOrdeLRS

Write an IAlgo visitor called lrs.visitor.InsertionSortLRS that uses the above algorithm.

The lrs package, including InsertInOrderLRS and the test code that your code is required to pass has been provided.

Last Revised Thursday, 03-Jun-2010 09:50:18 CDT

©2004 Stephen Wong and Dung Nguyen