Programming Assignment 2

Due Date

See the assignment turn-in page (last modified on 23 February 2010) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 2 is Saturday, 13 November at 11:30 p.m. It is not possible to turn-in Assignment 2 after the absolute deadline.

Background

the skyline of S is the line tracing the largest y value from any rectangle in S

The Problem

Write the method getSkyline() that accepts a rectangle set S and returns the skyline for S. Your method should solve the problem three different ways; each solution should produce the correct answer, but will take differing amounts of time: O(n²), O(n log n) or O(n), where n is the number of rectangles in S. getSkyline() is defined in the interface

/export/home/class/cs-305/pa2/Skyliner.java

Implementing

The classes created for the first assignment should be placed in the default package. Classes are placed in the default package when the Java source code does not use package declarations. Using package declarations in Java source code places class files in non-default packages, and the turn-in software, expecting the class files to be in the default package, won’t be able to find them.

/export/home/class/cs-305/pa2/pa2.jar

$ java -classpath jar-path/pa2.jar:. main class-name

where jar-path is the path to pa2.jar and class-name is the name of the class implementing the Skyliner interface. For example, if the class Outliner implements Skyliner and you’re using pa2.jar in the public class directory, you would type

$ java -classpath /export/home/class/cs-305/pa2/pa2.jar:. main Outliner

Make sure you give the class name (Outliner in this example) on the command line, not the name of file containing Outliner (Outliner.class).

You can simplify your typing a bit by copying pa2.jar to your working directory ( . ):

$ cp /export/home/class/cs-305/pa2/pa2.jar .

$ java -classpath ./pa2.jar:. main Outliner

If you do copy pa2.jar, make sure you keep it up to date with version in the class directory. You can check jar file j’s version by typing

jar tf j | grep 2010

For example,

$ jar tf /export/home/class/cs-305/pa2/pa2.jar | grep 2010
2010.Sep.29

$ 

The recognized optional command-line options are:

• -c: only check answers; the default is to check answers and run timing tests.
• -g: show a graph of the timing results; the default is to not show a graph. Ignored if timing isn’t being checked.
• -t: only check timing; the default is to check answers and run timing tests.
• -v: print informative message to std-err while running tests.

$ java -ea -cp pa2.jar:. main -v SL
Check correctness.
Check timings.
 
$