CSC 148H - Assignment #2 - Recursion and Backtracking

Part 1 - Anagram Generator (80%)

This assignment question will give you practice with recursive backtracking. You are to create a class called AnagramSolver that uses a word list to find all combinations of words that have the same letters as a given phrase. You might want to first look at the sample log of execution at the end of this part of the assignment.

Your class must include the following methods.

• A constructor. Takes a list of words, and constructs an anagram solver that will use the given list as its dictionary. It is not to modify the list. You should use this Sample Dictionary when writing your code so that your results will match the sample execution below.
• generateAnagrams. Takes a string s and an integer max, and returns all combinations of words from its dictionary that are anagrams of the String s and that include at most max words (or unlimited number of words if max is 0). Throws an appropriate exception if max is less than 0.

Your generateAnagrams method must produce the anagrams in the same format as in the sample log. In particular, it is to return a list of lists, where each list is an anagram. The easiest way to do this is to build up your answer in a list. Then you can simply append that list to your master list of anagrams.

You are required to solve this problem by using recursive backtracking. In particular, you are to write a recursive method that builds up an answer one word at a time. On each recursive call, you are to search the dictionary from beginning to end and to explore each word that is a match for the current set of letters. The possible solutions are to be explored in dictionary (i.e. alphabetical) order. For example, in deciding what word might come first, you are to examine the words in the same order in which they alphabetically appear in the dictionary.

The low-level details for the anagram problem involve keeping track of various letters and figuring out when one group of letters can be formed from another group of letters. It turns out that the LetterManager class that we wrote for assignment 1 provides us with the low-level support we need.

For any given word or phrase, what matters to us is how many of each letter there are. Recall that this is exactly what the LetterManager keeps track of. In addition, the subtract method of the LetterManager is the key to solving this problem. A Python LetterManager is provided for you to use in this assignment.

Part of your grade will be based on the efficiency of your solution. Recursive backtracking is, in general, highly inefficient because it is a brute force technique that checks every possibility, but there are still things you can do to make sure that your solution is as efficient as it can be. Be careful not to compute something twice if you don’t need to. And don’t continue to explore branches that you know will never be printed. You are also required to implement the following two optimizations:

1. There is no reason to convert dictionary words into inventories more than once. You should preprocess the dictionary in your constructor to compute all of the inventories in advance (once per word). You’ll want fast access to these inventories as you explore the possible combinations. A Python map will give you fast access.
2. For any given phrase, you can reduce the dictionary to a smaller dictionary of relevant words. A word is relevant if it can be subtracted from the given phrase. Only a fraction of the dictionary will, in general, be relevant to any given phrase. So reducing the dictionary before you begin the recursion will allow you to speed up the searches that happen on each recursive invocation. To implement this, you should construct a short dictionary for each phrase you are asked to explore that includes just the words relevant to that phrase. An important efficiency decision you have to make is whether to do this once before the recursion begins, or also on a certain number of deeper levels of recursion. You should experiment with different word lengths, make your decision, and document your reasoning.

Your generateAnagrams function is to produce exactly the same output in exactly the same order as in the sample below. The input s is office key, max is 0, and the output is as follows.

[['eke', 'icy', 'off'],
['eke', 'off', 'icy'],
['ice', 'key', 'off'],
['ice', 'off', 'key'],
['icy', 'eke', 'off'],
['icy', 'off', 'eke'],
['key', 'ice', 'off'],
['key', 'off', 'ice'],
['key', 'office'],
['off', 'eke', 'icy'],
['off', 'ice', 'key'],
['off', 'icy', 'eke'],
['off', 'key', 'ice'],
['office', 'key']]

Download the starter code here: anagram-template.py. You are to implement the constructor and the generateAnagrams method in this file. Do not modify the header definitions for the generateAnagrams method or the constructor. You are free to add any helper functions or any other code that you feel that you need.

For this part of the assignment, you should submit your AnagramSolver class. You should also submit a text document that outlines your design decisions, and a Python file containing: Nose tests, why you felt each test was necessary, and why you feel your test cases are sufficient to conclude that your implementation is correct.

Part 2 - Binary Tree Representations (20%)

For this part of the assignment, you are to create a Python function ll2nr that takes a list of lists representation of a binary tree and converts it to an equivalent binary tree in nodes and references form. Your function should return a binary tree object of the class in nodesrefs.py (do not make any changes to this file). Your ll2nr is required to be recursive (an iterative algorithm is not allowed). You should submit just one Python file containing your ll2nr function. You should start with ll2nr-template.py and add your code for the method. Do not modify the function header. You are free to add any helper functions or any other code that you feel that you need.

Marking