There are two problems in this homework.

Problem A

Earlier in this course, we wrote a WordBag class for maintaining a bag (multiset) of strings. To implement the class, we used an array of MyWord objects called myArray. (In later homeworks, we wrote different classes with the same functionality.) In this problem, you should implement a class called HashMapWordBag, a stub of which is given here. HashMapWordBag should have the same functionality as WordBag, that is, support the same public methods. (One minor difference is that HashMapWordBag has only one constructor, a zero-parameter one.) The signatures of the constructor and the public methods that HashMapWordBag should support are included in the stub.

Your implementation of HashMapWordBag should use hm, a HashMap object for storing key-value pairs with String keys and Integer values. If our current multiset is {Alice, Bob, Alice, Joe, Alice}, hm should store the key-value pairs (Alice,3), (Bob,1), and (Joe,1).

A few notes on your implementation:

For each method of HashMapWordBag, estimate its worst case and "average" case running times as a function of n, the number of distinct words in the bag. For this, you can assume that checking string equality and evaluating the hashcode function on the string keys takes constant time. Write the running times as comments accompanying the corresponding methods.

This problem is worth 7 points

Problem B

Write a method haveCommonElements from here that takes as input two ListIterators on two Lists of Integers, and returns true if and only if the two lists have a common integer. Assuming the two Lists have size n, write the running time of this method as a comment to the method. (3 points)

Submit the source files into a dropbox in ICON called Homework7. This assignment is due by 11:59 pm on Wednesday, November 20.