## Final Exam Review Spring2006

Below are questions like those we plan to ask on the Final Exam (Friday the 5th at 2:50 pm). The exam will consist of 5-8 questions like these.

1. If you don't post, neither will we. We will not be posting official solutions to these problems at all! If one of you gets it right, terrific!
2. We will try to always point out if an answer is wrong. We won't always point out when the answer is right.
3. We are glad to work with you toward the right answer. We will give hints, and I'm glad to respond to partial guesses.

## Reverse the sort

Below is the sort from EventQueue.java

```  public void sort(){
// Perform an insertion sort

// For comparing to elements at smaller indices
SimEvent considered = null;
SimEvent compareEvent = null; // Just for use in loop
// Smaller index we're comparing to
int compare;

// Start out assuming that position 0 is "sorted"
// When position==1, compare elements at indices 0 and 1
// When position==2, compare at indices 0, 1, and 2, etc.
for (int position=1; position < elements.size(); position++){
considered = (SimEvent) elements.get(position);
// Now, we look at "considered" versus the elements
// less than "compare"
compare = position;

// While the considered event is greater than the compared event ,
// it's in the wrong place, so move the elements up one.
compareEvent = (SimEvent) elements.get(compare-1);
while (compareEvent.getTime() >
considered.getTime())  {
elements.set(compare,elements.get(compare-1));
compare = compare-1;
// If we get to the end of the array, stop
if (compare <= 0) {break;}
// else get ready for the next time through the loop
else {compareEvent = (SimEvent) elements.get(compare-1);}
}
// Wherever we stopped, this is where "considered" belongs
elements.set(compare,considered);
} // for all positions 1 to the end
} // end of sort()

```

How would you change it so that event with the LARGEST time was at the FRONT of the queue?

## Reverse the insert

Below is the insertion method from EventQueue.java

```  /**
* Put thisEvent into elements, assuming
* that it's already in order.
**/
public void insertInOrder(SimEvent thisEvent){
SimEvent comparison = null;

// Have we inserted yet?
boolean inserted = false;
for (int i=0; i < elements.size(); i++){
comparison = (SimEvent) elements.get(i);

// Assume elements from 0..i are less than thisEvent
// If the element time is GREATER, insert here and
// shift the rest down
if (thisEvent.getTime() < comparison.getTime()) {
//Insert it here
inserted = true;
break; // We can stop the search loop
}
} // end for

// Did we get through the list without finding something
// greater?  Must be greater than any currently there!
if (!inserted) {
// Insert it at the end
}
```

How would you change it so that event with the LARGEST time was at the FRONT of the queue?

## Match the Data Structure

Below is a method setUp2() from SoundTreeExample.

(a) Below, you will find four possible diagrams describing the tree created in this method. Idnetify the one that you think is correct.

(b) Show that you understand how tree traversal works by describing the sounds that you hear, in order and with scaling effects, from playing this tree.

```    public void setUp2() {
FileChooser.setMediaPath("D:/cs1316/MediaSources/");
Sound clap = new Sound(FileChooser.getMediaPath("clap-q.wav"));
Sound chirp = new Sound(FileChooser.getMediaPath("chirp-2.wav"));
Sound rest = new Sound(FileChooser.getMediaPath("rest-1.wav"));
Sound snap = new Sound(FileChooser.getMediaPath("snap-tenth.wav"));
Sound clave = new Sound(FileChooser.getMediaPath("clave-twentieth.wav"));
Sound gong = new Sound(FileChooser.getMediaPath("gongb-2.wav"));
Sound guzdial = new Sound(FileChooser.getMediaPath("guzdial.wav"));
Sound is = new Sound(FileChooser.getMediaPath("is.wav"));

root = new SoundBranch();
SoundNode sn;

SoundBranch branch1 = new SoundBranch();
sn = new SoundNode(guzdial.append(is).append(snap));
sn = new SoundNode(guzdial.append(is).append(is));

scaledBranch = new ScaleBranch(2.0);
sn = new SoundNode(rest.append(chirp).append(clap));

scaledBranch = new ScaleBranch(0.5);
sn = new SoundNode(guzdial.append(is).append(gong));

SoundBranch branch2 = new SoundBranch();
sn = new SoundNode(clap.append(clap).append(clave));
sn = new SoundNode(snap.append(snap).append(clave));
sn = new SoundNode(snap.append(snap).append(clave));

root.playFromMeOn();
}

```

