Programming Assignment 2

Skyline×3

Data Structures & Algorithms Fall 2009

Due Date

This assignment is due by 11:30 p.m. on Tuesday, 3 November.

See the assignment turn-in page (last modified on 22 September 2009) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 2 is Friday, 6 November 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 a program that inputs a rectangle set S and outputs the skyline for S. Your program 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.

Input

Input should be read from std-in. Input consists of a single timing word followed by one or more rectangle descriptions. A timing word is one of the words square, nlogn, or linear representing a solution taking O(n2), O(n log n) or O(n) time respectively.

A rectangle description is a triple of integers x h w where x is the left-most coordinate of the rectangle side co-incident with the x axis, h is the rectangle height and w is the rectangle width.

The timing word is separated from the building descriptions by one or more space characters, as are successive building descriptions and the succssive integers within a building description.

Example input: 

square 2 3 4
4 5 5
0 2 10

Output

Output is written to std-out and consists of the points making up the skyline of the input rectangle set. Each point is an integer pair x y. Successive integers are separated by one or more space characters.

Implementing

Your code should be implemented in a package called assignment .

Testing

The shell script /export/home/class/cs-305-503/a2/gen-problem, when executed, writes to std-out a correct instance of the Skyline problem: 

$ /export/home/classes/cs-305-503/a2/gen-problem
nlogn
4 1 5 9 1 8 3 4 6 -5 6 10 1 4 6 0 4 5 3 6 1
-7 6
1 -10 7 5 -2 7 3
-4 1
9 0
7 9 -4 5
5
-10 4 5 -8 6 8

$

Your code will be tested on a wide range of problems, not on just the problems generated by gen-problem. You should make sure your testing includes problems beyond those generted by gen-problem.

This page last modified on 26 October 2009.