CS 261 Homework 1 - LetterSet

Due Mon Jan 27 at 11:59pm

Overview

This short assignment will help you refresh some of your Java basics, and give you a chance to practice working with the Eclipse IDE. Your task is to create a Java class that represents a "bag of letters". This class will keep track of the number of occurances of each particular letter in the set--so the word "banana" would have 3x 'a', 1x 'b', and 2x 'n'.

This assignment should be completed individually.

Objectives

To review some topics (arrays, loops, searching, etc) from CS 161
To practice creating Java data structures
To practice reading and producing code documentation
To become more familiar with the Eclipse IDE

Necessary Files

You will be creating your own program from scratch for this assignment---select "New > Java Project" from the File menu to create a new project.

You will need to download a copy of the README.txt (right-click on the link and select "Save Link As" to download the file) to fill out and turn in along with your assignment.

Assignment Details

Read through all of these instructions carefully before you begin!
Your task is to create a new class called LetterSet that will represent a set of letters. Your class should have the following public interface:
- LetterSet(String data)
  Constructs a new LetterSet object that represents the alphabetic letters in the given string (ignoring the case of letters and ignoring any non-alphabetic characters).
- LetterSet()
  Constructs a new empty LetterSet object (all letters have count of 0).
- int getCount(char c)
  Returns a count of how many of the given letter (ignoring case) are in the set.
- void setCount(char c, int num)
  Sets the count of how many times the given letter (ignoring case) appears in the set.
- int size()
  Gives the "size" (the number of total letters) in the set.
- boolean isEmpty()
  Returns whether or not the set is empty (has no letters in it).
- String toString()
  Returns a String representation of the set. The letters should be listed in order, without spaces, inside curly braces. For example, an inventory of 3 a's, 1 b, 2 n's would be represented as "{aaabnn}".
- LetterSet add(LetterSet other)
  Returns a new LetterSet object that represents the "sum" (the union) of this and the given LetterSet. This is like we put all the letters in the same bag--the new LetterSet has the sum of the counts of each individual letter.
- LetterSet sub(LetterSet other)
  Returns a new LetterSet object that represents the "difference" (the complement) of this and the given LetterSet. This is like we removed a set of letters from the bag--the new LetterSet has letter counts that are the current counts minus the counts of the other set. If any of the letter counts would be negative (so the parameter cannot be subtracted), this method returns null.
- char[] mostFrequent()
  Returns an array of the most frequently appearing letter(s) in the set. Note that this array will usually be of length 1, but may be longer if there is a 'tie'. If the set is empty, the returned array will have length 0.
  - Advice: this can be a challenging algorithm to implement, though it is based on a "king-of-the-hill" search. Try to think it through on paper before you implement it.
You should include full JavaDoc comments for each method you create--be sure and include proper @param and @return tags.
- Also include plenty of inline comments--remember to explain the why of the code, not the what!
Note that this is the public interface. Your are welcome to create whatever private methods or variables you may need (following good programming style of course).
- You should implement this class so that the methods are as effieicnt as possible. This means you should use an array, rather than an ArrayList (we'll talk about efficiency more as we go). Similarly, you'll want your size() method to be fast--keep track of the Set's size as an instance variable (whenever the size changes), rather than needing to calculate it whenever size() method is called.
You should look at the built-in Character class--it has static methods that could be particularly helpful (like toLowerCase). But remember not to use the wrapper class for actual computation--instead you should use the char data type.
- Fun and useful fact about chars: the char primitive can be cast to an int, the same way a double can be. chars are cast to a number representing their Unicode value--which gives an integer representation of the letter (for example, if we had 'a' == 1, 'b' == 2, 'c' == 3, etc). Note that the Unicode value of 'a' is not 1; you can instead find out the ASCII value of 'a' by casting to an int. By subtracting this value from the int value of a letter, you can effectively treat the value of 'a' as an offset which will let you convert letters into numbers such that 'a' == 0, 'b' == 1, etc.
  - Remember to use CONSTANTS rather than "magic numbers" for things like offsets!
  - This also means that you can compare letters using < and >, in the manner you'd expect!
I recommend you write your own testing class (LetterSetTester) to test and debug your program and make sure it works. You are not required to turn in this testing class.
Finally, be sure to complete the README.txt file and upload it along with your program!

Submitting

BEFORE YOU SUBMIT: make sure your code is fully documented and functional! If your code doesn't run, I can't give you credit!

Submit your program to the Hwk1 submission folder on hedwig, following the instructions detailed in Lab A. You will need to connect to the network drive to do this. Make sure you upload your work to the correct folder!. You should upload your LetterSet.java file, and the completed README.txt.

The homework is due at midnight on Mon Jan 27.

Extensions

A good practice exercise would be to write an interactive tester--a program that lets the user input words (via the Scanner) and then displays the Letter Sets. You can also give the user the option to manipulate LetterSets--for example, to create new ones and add or subtract them.

Can you write a simple program using this class to check if two words are anagrams of each other? Think about what will happen if you subtract their LetterSets!

Grading

This assignment will be graded based on approximately the following criteria:

Your class provides the ten listed methods of the public interface [75%]
Your program is well documented, with complete and proper JavaDoc comments [10%]
Your program demonstrates reasonable efficiency [5%]
Your program includes good programming style (variable naming and usage, etc) [5%]
README is completed [5%]