Legend:

ONE:

TWO:

THREE:

FOUR:

Questions, comments, and answers at FinalExam Review Spring2006: Match the Data Structure

## Understand the tree

Below is a (slightly modified) copy of the code that sets up the WolfAttackMovie.

```  /**
* Set up all the pieces of the tree.
**/
public void setUp(){
FileChooser.setMediaPath("D:/cs1316/mediasources/");
Picture wolf = new Picture(FileChooser.getMediaPath("dog-blue.jpg"));
Picture house = new Picture(FileChooser.getMediaPath("house-blue.jpg"));
Picture tree = new Picture(FileChooser.getMediaPath("tree-blue.jpg"));
Picture monster = new Picture(FileChooser.getMediaPath("monster-face3.jpg"));

//Make the forest
MoveBranch forest = new MoveBranch(10,400); // forest on the bottom
HBranch trees = new HBranch(50); // Spaced out 50 pixels between
BlueScreenNode treenode;
for (int i=0; i < 3; i++) // insert 3 trees
{treenode = new BlueScreenNode(tree.scale(0.5));

// Make the cluster of attacking "wolves"
wolfentry = new MoveBranch(10,50); // starting position
VBranch wolves = new VBranch(20); // space out by 20 pixels between
BlueScreenNode wolf1 = new BlueScreenNode(wolf.scale(0.5));
BlueScreenNode wolf2 = new BlueScreenNode(wolf.scale(0.5));
BlueScreenNode wolf3 = new BlueScreenNode(wolf.scale(0.5));

// Make the cluster of retreating "wolves"
wolfretreat = new MoveBranch(400,50); // starting position
wolves = new VBranch(20); // space them out by 20 pixels between
wolf1 = new BlueScreenNode(wolf.scale(0.5).flip());
wolf2 = new BlueScreenNode(wolf.scale(0.5).flip());
wolf3 = new BlueScreenNode(wolf.scale(0.5).flip());

// Make the village
MoveBranch village = new MoveBranch(300,450); // Village on bottom
HBranch hhouses = new HBranch(40); // Houses are 40 pixels apart across
BlueScreenNode house1 = new BlueScreenNode(house.scale(0.25));
BlueScreenNode house2 = new BlueScreenNode(house.scale(0.25));
BlueScreenNode house3 = new BlueScreenNode(house.scale(0.25));
VBranch vhouses = new VBranch(-50); // Houses move UP, 50 pixels apart
BlueScreenNode house4 = new BlueScreenNode(house.scale(0.25));
BlueScreenNode house5 = new BlueScreenNode(house.scale(0.25));
BlueScreenNode house6 = new BlueScreenNode(house.scale(0.25));
hhouses.addChild(vhouses); // Yes, a VBranch can be a child of an HBranch!

// Make the monster
hero = new MoveBranch(400,300);
BlueScreenNode heronode = new BlueScreenNode(monster.scale(0.75).flip());

//Assemble the base scene
sceneRoot = new Branch();
}
```

```  /**
* Method to add nodes to children
**/
if (children != null)
else
{children = child;}
}
```

A. Below is a (slightly modified) copy of the tree that we showed in lecture for what got generated by this code. But now you know better-this isn't exactly how it works. This depiction of the tree doesn't make clear the difference between the children links and the next links.

Draw in whatever additional links you need, and X out the ones you don't, and label all children and next links. (You can just write a "C" or "N" near the arrow to represent children and next.) Make sure that you get the order right based on the code above.

B. This tree doesn't include the wolfretreat or hero branches. Draw those below or on the next page, with nodes represented like above and with links identified clearly as children or next.

## Be a Data Structure Consultant

