Programming Assignment 2

Skyline×3

Data Structures and Algorithms Spring 2011


Due Date

This assignment is due by 11:30 p.m. on Wednesday, 23 March.

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

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

Background

Given a set S of rectangles, each of which has a side in common with the x axis and non-negative y values

a rectangle set

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

a skyline

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(n2), 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-503/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, wont be able to find them.

Once youve got your implementation far enough along, you can try it out using the jar file
/export/home/class/cs-503/pa2/pa2.jar
by typing

$ 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 youre using pa2.jar in the public class directory, you would type

$ java -classpath /export/home/class/cs-503/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-503/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 js version by typing

jar tf j | grep 2011

For example,

$ jar tf /export/home/class/cs-503/pa2/pa2.jar | grep 2011
2011.Mar.7

$ 

The recognized optional command-line options are:

Command-line options should be given after main and before the generator class; for example

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


This page last modified on 2011 February 28.