Solution for HW 4, CS 3114, Summer 2016
------------------------------------------------------------------------------------
Q1:
      a    b    c    d    e    f    g    h    i    j    k   node added / distance
    --------------------------------------------------------------------------------
      0    x    x    x    x    x    x    x    x    x    x
     add   6*   x    x    5*   x    x    8*   x    x    x      a /  0
           6    x    x   add   8*   x    6*   x    x    x      e /  5 
          add   x    x         7*   x    6    x    x    x      b /  6
                9*   x         7    x   add   9*   x    x      h /  6
                8*  13*       add  14*        9   10*   x      f /  7
               add  10*            14         9   10    x      c /  8
                    10             14        add  10    x      i /  9
                    add            12*            10   16*     d / 10
                                   11*            add  14*     j / 10
                                   add                 14      g / 11
                                                       add     k / 14
    --------------------------------------------------------------------------------


Q2:

   Pass 1:
        a --> b --> c --> d --> k   add k
                      backtrack     add d
                 backtrack          
                    c --> g         add g
                 backtrack          add c
          backtrack                 add b
    backtrack
        a --> e                     add e
    backtrack                       add a

   Pass 2:
       f                            add f
   Pass 3:
       h --> i --> j                add j
         backtrack                  add i
    backtrack                       add h
              

   Ordering from first-done to last-done:  

                      h, i, j, f, a, e, b, c, g, d, k


Q3:
   a) Begin by factoring the integer.  Then search the list for each factor.  This
      searching would obviously be faster if the list were sorted.  In fact, it would
      be better than #factors * log N, since we would shorten the search list at each
      step.

   b) Here we can compute multiples of the given integer, and searching the list for
      each of those.  If the list is sorted, we know the maximum element, which tells
      us the largest multiple we must consider.  Otherwise, it's basically the same
      cost as the previous part.

   c) If the list is unsorted, we'd have N /2 strings whose reversals would need to be
      searched for.  That looks like N^2 if the list is unsorted and N log N if it is
      sorted.

   d) If we store the reversed strings in sorted order, then it takes log N time to see
      if the suffix matches the beginning of any string.

   e) And once more, sorting improves performance.  IF the list is sorted, we can do this
      in N steps.


Q4:  The idea is this:  walk indices from both ends toward the middle,
                        when the left index finds a 1 and the right index finds a 0
                             flip them
                        stop when the left index reaches the right index

     This will examine each element in the list exactly once, and never reset (or move)
     any element more than once.  Note there's no need to swap since there are only two
     possible values.