Lab 07 - The Collections Framework

Instructions

For each problem, create a class named ProblemX, where X is the problem number (e.g., Problem1.java). Write corresponding JUnit test classes named ProblemXTest. All methods (yes, including helpers) must include proper Javadoc comments describing the (1) purpose of the method, (2) parameters, and (3) return value. Helper methods should be marked as private. You do not need to write explicit tests for helper methods because they will be indirectly tested through the driver methods.

For problems containing multiple parts, write the methods inside the same class.

What You Cannot Use

You may not use anything beyond Chapter 3.2. This includes but is not limited to:

Any violation results in a score of 0 on the lab.

Please contact a staff member if you are unsure as to whether you're allowed to use something.

Notes and Version Changes:

Problems

  1. (40 points) Design the Set<Integer> moreThanN(int[] A, int n) method, which receives an int[] A and an integer n ≥ 1 and returns a new Set<Integer> of values containing those values from A that occur strictly more than n times.

    Note: The output order does not matter.

    Files to Submit: Problem1.java, Problem1Test.java

  2. (60 points) Anagrams are strings that are formed by rearranging the letters of another string. For example, "plea" is an anagram for "leap", but we consider an alphabetized anagram to be the alphabetized arrangement of letters for an anagram. As an example, "aelrst" is the alphabetized anagram for "alerts", "alters", "slater", and "staler". Design the static Map<String, Set<String>> alphaAnagramGroups(List<String> los) method, which maps all alphabetized anagrams to the strings los using the above criteria.

    The output order of the map is significant: it should be alphabetized by the ordering of the strings. (Which Map type should you use?) Additionally, the fact that we map alphabetized anagrams to strings to sets indicates that duplicates do not matter, and that is true.

    The ordering of the sets is significant: it should be the insertion order of the strings. (Which Set type should you use?)

    Use the following test case as an example. 

    
los = ["presorting", "plea", "introduces", "anger", "leap", "petals",
       "donate", "plates", "range", "reductions", "rediscount", "anger",
       "tapers", "pale", "atoned", "staple", "repast", "reportings"]

alphaAnagramGroups(los)
  => {
       {"adenot", ["donate", "atoned"]},
       {"aegnr", ["anger", "range"]},
       {"aelp", ["plea", "leap", "pale"]},
       {"aelpst", ["petals", "plates", "staple"]},
       {"aeprst", ["tapers", "repast"]},
       {"cdeinorstu", ["introduces", "reductions", "rediscount"]},
       {"eginoprrst", ["presorting", "reportings"]}
     }

    Hint: You will need to design a method that creates an "ordered version" of a given string.

    Warning 1: To create the ordered string, you cannot use any Java sorting methods to do this, e.g., Arrays.sort, Collections.sort, and so forth. Think about how you can leverage a PriorityQueue!

    Warning 2: If you only use the test that we give, your "Student Tests" score will be very low.

    Files to Submit: Problem2.java, Problem2Test.java