Solution for HW 4, CS 3114, Summer 2013
------------------------------------------------------------------------------------
Q1:

      0   1   2   3   4   5   6   7   8   9  10    Current solution set
    ----------------------------------------------------------------------------
      0                                                                
      +   7   x   x   5   x   x   2   x   x   x	 {0}	
          7   x   x   4   8   x   +   5   x   x	 {0,7}
          5   x   x   +   7   x       5   x   x	 {0,7,4}
          +   8   x       6   x       5   x   x	 {0,7,4,1}
              8   x       6   x       +   7   x	 {0,7,4,1,8}
              7  12       +  13           7   x	 {0,7,4,1,8,5}
              +   9          13           7   x	 {0,7,4,1,8,5,2}
                  9           8           +  11	 {0,7,4,1,8,5,2,9}
                  9           +              11	 {0,7,4,1,8,5,2,9,6}
                  +                          11	 {0,7,4,1,8,5,2,9,6,3}
                                              +	 {0,7,4,1,8,5,2,9,6,3,10}


Q2:

   Pass 1:             0-->1-->2-->3-->10
    stack: 10          0-->1-->2-->3         (backtrack)
    stack: 3,10        0-->1-->2             (backtrack)
    stack: 2,3,10      0-->1                 (backtrack)
    stack: 1,2,3,10    0                     (backtrack)
    stack: 0,1,2,3,10                        end DFT pass

   Pass 2:             4
    stack: 4                                 end DFT pass

   Pass 3:             5
    stack: 5                                 end DFT pass

   Pass 4:             6
    stack: 6                                 end DFT pass

   Pass 5:             7-->8-->9
    stack: 9           7-->8                 (backtrack)
    stack: 8,9         7                     (backtrack)
    stack: 7,8,9                             end DFT pass

   Ordering from first-done to last-done:  

                      7, 8, 9, 6, 5, 4, 0, 1, 2, 3, 10


Q3:
   a) The question does not specify whether the words would be stored in an array
      or a linked structure.
		
		If you are given a specific word, say "plum", having the words in a sorted
      list would offer at least a small advantage.  If you generated all 4! different
      permutations of "plum", you could then quickly see whether each of them did
      occur within an array of words.
		
		However, if the question is broader, that is, are there any two words in the
      set that are anagrams of each other, the computational complexity is going to
      be enormous in any case.  Sorting would still reduce the search complexity.

      (This problem can be attacked more efficiently by loading the original strings
      into a more sophisticated structure... see Patricia tries for one idea.)
		
		As usual, if the values were stored in a linked list, having them sorted would
      provide at most a tiny advantage.

   b) As with part a), there are a large number of pairs that must be considered, so
      it would seem this will be expensive in any case.  

      If your approach is to take each pair, compute its sum, and search for that sum
      then efficiency would be enhanced if the list (an array) were sorted.

   c) In this case, we'd just need to perform a search on the list for the given
      specific prefix... if we don't find it, we should still locate the nearest match,
      and any strings that have that prefix will be nearby only if the list is sorted.

      So yes, sorting would improve performance.

   d) For each string S in the collection, if the set is sorted then any string that has
      S as a prefix will be near to S.  Otherwise, we'd have to do a comprehensive search.

      Sorting would help tremendously in this case.

   e) The multiples of a divisor would not necessarily be close to each other, so sorting
      would not seem to offer any advantage in that regard.

      If the list were sorted, we could generate all multiples of the given divisor that
      lie between the smallest and largest elements of the list, then use a binary search
      to see if any of those were present.  However, unless the number of multiples was
      very small, it would be more efficient to just do a O(N) linear traversal.

      So, sorting could help undeer special conditions.


Q4:  I'll discuss this one in class...