Review

Exam Description

My exams tend to have three to six questions. They are closed book, closed notes. I prefer to ask questions with objective answers. Mainly, I will ask you to draw diagrams, describe what happens when a piece of code is executed, and to write code. You will have the entire class period to finish the exam. Midterms emphasize the material covered since the last midterm. Final exams are comprehensive. The exam questions are mostly based on the homework, text, and lectures.

Study Suggestions

There are three levels of understanding. From lowest to highest they are:

Level 1: Ability to understand explanations of others
Level 2: Ability to solve new problems
Level 3: Ability to explain material to others

You need to attain level 2 in order to pass the exam. This means you have read and understood your notes, reviewed your homework, and reviewed previous exams (level 1).

Beyond that, you have invented and solved variations of the problems discussed in class. (Level 2).

To attain Level 3, form a study group and take turns explaining the material to each other. If someone in the group gives a lazy or bad explanation, let him have it!

I tend to give away a lot of information in the review session.

Topics

Patterns

Sample Questions

Principles

(a) What is the Liskov Substitution Principle? Give examples of how it can be violated.

(b) What is the Open-Closed Principle?

Metrics

Measuring Cohesion

Recall that the Modularity Principle suggests that a system be decomposed into cohesive, loosely coupled modules. Chidamber & Kemerer provide a metric for measuring a module's lack of cohesion (LCOM1). There are several minor improvements on this metric (LCOM2 and LCOM3).

LCOM1

In a method coupling graph for a class C-- MCG(C)-- nodes are methods. Two nodes are connected by an undirected edge if they both reference the same field. In fact, the edge can be labeled by the number of common attributes the methods reference.

(a) Draw MCG(Test) where Test is the following class:

class Test {
   int a, x, y, z;
   void m1() {
      System.out.println(x);
      System.out.println(y);
   }
   void m2() {
      System.out.println(y);
      System.out.println(z);
   }
   void m3() {
      System.out.println(x);
      System.out.println(z);
   }
   void m4() {
      System.out.println(a);
   }
   void m5() {
      System.out.println(a);
   }
}

Recall that

LCOM1(C) = choose(n, 2) - e

where:

n = # of nodes in MCG(C) = # of methods in C
choose(n, 2) = n * (n - 1) / 2
e = # of edges in MCG(C)

(b) Compute LCOM1(Test).

(d) Under what conditions does LCOM1(C) = 0?

LCOM2 and LCOM3

In a method-attribute graph for a class C-- MAG(C)-- nodes are methods and attributes (fields). A directed edge connects a method node to an attribute node if the method references the attribute.

(e) Draw MAG(Test).

Recall that

LCOM2(C) = 1 - e/(n * a)

where:

e = # of edges in MAG(C)
n = # of methods
a = # of attributes

(f) Compute LCOM2(Test).

Recall:

LCOM3(C) = n/(n - 1) * LCOM2(C) = (n - e/a)/(n - 1)

(g) Compute LCOM3(Test).

(h) Prove 0 <= LCOM2(C) <= 1

(i) Prove 0 <= LCOM3(C) <= 2

(j) What action would you recommend if LCOM3(C) > 1?

Class-Level Dependencies

In the dependency graph for a system S-- DG(S)-- nodes are classes. An arrow runs from class A to class B if A references B (implicitly or explicitly). We say that A is the client and B is the provider.

For a particular class C in DG(S):

Ca(C) = # of afferent (arriving) arrows for C = # of clients of C
Ce(C) = # of efferent (exiting) arrows for C = # of providers of C

C is responsible if it has many clients. C is stable if it doesn't have many providers. Chidamber & Kemerer refer to Ce(C) as CBO(C). Thus, a large value of CBO(C) would indicate a high degree of instability.

(a) Compute Ca(C) and Ce(C) for each class C in S, where S is the following system:

Coupling Degree

The coupling degree is a measure of the intimacy of a dependency between two classes. Based on Hitz & Montazeri paper we proposed the following measure of coupling degree:

couplingDegree(A, B) =
(instability(B) + access(A, B) + scope(A, B))/12

(b) Taking CBO(C) as a measure of instability, compute the coupling degree for each pair of classes in S.

Hints:

Assume access(A, B) attains its maximum value, where:

access(A, B) <= 3 if there is an association from A to B
access(A, B) = 1 if A references an abstract superclass of B
access(A, B) <= 4 if A extends B

if A depends on B assume scope(A, B) = 3

(c) The denominator, 12, assumed instability(C) <= 4. How can you adjust this so that the coupling degree is between 0 and 1?

(d) The Law of Demeter (a.k.a. The Principle of Least Knowledge) frowns upon certain kinds of implicit references between classes. Give an example of such a reference. How would you eliminate such a reference? How would a tool detect such a reference? Give an example of an implicit reference that isn't frowned upon by Demeter.

