EECS2011ON: Fundamentals of Data Structures

Assignment 1

• This is an individual assignment; you may not share code with other students.

• Read the course FAQ on how to submit assignments and the marking scheme.

• Print your name, EECS account and student ID number on top of EVERY file you

submit.

Department of EECS

York University

Term: Winter 2020

Instructor: Andy Mirzaian

Further Instructions:

• This assignment consists of 3 problems and is designed to let you practice on arrays, (nested)

loops, and some elementary constructs of the Java programming language.

• You can also access the following code templates:

ArraySqeeze.java , ArrayLongestPlateau.java , TestHelper.java .

• You will design more classes/fields/methods and test cases of your own as required. Use

informative Javadoc-style comments as well as inserted comments to further explain your code.

• In addition to the required .java files, you may also submit a file a1sol.pdf in which you provide

further explanations and illustrations (particularly pertaining subtle parts of your codes) to help

the reader better understand the underlying ideas behind your codes. It may also include (by

cut-and-paste) output results of your programs for each of the 3 problems.

1

Problem 1 (25 points): Squeeze an array:

Implement the squeeze() method in the provided ArraySqueeze class so that it performs as

indicated in the comment. The main() method in this class runs some test cases on squeeze(). You

should also add a few nontrivial and interesting test cases of your own at the end of main().

Problem 2 (35 points): Longest plateau:

Consider a non-empty int array ints. A contiguous subarray ints[ start .. start + len -1 ] (with

starting index start and length len) is called a flat if all elements of that subarray are equal.

Furthermore, such a subarray is called a plateau if it is flat and each of the elements ints[start -1]

and ints[start + len] that immediately proceed/succeed the subarray are either nonexistent (i.e.,

out of array’s index range) or are strictly smaller than the elements of the subarray. Your task

includes the design of a public static method longestPlateau(int[] ints) that returns (a compact

description of) the longest plateau of the input array ints. You may break ties arbitrarily if ints has

more than one longest plateau. The return type should be a 3-element array representing { value ,

start , len } : The first indicates common element value ints[start] of the plateau, the second its

starting index, the third its length.

Implement the longestPlateau() method in the provided ArrayLongestPlateau class so that it

performs as indicated. The main() method in this class runs some test cases on longestPlateau().

You should also add a few nontrivial and interesting test cases of your own at the end of main().

2

Problem 3 (40 points): Overlap/enclosure counts of windows:

Given an array of windows in the plane, we want to count how many overlapping and how many

enclosing pairs of windows there are (without double counting).

A window is the region of the plane enclosed by a rectangle with sides parallel to the x and y axes.

A window can be abstracted as an object with the 4 fields of doubles: (left, right, bottom, top).

These fields should satisfy the invariant: left < right and bottom < top. The window is the

Cartesian product of the x-interval [left, right] and the y-interval [bottom, top], i.e., the set of

points (x,y) in the plane such that left < x < right

and bottom < y < top .

Consider a pair of windows w0

and w1

. We say these two windows overlap if they have a common

interior point (just touching boundaries is not enough). We say w0

encloses w1

if no part of w1

is

outside w0

. (Note that the first relationship is symmetric but the second is anti-symmetric.)

Design a class called Window with the following fields and methods:

(Note: you should not confuse this with the Java API class java.awt.Window.)

• Protected fields left, right, bottom, top.

• A constructor that throws an exception named InvalidWindowException if the given 4 fields do

not satisfy the above invariant.

• Public getters and setters for these fields. The setters also throw InvalidWindowException if

invalid field value is attempted to be set.

• Boolean instance method encloses(Window w) returns true if and only if the instance window

encloses the argument window w.

• Boolean instance method overlaps(Window w) returns true if and only if the instance window

overlaps the argument window w.

• Static method overlapCount(Window[] windows) returns the number of (unordered)

overlapping pairs of windows in the input array windows.

• Static method enclosureCount(Window[] windows) returns the number of (ordered)

enclosing pairs of windows in the input array windows.

• main() method runs some interesting test cases of the above methods.