CS 314 – Specification 7 – Anagrams
Programming Assignment 7 Individual Assignment. You must complete this assignment on your own. You may not acquire from any source (e.g. another student or an internet site) a partial or complete solution to a problem or project that has been assigned. You may not show another student your solution to an assignment. You may not have another person (current student, former student, tutor, friend, anyone) “walk you through” how to solve an assignment. You may get help from the instructional staff. You may discuss general ideas and approaches with other students but you may not develop code together.
- Placed online: Tuesday, March 23
- 20 points, ~2% of final grade.
- Due: no later than 11 pm, Thursday, April 1(no fooling)
The purposes of this assignment are:
- to use various data structures
- to implement a program that uses multiple classes
- to implement a recursive backtracking algorithm
Thanks to Stuart Reges for sharing this assignment with me.
In this assignment you will implement several classes that allow a user to find anagrams of words and phrases they type in.
Summary: An anagram is formed by taking all of the letters in one word or phrase and scrabbling them to form a new word or phrase. All of the letters from the original word / phrase must be used and no letters can be added. The new word or words must be valid based on some dictionary. For example an anagram of the phrase “
Isabelle Scott” is
See the guide below for suggestions on how to complete the assignment.
|Source Code||AnagramMain.java The driver program for the completed anagram solver.||Provided by me. Do not alter except for printing out time results if you would like.|
|Source Code||LetterInventory.java A class that represents a collection of letters from the English alphabet. You must add the standard header with your information and the academic honesty statement. Failure to do so will cause you to lose points on the assignment.||Provided by you.|
|Source Code||AnagramFinderTester.java. A class with tests for the LetterInventory and your AnagramSolver classes. Add at least 2 tests per public method and the constructor in LetterInventory.java. (Delete the provided tests after you are sure you code passes them.)The tester requires the d3.txt file for the dictionary and this file with the expected results.
Here is the expected output of the tester without the anagrams shown and with the anagrams shown. You times will vary. Any of the given tests that complete in less than 0.2 seconds should take less than 1 second on the CS department machines. Any of the given tests that take >= 0.2 seconds should take no more than 5X my time when run on the CS department machines.
It is up to you to explore various approaches to try and speed up your algorithm. There is no one right way to do this. It is up to you to try different things. Neither the TAs, nor the instructor, have a “magic answer” that works for all cases. I want to stress this. Don’t come to lab hours expecting us to tell you exactly how to speed up your program. We will give high level suggestions, not detailed advice.
|Provided by me.|
|Source Code||AnagramSolver.java. A class that solves and returns a list of anagrams for a given phrase and maximum number of words.||Provided by you|
|Source Code||Stopwatch.java. A class for calculating elapsed time when running other code. You may use this to see how long it takes to find anagrams and compare results on Piazza.||Provided by me.|
|Dictionary Files||d1.txt A small dictionary file with 56 words.
d2.txt A medium size dictionary file with 3927 words.
d3.txt A large dictionary file with 19911 words.Note, when we test your program, we will use other dictionaries that contain one and two letter words. Do not assume all words in the dictionary will have a length of 3 or greater. There can and will be words of length 1 or 2 in the dictionaries we use to test your solution.
|Provided by me.|
|Sample Output||Sample run of anagram solver using d1.txt. Other than the timing results, your program must match this output given the same input. I have trimmed many of the anagrams for clarity, but when you run AnagramMain it prints out all the result. The output also shows the timing data for the sample solution and the tests in AnagramFinderTester.Here is a run of the anagram solver using d3.txt with all the output.||Provided by me.|
|Submission||Turn in a7.zip with these three files: AnagramFindrerTester.java, AnagramSolver.java, LetterInventory.java.||Provided by you.|
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx