If you are one of the people whom Prof. Hearst said should most definitely take IS255, we won't grade your exam, but we would like to see it. So please answer No below if you are one of these people:
Should we grade this exam? Yes No
Name: _______________________________________
Question 1. Data Structures
(a) What does ``Quicksort'' do?
(b) Quicksort is an O(n log n) recursive algorithm. Explain what
``O'', ``n'', ``log'', ``recursive'', and ``algorithm'' mean. Be as
precise as possible.
(c) Consider data that has been run through Quicksort. What is
the order of the expected time to search for that data using the standard
algorithm? Write this in the most concise mathematical notation
you know.
(d) Briefly describe two algorithms that perform the same function as
quicksort. Which one is these three algorithms is best? Why?
(e) If we are using quicksort on an array of very large data data
records, it may take time to move the data records in memory. What can we
do to make running quicksort on large data records almost as fast as quicksort
on integers?
Question 2. Java and OOP
Please refer to the java code on the separate page when answering the following questions:
(a) What is the relationship between the following three classes:
GeometricObject, Rectangle and Square?
(b) Why can't we create an instance of the GeometricObject class? (Why
would line 13 in ShapeFactory.java, if uncommented, produce an error?)
(c) What is wrong with line 19 of ShapeFactory.java? What is the correct way
of accessing the count of GeometricObjects? What is the output of this
line when corrected?
(d) What is the purpose of lines 6-12 in Rectangle.java? What is the
special name given to this type of method? What about lines 14-21?
(e) What is the purpose of the 'super' statements (lines 7, 12) in
Square.java?
(f) What changes must be made if we wish to keep track of the number of
Squares (in addition to the GeometricObject count in general)?
(g) What changes must be made to ShapeFactory to catch any exceptions thrown
by the Rectangle and Square classes in the creation of new geometric objects?