Now that you’re a data structures expert, people may want to hire you as a consultant to advise them on what data structure to use when. Suggest a structure for each of the situations described below. Recall that data structures that we discussed this semester include arrays, matrices, linked lists, circular linked lists, trees, graphs, stacks, queues, and event queues.

(a) “I’ve got a set of data that I need to store and access: Just a long list of objects. The size of the data will never change, and I need super-fast access to each and every element. What data structure should I use?”

(b) “I’m trying to represent the hierarchical relationship between employees in a company. People are being hired or leaving all the time. What’s a good way of representing that?”

(c) “I’m creating a simulation of a cafeteria. There are lines for sandwiches, for hot food, and for drinks. What’s the best data structure to represent the people standing in line?”

(d) “I’m going to represent the sidewalks around Georgia Tech. They go every which way, and they connect all over the place. What kind of data structure do you use to represent things like that?”

(e) "I'm making a video game that will run on wrist watches-small screen, low resolution. To 'animate' my characters, I'm just going to use real simple animation: I'll have images for four different positions of the character that I'll loop through. What's a good data structure for storing these images?"

Questions, comments, and answers at FinalExam Review Spring2006: Be a Data Structure Consultant

## What’s the Diff?

Each of the pairs below describes two things that are similar. Tell me what’s similar about them, and then, what the critical difference is it between them. For example, if I gave you int and double, you’d tell me that they are two types, each representing numbers, but int is only for integers and double can have decimal places.

(a) Discrete Event Simulations vs. Continuous Simulations

(b) Stacks vs. Queues

(c) Trees vs. Lists

(d) BorderLayout vs. FlowLayout

## Make a Super Truck

Below is the code for the Truck class from our FactorySimulation. Let’s imagine that our company has just bought a whole new fleet of super trucks that can carry 50% as much (20-30 items per load) and takes 1/3 less time to travel (average of two days per trip). What would you change in the Truck class to describe the new super trucks? Be specific—cross out and rewrite lines below so that this class will work as the new super truck.

```import java.awt.Color; // For color

/**
* Truck -- delivers product from Factory
* to Warehouse.
**/
public class Truck extends DEAgent {

/////// Constants for Messages
public static final int FACTORY_ARRIVE = 0;
public static final int WAREHOUSE_ARRIVE = 1;

////// Fields /////
/**
* Amount of product being carried
**/

//// METHODS ///
/** A new load is between 10 and 20 on a uniform distribution */
return 10+randNumGen.nextInt(11);
}

/** A trip distance averages 3 days */
public double tripTime(){
double delay = randNumGen.nextGaussian()+3;
if (delay < 1)
// Must take at least one day
{return 1.0+((DESimulation) simulation).getTime();}
else {return delay+((DESimulation) simulation).getTime();}
}
/**
* Set up the truck
* Start out at the factory
**/
public void init(Simulation thisSim){
// Do the default init
super.init(thisSim);
this.setPenDown(false); // Pen up
this.setBodyColor(Color.green); // Let green deliver!

// Show the truck at the factory
this.moveTo(30,350);
// Load up at the factory, and set off for the warehouse
new SimEvent(this,tripTime(),WAREHOUSE_ARRIVE));
}

/**
* Process an event.
* Default is to do nothing with it.
**/
public void processEvent(int message){
switch(message){
case FACTORY_ARRIVE:
// Show the truck at the factory
((DESimulation) simulation).log(this.getName()+"\t Arrived at factory");
this.moveTo(30,350);
// Load up at the factory, and set off for the warehouse
new SimEvent(this,tripTime(),WAREHOUSE_ARRIVE));
break;
case WAREHOUSE_ARRIVE:
// Show the truck at the warehouse
this.moveTo(50,50);
// Unload product -- takes zero time (unrealistic!)
new SimEvent(this,tripTime(),FACTORY_ARRIVE));
break;
}
}

// CONSTRUCTORS GO HERE, BUT THEY’VE BEEN REMOVED FOR THE EXAM.
}
```

Questions, comments, and answers at FinalExam Review Spring2006: Make a Super Truck

## And a One and a Two

