CMSI 2120

Classwork 7 - Priority Hashing

6 min read

Definition

[Bonus Classwork] This class work is a bonus exercise! Not completing it won’t hurt you, but completing it (correctly) will net you a bonus +6 Homework Points on a single assignment!

In this classwork, we’ll get some practice using JCF Maps and PriorityQueues! You’ll use the both quite a bit in your future classes, so better to master them now!

GitHub Classroom + Skeleton

Definition

Start with the solution skeleton in-hand! The following will also serve as your submission mechanism (see submission instructions below).

Assignment

Classwork 7 - GitHub Classroom

Specifications

Recall our solution to Classwork 2 (how long ago it feels!) counting the number of unrepeated words.

package senttools.solution;
 
/**
 * Simple library which might (outside of this assignment) contain
 * various functions related to some sentence tools.
 */
public class SentTools {
 
    /**
     * Returns the number of unique, unrepeated words that are found
     * in the given sentence sent
     * NOTE: This solution is not very good!!! It can be simplified
     * by using ArrayLists, but even those aren't the best choice here!
     * @param sent The sentence in which to count unique words
     * @return The number of unique, unrepeated words in sent
     */
    public static int uniqueWords (String sent) {
        String[] words = sent.split(" ");
        String currWord, compWord;
        int count = 0;
 
        // Compare each pair of words (again, warning: not great)
        for (int i = 0; i < words.length; i++) {
            boolean repeatFound = false;
            currWord = words[i];
            if (currWord.equals("")) { continue; }
 
            for (int j = 0; j < words.length; j++) {
                compWord = words[j];
                if (currWord.equals(compWord) && i != j) {
                    repeatFound = true;
                    break;
                }
            }
 
            // Only increment the count for the first occurrence of each match
            count += (repeatFound) ? 0 : 1;
        }
 
        return count;
    }
 
}

Definition

Your task: rewrite this method using HashMaps to turn the current (O(n^2)) solution into one that operates in (O(n))!

Toolkit

Complete the uniqueWords method stubbed in the /src/senttools/SentTools.java in the skeleton.

Here’s your chance to feel like you’ve really grown as a programmer, which (central to this class) involves choosing the right tool for the job!

Before tackling the above, you should read through the following:

  • HashMap Documentation: check out the HashMap Javadocs to learn the methods available to you!
  • How to Iterate over a Map’s Key-Value Pairs: although not a typical requirement, sometimes we need to iterate over all of the key-value pairs stored in a Map; here’s the best way: StackOverflow on Iterating over Maps.

As a second sentence-related tool, suppose we’re interested in determining the most frequently appearing words in a sentence, but we don’t need a complete decomposition of all words and their frequencies.

Instead, suppose we want to request the k most commonly appearing words in a sentence, which can be done very efficiently using a Priority Queue!

As such, for this problem…

Definition

Your task: implement the Map<String, Integer> kMostFrequentWords(String sent, int k) that takes in a sentence of space-separated words, sent, and the number of most frequently occurring words to return, k, and returns a Map of k String keys (the most frequent words) mapped to the number of times they appear in the sentence.

Debug

The catch: your solution must use a PriorityQueue and accomplish the above in (O(n * log(k))) runtime for n words. (Since k is a constant, this is really (O(n)), but we’ll leave the (log(k)) as a hint for the implementation).

Example

Here are some example calls to this method; we’ll represent the conceptual contents of a map as {key1: value1, key2: value2, ...}

kMostFrequentWords("A A A B B C", 1);
=> {"A": 3}
 
kMostFrequentWords("A A A B B C", 2);
=> {"A": 3, "B": 2}
 
kMostFrequentWords("A A A B B C", 3);
=> {"A": 3, "B": 2, "C": 1}
 
kMostFrequentWords("A A A B B C", 4);
=> {"A": 3, "B": 2, "C": 1}

Some notes on the above:

  • If k is greater than the number of unique words in the (as in the above example with k=4), we simply return a map with as many words as there are unique ones in the given sentence. DO NOT worry about handling this case specially, NOR calling your uniqueWords method above — in the correct solution, this shouldn’t be a problem.
  • In the event that the provided String is empty, simply return an empty map.
  • For the purposes of testing the correctness of this assignment, you may assume that there will never be two words with the same frequency in the input sentence; in general, it would likely not matter which words that tied for highest frequency were returned.
  • Here are some suggested steps for completing this method:

    1. Create a helper responsible for creating a Map of all of the words in a given sentence to their frequencies. Hint: you might also use this in the uniqueWords method.

    2. Complete the provided WordCounter helper class that represents pairs of Words mapped to their Frequencies by implementing its compareTo method to be consistent with the Comparable interface’s expectations.

    3. In kMostFrequentWords, iterate over the entries in the map created using your helper in step 1, creating a new WordCounter that is then stored in a PriorityQueue of WordCounters. These will be “prioritized” by however you specified the compareTo method in step 2.

      Debug

      Importantly: the size of your PriorityQueue should not exceed k.

      That bound is what gives the asymptotic runtime guarantee above!

    4. If done correctly, the remaining WordCounters in your PriorityQueue will be the k most frequent — just pop these all into a result Map and return!

Debug

The unit tests in the skeleton will test the correctness of your methods, though not necessarily their efficiency — make sure you’re using these new data structures properly by the criteria above — double check your asymptotic analysis to be certain!

Submission

Definition

You will be submitting your assignments through GitHub Classroom!

What

Provide answers to all of the above in the solution skeleton provided!

How

To clone this assignment (if you need a refresher), consult the guide here:

Assignment

GitHub Classroom Tutorial

To submit this assignment:

  • Simply push your final, submission copy to the GitHub Classroom repository associated with you or your group.
  • If you worked in a group (3 individuals maximum), ensure that your GitHub Classroom group includes all members, and place all group members’ names at the top of all submitted files (in appropriate JavaDoc commenting fashion) AND in the accompanying readme file.

Graph View

Backlinks