• Introduction
• Problem 1: Flight
• Comparators & Lambdas
• Your Task
• Problem 2: Rabin-Karp Algorithm (Extra)
• Your Task
• Submission

Introduction

In this lab, you’ll be working with heaps and hashing. You will only need to complete the first problem to get credit, but we added the second question to give you some practice with using APIs and help you see practical applications of hashing!

Problem 1: Flight

Imagine that we have a list of every commercial airline flight that has ever been taken, stored as an ArrayList. Each Flight object stores a flight start time, a flight ending time, and a number of passengers. These values are all stored as ints.

Each flight’s start time and end time represents the number of minutes that have elapsed in the Pacific Time Zone since midnight on January 1st, 1914, which was the first day of commercial air travel.

For example, a flight taking off at 2:02 PM on March 6th, 1917 and landing at 3:03 PM the same day carrying 30 passengers would have takeoff time 1,671,243, landing time 1,671,304, and number of passengers 30.

Implement an algorithm for finding the largest number of people that have ever been in flight at once.

Your algorithm must run in \(\theta(N\log N)\) time, where \(N\) is the number of total commercial flights ever taken. Your algorithm must not have a runtime that is explicitly dependent on the number of minutes since January 1st, 1914, i.e. you can’t just consider each minute since that day and count the number of passengers from each minute and return the max.

Your algorithm may use any data structure that we’ve covered thus far, though we recommend doing it with a java.util.PriorityQueue.

Comparators & Lambdas

You may need to use comparators in your solution for comparing objects. You can construct a concrete class (which can be somewhat verbose) or use lambda functions instead. The syntax for declaring a lambda for a comparator is:

    Comparator<Type> function = (Type arg1, Type arg2) -> (...);
    Comparator<Type> functionEquivalent = (arg1, arg2) -> (...);

where (…) is your desired return value that can use arguments arg1 and arg2.

Examples:

        Comparator<Integer> intComparator = (i, j) -> i - j;
        Comparator<Integer> intComparatorEquivalent = (i, j) -> {
          int diff = i - j;
          return diff;
        };

You may also want to look into the function Integer.compare. Note: lambdas will not be in scope for this course (i.e. not tested).

Your Task

Write the class FlightSolver that has the following methods:

• FlightSolver(ArrayList<Flight> …): Constructor that takes in an ArrayList of Flight objects as described above.
• public int solve(): Returns the solution to the problem described above.

Problem 2: Rabin-Karp Algorithm (Extra)

The Rabin-Karp algorithm is a string-searching algorithm that “uses hashing to find any one of a set of pattern strings in a text”. One practical application is detecting plagiarism. The algorithm takes \(\theta(n+m)\) time, for text of length \(n\) and a pattern string of length \(m\).

Your Task

• Use the provided RollingString methods to implement the Rabin-Karp algorithm in the RabinKarpAlgorithm class. Check out the Wikipedia article for more information (i.e. psuedocode). Note that the staff implementation is case-sensitive.

  • Some Tips
    • Make sure to actually use the provided methods.
    • Be careful about the indices!
    • If the user inputs are invalid (i.e. the pattern length to match is longer than the string itself), return -1.
    • Your solution won’t work before you implement the RollingString class.
  • Then, finish implement the RollingString class according to the descriptions above each method. Make sure to implement all the necessary functions. Do not change the UNIQUECHARS and PRIMEBASE attributes, and make sure to use them in your solution. Convert chars to integers by casting them to ints.
    • Let \(c_i\) denote the \(i\)th character from the right (0-indexed) and \(n\) be the length of the string. The hashcode should be: \(h = (\sum_{i=0}^{n-1} c_i * \text{UNIQUECHARS}^i) \mod \text{PRIMEBASE}\).
    • It is up to you to figure out how to compute the hashcode in constant time as we add characters to the String.

Submission

Submit your solution to part 1 (and optionally part 2) to Gradescope.