There are two problems in this homework.

Problem A

The WordBag we developed in class maintains a multi-set of strings. The class implementation uses two fields, the array myArray for remembering string-frequency pairs, and the int numWords for remembering the number of distinct strings.

For example if the multiset currently consists of the strings alice, bob, joe, and jack with frequencies 4, 3, 1, and 1, respectively, then numWords equals 4, and the first four entries of myArray may be (references to) MyWord objects corresponding to the pairs (jack,1), (alice,4), (joe,1), and (bob,3)

In this assignment, we want to change the implementation of the class so that the array locations myArray[0], myArray[1], ..., myArray[numWords - 1] store the MyWord objects in decreasing (non-increasing) order of frequency. In the example, this would mean having myArray[0] correspond to (alice,4), myArray[1] correspond to (bob,3), and the next two array locations correspond to (jack,1) and (joe,1). The order of these last two MyWord objects is unspecified because ties in frequency can be broken arbitrarily.

Give new implementations of the public methods in the WordBag class accordingly. (5 points)

Problem B

In the lectures, we discussed a class, SLinkedList, which, from the perspective of the user, is an ordered list of string elements. In designing the code for the class, we used a linked list implementation.

In this assignment, you should add the correct code for two public methods of the class SLinkedList:

  1. A method public void addLast(String s), by which the user can add string s to the end of the list.
  2. A method public boolean contains(String s) which returns true exactly when string s is in the list.

You do not have to write the code for the removeLast method. The SLinkedList class with the code for some of the other methods of the class can be found here, along with the Node class that it uses. Do not modify the Node class, or any existing methods and fields of the SLinkedList class. The things you are allowed to do are (a) write and modify the body of the two methods above as needed, and (b) add new private fields or methods to the SLinkedList class if you need to do so. (4 points)

Submission Instructions

The source code for this homework needs to be submitted into a dropbox called Homework3 in ICON. You will receive 1 point for preserving the package, class, and file names I have used. The homework is due Monday, September 30, at 11:59 pm.