Princeton Algorithms: Part 1, Week 3

Resources

• Lecture Slides & Presentation

  • 2.2 — Mergesort
  • 2.2 — Demo Merge

• Book Notes

  • 2.2 — Mergesort

• Assignment

  • Problem Description
  • Assignment Checklist
  • Files

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