Abstract

Usage and demonstration of the performance and effectiveness of essential data structures, generics, collections, and elementary sorting algorithms

Table of Contents

Resources

Programming Assignment

Brute Collinear Points Implementation

Implemented using an algorithm that found all of the combinations (N choose 4), not the permutations (number of tuples is N^4), and then found the line segments by iterating through the combinations. Used Java’s built-in Array utilities to naturally sort the points and to copy arrays as needed to maintain idempotency of certain operations.

Fast Collinear Points Implementation

Implemented FastCollinearPoints using the recursive Mergesort algorithm from the lecture slides. Implemented said algorithm using an auxiliary array. Didn’t use a cutoff to insertion sort when the sort array hit a certain size (7 was recommended) nor did I use a check to see if the sort array was already sorted. Decided that the improvements weren’t necessary since all performance requirements were met.

To decide if to add a found line segment, I compared the first point in the found line segment to the base point. If the two were equal, then I added the line segment. This ensured that a line segment was only added once while also not needing to check Point coordinates or the composition of existing line segments.

Point Implementation

Implemented a compareTo() method for a natural sort and used that method in a Comparator private class which was returned by the slopeOrder() method. Implemented a slopeTo() method to calculate the slope of two points.

Results

Collinear Points Grade

Fast Collinear Points Tests

Brute Collinear Points Tests

Point Tests