Data Structures Lab#3 Solution

Description

Instructions

An anagram is a permutation of the letters of a word to produce another word. The method

print_anagrams shown below (adapted from Carl Burch’s book Programming via Java) prints all

the anagrams of a given word. To do this, it generates all permutations of the letters in the word

and, for each permutation, it checks if it is a valid word in the English language. For example, if

you call print_anagrams(”spot”), the method should print the following words: spot, stop, post,

pots, opts, and tops

“`python

def print_anagrams(word, prefix=””):

if len(word) <= 1:

str = prefix + word

if str in engish_words:

print(prefix + word)

else:

for i in range(len(word)):

cur = word[i: i + 1]

before = word[0: i] # letters before cur

after = word[i + 1:] # letters after cur

if cur not in before: # Check if permutations of cur have not been generated.

print_anagrams(before + after, prefix + cur)

“`

The method uses a data structure called engish_words to determine if a given anagram is a

valid word in the English language. You can think of engish_words as a container of all the

words in the English language. We will implement this data structure using a binary search tree.

To populate engish_words, we will use a text file called words.txt that contains 354,984 English

words. You can download words.txt from the following URL:

https://github.com/dwyl/english-words/. Once you have downloaded words.txt, write a function

that reads the file and populates the binary search tree with all the English words contained in

the file. Ask the user what type of binary search tree he/she wants to use (AVL Tree or

Red-Black Tree). You are free to use the implementation provided in your zyBook for these two

types of trees. Adapt zyBook’s code to include the word and make it the key.

Write another function called count_anagrams that does not produce output, but returns the

number of anagrams that a given word has. For example, count_anagrams(”spot”) should return

6. Finally, write another function that reads another file that contains words (feel free to create it

yourself) and finds the word in the file that has the greatest number of anagrams.

What you need to do

Part 1

Implement the program described above, and upload your code to GitHub.

Part 2

Add your team members as collaborators to your GitHub repo. They will add you to their

projects as a collaborator as well. Read their code and give them feedback. Use pull requests

and/or the Issues section to do so .

Extra Credit

Re-do the lab using a B-Tree, run multiple experiments using different values for the degree of

the tree, and include in your report how performance changes as the degree varies. Finally, use

tables and graphs to compare B-Trees with AVL and Red-Black trees.

#   Run the file “english.py”