Below is the code from SongNode for weave. Write a new method weaveTwo which takes two input SongNode instances (one and two) and an int named count. For count times, insertAfter one copy of one and two copies of two.

```  /**
* Weave the input phrase count times every skipAmount nodes
* @param nextOne node to be copied into the list
* @param count how many times to copy
* @param skipAmount how many nodes to skip per weave
*/
public void weave(SongNode nextOne, int count, int skipAmount)
{
SongNode current = this; // Start from here
SongNode copy; // Where we keep the one to be weaved in
SongNode oldNext; // Need this to insert properly
int skipped; // Number skipped currently

for (int i=1; i <= count; i++)
{
copy = nextOne.copyNode(); // Make a copy

//Skip skipAmount nodes
skipped = 1;
while ((current.next() != null) && (skipped < skipAmount))
{
current = current.next();
skipped++;
};

if (current.next() == null) // Did we actually get to the end early?
break; // Leave the loop

oldNext = current.next(); // Save its next
current.insertAfter(copy); // Insert the copy after this one
current = oldNext; // Continue on with the rest
}
}

```

Questions, comments, and answers at FinalExam Review Spring2006: And a One and a Two

## Compare the GUIs

A. Draw the tree described by the below two classes.
B. Explain the difference in what the user sees from creating instances of these two classes. Relate it to trees and rendering.

EXAMPLE ONE:
```/**
* A GUI that has various components in it, to demonstrate
* UI components and layout managers (rendering)
**/
import javax.swing.*; // Need this to reach Swing components
import java.awt.*; // Need this to reach FlowLayout

public class GUItreeFlowed extends JFrame {

public GUItreeFlowed(){
super("GUI Tree Flowed Example");

this.getContentPane().setLayout(new FlowLayout());
/* Put in a panel with a label in it */
JPanel panel1 = new JPanel();
JLabel label = new JLabel("This is panel 1!");

/* Put in another panel with two buttons in it */
JPanel panel2 = new JPanel();
JButton button1 = new JButton("Make a sound");
JButton button2 = new JButton("Make a picture");

this.pack();
this.setVisible(true);
}
```

EXAMPLE TWO:
```/**
* A GUI that has various components in it, to demonstrate
* UI components and layout managers (rendering)
**/
import javax.swing.*; // Need this to reach Swing components
import java.awt.*; // Need this to reach BorderLayout

public class GUItreeBordered extends JFrame {

public GUItreeBordered(){
super("GUI Tree Bordered Example");

this.getContentPane().setLayout(new BorderLayout());
/* Put in a panel with a label in it */
JPanel panel1 = new JPanel();
JLabel label = new JLabel("This is panel 1!");

/* Put in another panel with two buttons in it */
JPanel panel2 = new JPanel();
JButton button1 = new JButton("Make a sound");
JButton button2 = new JButton("Make a picture");

this.pack();
this.setVisible(true);
}
}

```

## Slow! Sick People Crossing!

