## Abstract

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

## Table of Contents

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