(e) Class A depends on class B if some change to B forces a change to A. Clearly A depends on B if A references B (explicitly or implicitly). How could A depend on B if it didn't reference B?

(f) List the ways class A can explicitly reference class B. Give an example of each.

Stability & Abstraction

Recall that a collaboration is a collection of classes that work together to solve a problem.

Recall that martin takes the instability of a collaboration to be:

instability(K) = Ce(K)/(Ce(K) + Ca(K)

Since

0 <= instability(K) <= 1

we can also define:

stability(K) = 1 - instability(K) = Ca(K)/(Ce(K) + Ca(K))

Note: perhaps a better term than stability is responsibility.

Note: a high degree of instability implies more providers than clients. In this case K is more vulnerable to change since any change to a provider may cause a change to K. It also implies a low degree of responsibility since there aren't too many clients.

(g) In system S assume K = {B, D, E} is a collaboration. Compute instability(K).

(h) Let's extend this definition of instability to classes. Compute the stability of every class C in S. How does this compare to CBO(C)?

The abstractness of a collaboration is simply the ratio of abstract classes to classes.

(i) Compute abstractness(K), abstractness(S).

The Dependency Inversion Principle (DIP) recommends depending on abstract classes rather than concrete classes. If we follow this principle, then the degree of abstractness of a collaboration should be close to its stability. Martin measures how far apart abstractness and stability are using the

dist(K) = |A + I - 1|/2

where

I = instability(K)
A = abstractness(K)]

Using our definition of stability we have:

stability(K) = S = 1 - I

and so our formula simplifies to this:

dist(K) = |A - S|/2

(j) Compute dist(K).

Cyclatomic Complexity

(k) Implement a method or function that counts the number of even entries in an mxn matrix. Compute the cyclatomic complexity for this method.

Patterns

Example: Wines and Vintners

(a) Model the following concepts with a UML class diagram using the Bridge pattern:

Wine
   White Wine
      Chardonnay
         Charles Shaw Chardonnay
         Paul Masson Chardonnay
      Riesling
         Paul Masson Riesling
   Red Wine
      Cabernet
         Charles Shaw Cabernet
         Paul Masson Cabernet
      Merlot
         Charles Shaw Merlot
         Paul Masson Merlot

(b) In the previous example the Bridge pattern was used to separate grapes and vintners into two hierarchies connected at the top by a bridge. Every instance of the Wine class (or subclass) will have a pointer to some instance of the Vintner interface. This pointer will be initialized when the instance is created. How can we use the Factory Method pattern to avoid an explicit reference to the specific Vintner in the Wine class?

(c) Wines have attributes such as color, scent, and body. These attributes are derived in part from the type of grape and in part from the way the wine was crushed, fermented, and aged. Toward this end you decide to put crush, ferment, and age methods in your vintner interface. Unfortunately, Paul Masson doesn't use this terminology. Instead, they use squash, makeAlcoholic, and store. Charles Krug uses crush, sugarToAlcohol, and makeOld. How could you use the Adapter pattern to resolve the differences in terminology?

(d) Sketch the code for this design.

(e) A wine cellar keeps bottles of each type of wine in stock: Chardonnay, Riesling, Cabernet, and Merlot. How could you use the AbstractFactory pattern to decouple the wine cellar from the vintners that supply the wine?

(f) There are two types of wine: varietals and blends. A varietal is made from one type of grape (75% actually) while a blend is a mixture of varietals and perhaps even other blends. How can you use the Composite pattern to model this?

Example: Cars and Factories

A car implements the following interface:

interface Car {
   void start();
   void drive();
   void stop();
}

There are two car factories: Volvo and Toyota. These factories implement a factory method called makeCar. Show how you would implement this using polymorphism (Java or C++), smart factories (Java), and generic factories (C++).

Example: Dragons, Ghosts, and Robots

(a) A computer game has three types of monsters: dragons, robots, and ghosts. All monsters attack heroes. For now, dragons and robots crush heroes, while ghosts scare heroes. In the future, special types of robots and dragons may also scare heroes, while special types of ghosts may crush heroes. Still further in the future there may be new types of monsters and new ways to attack heroes. Use the Strategy pattern to design a monster hierarchy.

(b) How can we use the Factory method pattern to avoid making specific reference to the attack strategy in the monster class?

(c) Both monsters and heroes have a health attribute that ranges from 0% (= dead) to 100%. When a monster attacks a hero, the hero's health decreases by a set amount. When the hero defends himself against a monster, the monster's health is decremented by a set amount. This amount depends on the state of the hero: invincible, super charged, or normal. Of course different heroes are in different states. In the future there may be new hero states we would like to add to the system. Design the hero class. (Hint: This is called the State pattern and it is closely related to the Strategy pattern.)