Below is the code for the class PersonAgent from the DiseaseSimulation example. REMOVEDge it so that, when people get sick, they slow down by 75%.
```import java.awt.Color; // Color for colorizing

/**
* PersonAgent -- Person as a subclass of Agent
**/
public class PersonAgent extends Agent {

public boolean infection;

/**
* Initialize, by setting color and making move fast
**/
public void init(Simulation thisSim){
// Do the normal initializations
super.init(thisSim);

// Make it lightGray
setColor(Color.lightGray);

// Don't need to see the trail
setPenDown(false);

// Start out uninfected
infection = false;

// Make the speed large
speed = 100;
}

/**
* Count infected
**/
public int infected() {
int count = 0;
PersonAgent check;

for (int i = 0; i<agents.size(); i++){
check = (PersonAgent) agents.get(i);
if (check.infection) {count++;}
}

return count;
}
/**
* Become infected
**/
public void infect(){
this.infection = true;
this.setColor(Color.red);

// Print out count of number infected
System.out.println("Number infected: "+infected());
}

/**
* How a Person acts
**/
public void act()
{
// Is there a person within infection range of me?
PersonAgent closePerson = (PersonAgent) getClosest(20,
simulation.getAgents());

if (closePerson != null) {
// If this person is infected, and I'm not infected
if (closePerson.infection && !this.infection) {
// I become infected
this.infect();
}
}

// Run the normal act() -- wander aimlessly
super.act();
}

////////////////////////////// Constructors ////////////////////////
// Copy this section AS-IS into subclasses, but rename Agent to

/**
* Constructor that takes the model display (the original
* position will be randomly assigned)
* @param modelDisplayer thing that displays the model
* @param thisSim my simulation
*/
public PersonAgent (ModelDisplay modelDisplayer,Simulation thisSim)
{
super(randNumGen.nextInt(modelDisplayer.getWidth()),
randNumGen.nextInt(modelDisplayer.getHeight()),
modelDisplayer, thisSim);
}

/** Constructor that takes the x and y and a model
* display to draw it on
* @param x the starting x position
* @param y the starting y position
* @param modelDisplayer the thing that displays the model
* @param thisSim my simulation
*/
public PersonAgent (int x, int y, ModelDisplay modelDisplayer,
Simulation thisSim)
{
// let the parent constructor handle it
super(x,y,modelDisplayer,thisSim);
}

}
```

Questions, comments, and answers at FinalExam Review Spring2006: Slow! Sick People Crossing!

## Explain It in Your Words

A. What's the difference between discrete event and continuous simulations? When would you use each? For each, give an example of a kind of question that you could ask with one but not with the other.

B. Why did we use trees to create animations?

C. Why do we consider it "hard" to insert and delete into the middle of an array? Is it easier or harder with a matrix?

## Interpret the UML

Below is the UML class diagram for the Factory discrete event simulation.

A. By what name does a Resource know its queue of agents waiting for the resource?

B. When an instance of Distributor wants to get the object representing the factory, what expression does it evaluate? (Yes, it all is here in the diagram.)

C. If a Truck wanted to check the position of all trucks and distributors, how would it get at all of those objects? What expression would it evaluate?

D. By what name does FactorySimulation access an instance of FrameSequence?

## Explaining the Insert

Here is the (slightly modified) code that we used for inserting events into the event queue so that they were always sorted.

```  /**
* Put thisEvent into elements, assuming
* that it's already in order.
**/
public void insertInOrder(SimEvent thisEvent){
SimEvent comparison = null;

// Have we inserted yet?
boolean inserted = false;
for (int i=0; i < elements.size(); i++){
comparison = (SimEvent) elements.get(i);

// Assume elements from 0..i are less than thisEvent
// If the element time is GREATER, insert here and
// shift the rest down
if (thisEvent.getTime() < comparison.getTime()) {
//Insert it here
inserted = true;
//POSITION A
break; // We can stop the search loop
}
} // end for

// Did we get through the list without finding something
// greater?  Must be greater than any currently there!
if (!inserted) {
// Insert it at the end
// POSITION B
}
```

A. The block in which POSITION A is indicated inserts the new event thisEvent, but so does the block in which POSITION B is indicated. Under what condition does the add next to POSITION A get executed? Under what condition does the addLast next to POSITION B get executed?

B. Does it ever happen that both POSITION A's add and POSITION B's addLast get executed? If so, under what condition? If not, why not-what would prevent both add's from being executed?

### Make a Smarter Distributor

