ACM/College Board/Duke JETT, March 2003

Rectangles: Version I

1. Add methods to SimpleRectangle that return the area and the perimeter of the rectangle (add two methods, one for each property).

2. Add a top-left point to SimpleRectangle so that rectangles are anchored in the plane (assume integer coordinates). Add a new constructor that accepts four parameters and provide default values in the original two-parameter constructor.

3. Add a point to a rectangle so that it grows minimally to contain the new point. Don't use if statements, use static methods Math.min and Math.max to make calculations. public add(int x, int y) { }

   Develop some test cases with anticipated results to see if your method works correctly.

4. Write an equals method to test if one rectangle is equal to another: public boolean equals(Object o) { SimpleRectangle = (SimpleRectangle) o; // add code here }
5. Write a method that finds the perimiter of a java.awt.Rectangle object (assume your method is a static method in a class named RMath). You'll need to consult the API provided. public static int perimiter(Rectangle r) { }

6. Given three java.awt.Rectangle, return the rectangle that is their intersection, use the intersection method rather than createIntersection. public static Rectangle intersection(Rectangle r1, Rectangle r2, Rectangle r3) { }

7. Do the same problem as above, but assume an array of Rectangles is passed to the function (return intersection of all the rectangles). public static Rectangle intersection(Rectangle[] list) { }

   BlueJ

8. Using BlueJ and BigFactorial.java determine how many digits there are in 76! (call a method that returns the result without writing new code).

   Priority Queues

   These questions make reference to the AP PriorityQueue interface and the ArrayList-based simple implementation in ArrayPriorityQueue.java.

   ArrayPriorityQueue

9. The code below show methods peekMin and removeMin from the class ArrayPriorityQueue.

   What is the big-Oh complexity of for an N-element priority queue of removeMin and of peekMin? Justify.

   
       /**
        * Removes and returns a minimal element of this pq
        * @return a minimal element after removing it
        */
   
       public Object removeMin() 
       {
           Object min = peekMin();
   	items.remove(min);
   	return min;
       }
   
       /**
        * Returns a minimal element of this pq
        * @return a minimal element
        */
   
       public Object peekMin() 
       { 
           int minIndex = 0; 
           for (int i = 1; i < items.size(); i++) {
   	    Comparable c = (Comparable) items.get(i);
               if (c.compareTo(items.get(minIndex)) < 0) { 
                   minIndex = i; 
               } 
           } 
           return items.get(minIndex); 
       } 
   
   

10. What happens if either one of peekMin or removeMin is called on an empty priority queue?

11. Consider this alternative implementation of removeMin. Briefly give a reason why this implementation is superior to the one shown above and a reason that it is inferior.

    
        /**
         * Removes and returns a minimal element of this pq
         * @return a minimal element after removing it
         */
    
        public Object removeMin()
        {
    	int minIndex = 0;
    	for(int k=1; k < items.size(); k++) {
    	    Comparable c = (Comparable) items.get(k);
    	    if (c.compareTo(items.get(minIndex)) < 0) {
    		minIndex = k;
    	    }
    	}
    	Object retval = items.get(minIndex);
    	items.set(minIndex,items.get(items.size()-1));
    	items.remove(items.size()-1);
    	return retval;
        }
    
    
    
    

12. Consider the method sort below that sorts its parameter into non-decreasing order. What is the big-Oh complexity of this method? How does the complexity change if the formal parameter list has type LinkedList (in which case the function still works correctly)?

    
        /**
         * Sorts list into ascending/non-decreasing order.
         */
        public void sort(ArrayList list)
        {
    	PriorityQueue pq = new ArrayPriorityQueue();
    	int size = list.size();
    	for(int k=0; k < size; k++) {
    	    pq.add(list.get(k));
    	}
    	for(int k=0; k < size; k++) {
    	    list.set(k, pq.removeMin());
    	}
        }