CS 335-0. Programming assignment 5.

Assignment Handout (pdf)

Inputs:

M Go Blue    2 Word Phrases

101 Dalmations! 2 Word Phrases

Al.Gore.ISM   3 Word Phrases

Hints

FAQ.

17. I am having trouble grasping how to process inputs of more than 1 word, because the dictionary only contains single words and not phrases. Are we supposed to separate it using find() into different strings, word1, word2, etc. permutate each one and look each one up in the dictionary? I see how next permutation would work with multiple words but not how the binary search could manage more than 1 word.

1. You treat phrases the same way as single words. Remove all non-alphabetic characters (including spaces) and then form permutations of this set. See the example on the assignment page: "Toy Boat".

17. My program is taking a long time (hours). How long should it take?

1. Each data set should be processable in 15 minutes or less. { my longest one was 2 minutes 15 seconds. }

Some things to consider/try:

• pass containers by reference (or const reference) when possible.
• use binary_search to search your dictionary container
• Store only data you need later ( example: you don't need to store the permutations, just the valid anagrams)
• Eliminate un-necessary I/O
  • read the dictionary file once - into a container
  • remove 'debug' couts for production runs
• Use Compiler Optimization flags:
• g++ -O3 p5.cpp // that is an 'OH', should generate slightly faster code
• Test your code (w debug statements) on small input to see where your program is spending its time