Below is the code for the Distributor from our factory discrete event simulation at the end of class.
```import java.awt.Color; // To color our distributors
/**
* Distributor -- takes orders from Market to Warehouse,
* fills them, and returns with product.
**/
public class Distributor extends DEAgent {

/////// Constants for Messages
public static final int MARKET_ARRIVE = 0;
public static final int MARKET_LEAVE = 1;
public static final int WAREHOUSE_ARRIVE = 2;

/** AmountOrdered so-far */
int amountOrdered;

// Methods

public int newOrders(){
// Between 5 and 25, uniform
return randNumGen.nextInt(21)+5;
}

public double timeToDeliver(){
// On average 5 days to deliver, normal distr.
return validTime(randNumGen.nextGaussian()+5);}

public double tripTime(){
// On average 2 days to travel between market and warehouse
return validTime(randNumGen.nextGaussian()+2);}

/**
* Initialize a distributor.
* Start in the market, taking orders, then
* schedule arrival at the warehouse.
**/
public void init(Simulation thisSim){
//First, do the normal stuff
super.init(thisSim);
this.setPenDown(false); // Pen up
this.setBodyColor(Color.blue); // Go Blue!

// Show the distributor in the market
this.moveTo(600,460); // At far right
// Get the orders, and set off for the warehouse
amountOrdered = this.newOrders();
new SimEvent(this,tripTime(),WAREHOUSE_ARRIVE));
}

/** Are we ready to be unlocked? */
// Is the amount in the factory more than our orders?
return
((FactorySimulation) simulation).getFactory().amountAvailable()
>= amountOrdered;}

/**
* I've been unblocked!
* @param resource the desired resource
**/
public void unblocked(Resource resource){
super.unblocked(resource);

// Consume the resource for the orders
((DESimulation) simulation).log(this.getName()+"\t unblocked!");
((FactoryProduct) resource).consume(amountOrdered); // Zero time to load?
((DESimulation) simulation).log(this.getName()+"\t Gathered product for orders of \t"+amountOrdered);
// Schedule myself to arrive at the Market
new SimEvent(this,tripTime(),MARKET_ARRIVE));
}

/**
* Process an event.
* Default is to do nothing with it.
**/
public void processEvent(int message){
switch(message){
case MARKET_ARRIVE:
// Show the distributor at the market, far left
((DESimulation) simulation).log(this.getName()+"\t Arrived at market");
this.moveTo(210,460);
// Schedule time to deliver
new SimEvent(this,timeToDeliver(),MARKET_LEAVE));
break;
case MARKET_LEAVE:
// Show the distributor at the market, far right
((DESimulation) simulation).log(this.getName()+"\t Leaving market");
this.moveTo(600,460);
// Get the orders, and set off for the warehouse
amountOrdered = this.newOrders();
new SimEvent(this,tripTime(),WAREHOUSE_ARRIVE));
break;
case WAREHOUSE_ARRIVE:
// Show the distributor at the warehouse
((DESimulation) simulation).log(this.getName()+"\t Arrived at warehouse");
this.moveTo(600,50);
// Is there enough product available?
FactoryProduct factory = ((FactorySimulation) simulation).getFactory();
if (factory.amountAvailable() >= amountOrdered)
{
// Consume the resource for the orders
factory.consume(amountOrdered); // Zero time to load?
((DESimulation) simulation).log(this.getName()+"\t Gathered product for orders of \t"+amountOrdered);
// Schedule myself to arrive at the Market
new SimEvent(this,tripTime(),MARKET_ARRIVE));
}
else {// We have to wait until more product arrives!
((DESimulation) simulation).log(this.getName()+"\t is blocking");
waitFor(((FactorySimulation) simulation).getFactory());}
break;
}}

////////////////////////////// Constructors ////////////////////////
// REMOVED FOR SPACE
}
```

Your Distributors have realized that sometimes their customers have a rush need for product. If the Distributors could satisfy the Customers immediately, the Customers will be much happier. So now, your Distributors want to grab an extra FIVE (5) products each time that they leave the factory, beyond the number ordered already. The Distributors will sell those five products while on the road, in the Market.

REMOVEDge the code above to create this new kind of distributor. Don't change newOrders()! The number being ordered and its probability distribution doesn't change. However, do wait for 5 more product and consumer 5 more product. Scratch out whatever lines you need to and write in new code on the class above.

Questions, comments, and answers at FinalExam Review Spring2006: Make a smarter distributor

## Explain the Disease Simulation

Here's a UML diagram that you've seen before.

A. What are all the instance variables understood by the PersonAgent?

B. What are all the methods understood by DiseaseSimulation?

C. If a PersonAgent wants to get at the FrameSequence in his simulation, how would he do it? What code would he execute?

Questions, comments, and answers at FinalExam Review Spring2006: Explain the Disease Simulation