Question 1.

(a)  Sort data

(b)  "O" notation is used to indicate running time.  Mathematically, given two functions f(n) and g(n), ``f is O(g)'' means there exists N, c > 1 such that for all n>N, f(n) < c*g(n).

n is the size of the input, in this case, the number of data items to be sorted.

log is logarithm.  ``x is the logarithm of m base b'' means b^x = m, or b raised to the power of x equals m.

Recursive means that an algorithm calls itself (usually on a subset of its input).

An algorithm is a formal description of a method of computing an output from input

(c)  O(log n)

(d)  There are many sorting algorithms that can be discussed here.  Here are two:

Bubble sort:  in iterative rounds, sweep through the array, examing successive pairs of data in an array as needed so the smaller item is first.  Repeat the sweep n-1 times until all data is sorted.

Insertion sort:  Sort the first two items.  Then figure out where the 3rd last item goes, and put it in, so the first 3 items are sorted.  In the nth step, figure out where the nth item goes, so the first n items are sorted.

Bubble sort has O(n^2) running time.  Standard implementations of Insertion sort also take O(n^2) running time.  (It is possible to improve the running time of Insertion sort with very clever implementations, however, they are quite difficult and still inferior to Quicksort for most inputs.)  Quicksort has O(n log n) running time, and usually runs faster than these other sorting algorithms.

(e)  Use pointers to the large data records, and sort them.  Java usually takes care of this for you.

Question 2.

(a) This is an example of inheritance in Java. GeometricObject is a superclass which is extended by Rectangle, which is in turn extended by Square.

(b) GeometricObject is an abstract class and no objects can be instantiated from an abstract class (it can only function as a superclass).

(c) GeometricObject.count is a private variable and cannot be directly accessed from the "outside". There should be a method in the GeometricObject class that returns the value of count (which happens to exist).

The correct implementation should be:

System.out.println("Total number of GeometricObjects created is  " + GeometricObject.getCount());

and its output should be:

Total number of GeometricObjects created is 3.

(d) This is the default constructor of the class Rectangle. It will be used when no arguments are passed from the main applications (ShapeFactory). It is supposed to give a new object of the class Rectangle some basic properties (e.g., x and y coordinates). Lines 14-21 is also a contructor. The difference between them is the "signature" which is (for all methods) the combination of the name of the method plus the form of the arguments (order matters). When multiple methods exist with the same name, the method will be selected based on the signature. Using different constructors (methods) depending on signature is an example of "overloading".

(e) Defining a method in a subclass with the same name as a method defined in the corresponding superclass overwrites the method inherited from the superclass. In this case, you can invoke the overridden method through the use of the super keyword, i.e., "super(x0, y0, length)" calls Rectangle.Rectangle(double, double, double), passing the double objects for x0, y0, and length as the arguments.

(f) Add a static count variable within the Square class and increment that count each time a new Square is created.

(g) Enclose lines 14-17 of ShapeFactory.java within a try block, and insert a catch block immediately afterwards.