Implementation Challenges

 

1. (*) Anagrams are rearrangements of the letters of a word or phrase into a different word or phrase. Sometimes the results are quite striking. For example, ``MANY VOTED BUSH RETIRED'' is an anagram of ``TUESDAY NOVEMBER THIRD,'' which correctly predicted the outcome of the 1992 U.S. presidential election. Design and implement an algorithm for finding anagrams using combinatorial search and a dictionary.
2. (*) For any of the exercises above, design and implement a simulated annealing heuristic to get reasonable solutions. How well does your program perform in practice?
3. (**) Design and implement a parallel sorting algorithm that distributes data across several processors. An appropriate variation of mergesort is a likely candidate. Measure the speedup of this algorithm as the number of processors increases. Later, compare the execution time to that of a purely sequential mergesort implementation. What are your experiences?