## Abstract

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

### Resources

• Lecture Slides & Presentation

• Book Notes

• Assignment

### 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.