Description
1 (short answers)
a) (3 points) What must a non-abstract subclass of an abstract class do?
b) (3 points) You have the following stack:
top -> 55 66 11 88 1 78
What is the result of a top() operation (element returned only)?
c) (3 points) You have the following queue:
front -> 55 66 11 88 1 78 22 <- back
What is the result of a dequeue operation (show the new queue and the element returned)?
d) (3 points) What is the base case for the following recursive program?
public class Recursion2b
{
public static void main (String args[])
{
test(1);
System.out.println();
}
public static void test (int n)
{
System.out.print ("\nLevel: " + n);
if (n <= 2)
test (n+1);
System.out.print ("\nLEVEL: " + n);
}
}
2A. (24 points) The following page contains part of a linked list implementation we used in
class modified to use only Integer objects. You are to add the following method:
- An instance method public int countAdjacentPairs() which returns the
number of “adjacent duplicate” values in the list.
For example the following list:
Tail
¯
headà 1à 2à 3à 4à 5à null
would return 0 (there are no adjacent pairs)
Tail
¯
headà 1à 1à 2à 1à 1à null
would return 2 (there are a total of 2 adjacent pairs – 2 pairs of 1’s)
Tail
¯
headà 1à 2à 2à 1à null
would return 1 (there is a total of 1 adjacent pair – 1 pair of 2’s – the 1’s are not adjacent)
Tail
¯
headà 2à 2à 2à 2à null
would return 3 (there are a total of 3 adjacent pairs – the first two 2’s, the second and
third 2; and the third and fourth 2 are all adjacent pairs even though 2 of the 2’s are part
of 2 pairs)
You cannot modify the ListNode class.
2B. (5 points) What is the Big Oh of your solution to this question?
public class SinglyLinkedListInteger {
//---------------- nested Node class ----------------
/**
* Node of a singly linked list, which stores a reference to its
* element and to the subsequent node in the list (or null if this
* is the last node).
*/
private static class Node {
/** The element stored at this node */
private Integer element; // reference to the element stored at this node
/** A reference to the subsequent node in the list */
private Node next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param n reference to a node that should follow the new node
*/
public Node(Integer e, Node n) {
element = e;
next = n;
}
// Accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public Integer getElement() { return element; }
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node getNext() { return next; }
// Modifier methods
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the SinglyLinkedList
/** The head node of the list */
private Node head = null; // head node of the list (or null if empty)
/** The last node of the list */
private Node tail = null; // last node of the list (or null if empty)
/** Number of nodes in the list */
private int size = 0; // number of nodes in the list
/** Constructs an initially empty list. */
public SinglyLinkedListInteger() { } // constructs an initially empty list
// access methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns (but does not remove) the first element of the list
* @return element at the front of the list (or null if empty)
*/
public Integer first() { // returns (but does not remove) the first element
if (isEmpty()) return null;
return head.getElement();
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public Integer last() { // returns (but does not remove) the last element
if (isEmpty()) return null;
return tail.getElement();
}
// update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(Integer e) { // adds element e to the front of the
list
head = new Node(e, head); // create and link a new node
if (size == 0)
tail = head; // special case: new node becomes tail also
size++;
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(Integer e) { // adds element e to the end of the
list
Node newest = new Node(e, null); // node will eventually be the tail
if (isEmpty())
head = newest; // special case: previously empty list
else
tail.setNext(newest); // new node after existing tail
tail = newest; // new node becomes the tail
size++;
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public Integer removeFirst() { // removes and returns the first
element
if (isEmpty()) return null; // nothing to remove
Integer answer = head.getElement();
head = head.getNext(); // will become null if list had only one
node
size--;
if (size == 0)
tail = null; // special case as list is now empty
return answer;
}
}
3A. (24 points) On the next page is the BinaryNode class used to make a BinarySearchTree
(modified to remove generics). The following pages contain part of the BinarySearchTree
implementation. You are to add the following method to the BinarySearchTree class:
- Override java's equals method (public boolean equals (Object o)). This
method returns true if and only if the two trees have the same elements in the tree.
Note: This is not the same definition of equality from the sample question we did in class.
Under this definition, two trees are equal if, and only if; they have the same elements in
them regardless of position.
You can use the following methods from a Queue class which has the following methods:
public Queue( );
public boolean isEmpty( );
public Comparable dequeue( );
public void enqueue( Comparable x );
Do not worry about catching overflows from the Queue class – you can assume the queue
can hold all your data.
Basically, you want to build two queues - one with the elements of each
BinarySearchTree. Then cycle through the queues to make sure they contain all the same
elements. (You could use a different algorithm if you had a successor method for the
BinarySearchTree but you do not have one.)
The order in which you place the elements into the queue is very important. Your
algorithm should only visit each element in each queue one time (as opposed to cycling
through one of the queues for each element in the other queue).
You can use as many helper methods as you see fit. One solution uses just one recursive
helper method for building the queues.
3b) (5 points) What is the Big Oh for your algorithm?
// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of package DataStructures
class BinaryNode
{
// Constructors
BinaryNode( Comparable theElement )
{
this( theElement, null, null );
}
BinaryNode( Comparable theElement, BinaryNode lt, BinaryNode rt )
{
element = theElement;
left = lt;
right = rt;
}
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
public class BinarySearchTree
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( Comparable x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( Comparable x )
{
root = remove( x, root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( )
{
return elementAt( findMin( root ) );
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public Comparable findMax( )
{
return elementAt( findMax( root ) );
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x )
{
return elementAt( find( x, root ) );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t )
{
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
*/
private BinaryNode insert( Comparable x, BinaryNode t )
{
/* 1*/ if( t == null )
/* 2*/ t = new BinaryNode( x, null, null );
/* 3*/ else if( x.compareTo( t.element ) < 0 )
/* 4*/ t.left = insert( x, t.left );
/* 5*/ else if( x.compareTo( t.element ) > 0 )
/* 6*/ t.right = insert( x, t.right );
/* 7*/ else
/* 8*/ ; // Duplicate; do nothing
/* 9*/ return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
*/
private BinaryNode remove( Comparable x, BinaryNode t )
{
if( t == null )
return t; // Item not found; do nothing
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private BinaryNode findMin( BinaryNode t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t )
{
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t )
{
if( t == null )
return null;
if( x.compareTo( t.element ) < 0 )
return find( x, t.left );
else if( x.compareTo( t.element ) > 0 )
return find( x, t.right );
else
return t; // Match
}
/** The tree root. */
private BinaryNode root;
}
4 (25 points) President Elect Biden wants to create an alternative energy platform. He asked
internet inventor, Al Gore, to spearhead a new project to identify the best mix of alternative
energy sources. They have hired you to build an object oriented model which can be used to
measure the energy producing capabilities of various combinations of generation systems.
It seems clear that no single solution will be able to replace fossil fuels in the short term.
Instead it appears many different promising technologies will need to be employed to generate
energy. Biden hopes that the aggregate power harnessed will start to reduce our need to burn
fossil fuels.
It is also clear that the prototype you build must be flexible enough to easily add new
technologies which are yet to be invented.
The first step is to build a scaled down implementation as a proof of concept. If it works you
will be hired to build a larger system.
You need to design the following classes:
EneryProducer
WindFarm
SolarArray
All EnergyProducers have an identification number called a serial number. A valid serial
number is a positive integer. If a number below 1 is given as a serial number, a minus 1 (-1)
should be assigned as the serial number to indicate an incorrect serial number.
EnergyProducer has an abstract method called energy() which calculates the amount of
energy (in Megawatts) that can be produced by an EnergyProducer instance and returns the
value as a double.
(continued on next page)
For the prototype, EnergyProducer will only have two subclasses — WindFarm and
SolarArray.
— —
WindFarm objects have an instance variable for the number of acres (int) and an instance
variable for the Megawatts produced per acre (double). The energy produced by a
WindFarm object is
(Number of acres) X (Megawatts per acre)
— —
SolarArray objects have an instance variable for the maximum output (double) in
Megawatts and an instance variable for today’s intensity factor (double between 0 and 1).
The energy produced by a SolarArray object is:
(Maximum output) X (today’s intensity factor)
— —
The idea is to have client programs create an array of EnergyProducers and cycle through
the array to calculate the potential energy creation.
Design the three classes using all the good practices we have discussed throughout the semester.
The only getter and setter you need to write are for the serial number (to save time). You do
need to write constructors for each of the three classes. Your constructors can call setters even
if you did not write them.
Hints:
– Think about abstract classes, inheritance, and polymorphism when designing the
classes.
– Program “in the general” as much as possible.
5 (5 points) Write a client program (main() only) that produces an array of:
1 SolarArray (capable of 4.5 Megawatts and an intensity factor of .50)
1 WindFarm (10,000 acres and can generate 2.5 Megawatts per acre)
in an array of EnergyProducers. Use any serial numbers.
Then loop through the array to total the energy produced. The only thing you need to print is
the total.
