CSE 143: Computer Programming II, Autumn 2015

Homework 5 (Anagrams) FAQ

Q: I'm having a hard time with recursive backtracking. What should I do?

A: Take advantage of the examples we've seen in lecture and in section. In particular, take some time to understand the permutations and 8-queens examples from lecture. Notice how the eight queens problem stops after finding one possible solution, but the permutations example finds all possible solutions, like your program should. From the section handout, subsets, make-change, and sum-of-squares are some especially applicable methods. There are also some notes on recursive backtracking by Stuart Reges, available on the lecture section of the website.

Q: How does a LetterInventory work?

A: The LetterInventory is a very useful structure that keeps track of how many of each letter a given String has (ignoring whitespace, capitalization, and non-alphabetic characters). Each LetterInventory object has many methods for retrieving or modifying its properties. They include:

• Does this LetterInventory have any letters in it? (isEmpty)
• How many letters does this LetterInventory have? (size)
• Does this LetterInventory have the right letters to make a certain word? (contains)
• What are all of the letters in this LetterInventory, in alphabetical order? (toString)
• Keep track of this word, too. (add)
• Stop keeping track of this word. (subtract)

Notice that add, subtract, and contains all work with either a String or a LetterInventory.

Q: How am I supposed to get print to print no more than a certain number of words?

A: This is a harder aspect of this assignment, so you shouldn't tackle it first. Get your print method working so that it will print all appropriate anagrams regardless of how many words long they are. Once you have handled this somewhat easier problem, then take a look at only outputting the anagrams with no more than max words.

Q: Should print keep looking for anagrams once it exceeds max?

A: No. It is inefficient for your code to keep running down paths once you know that they won't yield a viable solution.

Q: We've learned that recursive backtracking often involves examining all combinations of a set of choices. In this problem, the choices are the words that can be formed from the phrase. Should my program consider every word in the original dictionary as a possible choice?

A: No. There is no need to spend time examining words that couldn't even be made using the original phrase. First, find a collection of words from the dictionary that can be made using the phrase. Then, use these possibilities as your "choices".

Q: Should we only output anagrams that use up all of the letters in the given word/LetterInventory?

A: Yes. The writeup explains, "An anagram is a word or phrase made by rearranging the letters of another word or phrase". For example, [love, lace] would not be an appropriate anagram for the string Ada Lovelace because it doesn't use the letters ada.

Q: How can I tell if my program is finding all of the correct anagrams?

A: Testing! Just like always, it's best to start small and then work your way up from there. Start off by using dict1.txt as your dictionary since it's small enough to check which of the words can be made from a given phrase just by looking at it. Once you've convinced yourself that your program works with this small dictionary, you should move on to the larger ones. The Output Comparison Tool on the Homework page of the course website shows output for various phrases from various dictionaries. Make sure to take advantage of this valuable resource! Remember that the tests from the comparison tool are not exhaustive, but it's a good place to start.

Q: How do I debug my recursive method?

A: Try using System.out.println to find out what the anagram looks like at certain points in your program. Try before and after your recursive step as well as in your base case. You might also find the debugger in jGRASP useful.

Q: My recursive method is really long and icky. How can I make it cleaner?

A: Start off by making sure you can identify the base case and the recursive case clearly. You want to practice recursion 'zen' by not burying your base case in your recursive method. Make sure you're not making any needless or redundant checks inside of your code.

Q: How can I make sure I get the best grade possible on this (or any) assignment?

A: The writeup is the key! It usually has all of the details of how your program should behave, what subtle cases you should make sure to cover, and anything else you might need to know to complete the assignment successfully. Use it like a checklist before, during, and after you do the assignment to make sure you do everything correctly.