Solution for HW 4, CS 3114, Spring 2018
------------------------------------------------------------------------------------
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    5    3    1    x    x    x    x    x    x    x            a /  0
           4    2  add    x    x    4    x    x    x    x            d /  1
           3  add         x    7    4    x    x    x    x            c /  2
         add              5    7    4    x    x    x    x            b /  3
                          5    7  add    x    x    x    x            g /  4
                        add    6         7    x    x    x            e /  5
                             add         7    9   12    x            f /  6
                                       add    9   12   10            h /  7
                                            add   10   10            i /  9
                                                 add   10            j / 10
                                                      add            k / 10


Q2:
   Pass 1:
        a --> b --> e --> h
                      <--                 add h
                <--                       add e
          <--                             add b
        a --> c --> d
                <--                       add d
              c --> g --> j --> i --> k
                                  <--     add k
                            <--           add i
                      <--                 add j
                <--                       add g
          <--                             add c
        a --> f
          <--                             add f
    <--                                   add a

    So a solution is:  a  f  c  g  j  i  k  d  b  e  h  
           

Q3:
    a)  Algorithm:
        Sort S into ascending order, alphabetically.
        Traverse S linearly (sorting does not help at this point);
        for each string Z in S, search S for the reversal of Z (sorting
        would allow using binary search here).
        Cost, excluding sorting:
          Theta( N log N) since we do N binary searches on S

    b)  Algorithm:
        Sort S based on the reversals of the strings in S.
        Binary search S for X; a match indicates X is in S, and X is a
        suffix of itself; otherwise the search will either terminate at
        string that has X as a suffix, or at a string that does not have
        X as a suffix.
        Cost, excluding sorting:
          Theta(log N) since we do a single binary search on S

    c)  Algorithm:
        Sort S alphabetically.
        For each prefix of X, binary search S for the prefix; if that is
        found, then binary search S for the rest of X; it that is found,
        we have a match, if not, extend the prefix by one character and
        repeat.
        Cost, excluding sorting:
          Theta( length(X) * log N )

    d)  Algorithm:
        For each string Z in S, perform a substring search for X.  This
        can be optimized by not comparing against strings in S that are
        shorter than X, and one could optimize that by first sorting S
        based on the lengths of strings.
        Cost, excluding sorting:
          Theta( N * cost of substring operation )