(d) The hero is moved by the player. Each time the hero moves, all monsters following the hero attack. When a monster dies, it no longer follows the hero. When a hero dies, he can no longer be moved. How could you use the Publisher-Subscriber pattern to notify monsters that the hero has moved?

(e) Sketch an implementation of this game.

(f) How could we use the Model-View-Control pattern to allow us to easily change the appearance of the hero and the way the player moves the hero?

Other Patterns

Publisher-Subscriber

Decorator

Strategy

Abstract Factory

Builder

Singleton

Bridge

Enterprise Patterns

There are two gaps that must be bridged: the gap between the domain model and the domain layer, and the gap between the domain layer and the database schema.

Quest

Quest is an online adventure game. Players move from room to room where they encounter monsters such as dragons and robots, other players, and treasures. Each room has a view. The bottom of the view has a control panel that displays the player's health and wealth. The control panel also has a text field where the user can enter commands such as "login" "move" "turn" "strike" "block" "grab" "exit north".

1. Draw a class diagram showing the relationships between player, maze, room, view, control panel, treasure, door, monster, dragon, and robot.

2. Assume you design this game using the Model-View-Controller architecture. What would the model be the model?

3. Draw a sequence diagram showing how a command "exit south" might be processed assuming a front controller is used.

4. Assume we want to add decorators that synchronize access to the front controller, cache views that can be reused, and login users. Draw a sequence diagram showing how this works.

5. Draw a sequence diagram showing how a command "exit south" might be processed assuming a page controller is used.

6. What is an application controller?

Assume a database contains a rooms table, treasure table, and a players table:

rooms(id: key, view: string)
treasures(id: key, value: int, available: boole, room: fkey)
players(id: key, description: string, health: int, wealth: int, room: fkey)

7. How would a table gateway, row gateway, and data mapper for this database differ?

8. How does a table module differ from a table gateway?

9. How does an active record differ from a row gateway?

Turtle Graphics

A GUI for a turtle graphics program consists of many GUI components: a main window containing a menu bar, a tool bar, and a view. The menu bar consists of four menus: file, edit, command, and help. Each menu consists of the usual menu items:

File (new, open, save, save as, close, quit)
Edit (copy, cut, paste, undo, redo)
Help (about, help)
Command (move, turn, pen up, pen down)

The tool bar consists of buttons that correspond to the most popular menu items.

The model consists of a canvas (a 2 dimensional array of pixels) and a turtle.

1. Draw a class diagram showing the relationship between all of these items.

Assume we want our program to run on two libraries of GUI components: WD, and UP. Both have the same GUI components mentioned above, but the names are prefaced by the name of the library. For example: WDButton, UPButton.

2. Draw a class diagram showing how you would use the Bridge Pattern and Adapter Pattern to separate the conceptual and implementation hierarchies for GUI components.

3. Draw a class diagram showing how you would use the Builder pattern to decouple the construction of the GUI from the construction of the GUI components.

4. Draw a class diagram showing how would you use the abstract factory pattern to decouple the construction of conceptual objects from the construction of library objects.

Assume the canvas implements the following interface:

interface Canvas extends Serializable {
   void drawLine(Point start, Point end);
   int getWidth(); // = width of canvas in pixels
   int getHeight(); // = height in pixels
}

The turtle is given by:

class Turtle implements Serializable {
   Canvas canvas = new Canvas();
   Point position = new Point(0, 0); // position on canvas
   boolean penUp = false; // draws if false
   int heading = 0; // 0 = north, 1 = east, 2 = west, 3 = south

   void turn(int heading) { this.heading = heading; }
   void penUP() { penUp = true; }
   void penDown() { penUp = false; }

   void move(int steps) {
      Point oldPosition = new Point(position.xc, position.yc);
      switch(heading) {
         case 0: position.xc -= steps; break;
         case 1: position.yc += steps; break;
         case 2: position.yc -= steps; break;
         case 3: position.xc += steps; break;
      }
      if (!penUp) canvas.drawLine(oldPosition, position);
   }
}

5. Assume the user use cases correspond to the menu items. Assume a use case controller implements the interface:

interface UseCaseController {
void execute(Serializable model) throws Exception;
}

Sketch a use case controller for the move use case.

6. The current policy in case the turtle moves off the canvas is to throw an exception, but later we may want to alter this policy to do something else, perhaps wrap around. So we add a use case TooFar that extends the Move use case. Show how you would change the move use case controller to add this extension.

7. Sketch an implementation of a transaction script for Turtle Graphics.