Solution for HW 4, CS 3114, Spring 2017
------------------------------------------------------------------------------------
Q1:
      a    b    c    d    e    f    g    h    i    j    k      node added / distance
    --------------------------------------------------------------------------------
      0
    add    5    x    x    4    x    x    2    x    x    x      a    0
           5    x    x    3    8    x  add    5    x    x      h    2
           4    x    x  add    6    x         5    x    x      e    3
         add    7    x         5    x         5    x    x      b    4  
                6   11       add   12         5    8    x      f    5
                6   11             12       add    7    x      i    5
              add    8             12              7    x      c    6
                     8              8            add   11      j    7
                   add              8                  11      d    8
                                  add                  11      g    8
                                                      add      k   11
    --------------------------------------------------------------------------------


Q2:

   Pass 1:
        a --> b --> c --> d         prefix d
                    backtrack       prefix c
                backtrack           prefix b
        a --> e                     prefix e
        backtrack                   prefix a

   Pass 2:
       f --> g --> k                prefix k
	            backtrack           prefix g
			backtrack               prefix f
	        
   Pass 3:
       h --> i --> j                prefix j
         backtrack                  prefix i
    backtrack                       prefix h
              

   Ordering from first-done to last-done, following the given rules:  

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


Q3:
   a) Simply make one pass of insertion sort, placing the one unsorted element into
      the correct place.
	  
	  At worst, the "new" element goes in the front of the list, so an insertion sort
	  pass could cost N comparisons and N + 1 copy operations, which is still O(N).

   b) Using log N insertion sort passes could cost N log N, so that won't do...
   
      Apply HeapSort to the unsorted tail; that costs M log M.  Then merge the sorted
	  front part and the sorted tail; that costs N + M.  But is this O(N)?
	  
	  Well, M log M = (log N) log(log N). Is this O(N)?  Yes; taking the relevant limit
	  will verify that.
	  
	  And, N + M = N + log N, which is clearly O(N).
	  
	  So, this procedure is O(N).

   c) The same strategy as used for part b) works here, although the details of the
      verifications differ slightly.
	  
	  Sorting the tail will cost sqrt(N) log(sqrt(N)), and that's O(N).  The merging
	  pass is the same, so that's O(N).


Q4:  
   a) If the list is sorted, all we have to do is compute differences between successive
      elements, and keep track of the smallest sum of two successive differences.
	  
	  If the list is not sorted, it's hard to see how to solve the problem without first
	  sorting it.
	  
   b) If the list is unsorted, we could traverse the list and compute remainders mod 100.
      That would be O(N).
   
      An integer N would be congruent to M mod 100 if and only if N was of the form
      100*q + M for some integer q.  So, once we know what M is, we can compute values
	  that are congruent to M mod 100 (100*0 + M, 100*1 + M, 100*2 + M, etc.).
	  
	  If the list was sorted, we could traverse the list, keeping track of which "century"
	  we are in.  That is, are we in the range [0, 99), [100, 199), etc.  For each such
	  "century", we only need to watch for the occurence of one specific value; for
	  example, if we are between 700 and 799, we only need to watch for 700 + M.
	  
	  This is still O(N), but it doesn't require computing a remainder for each of the
	  values in S, so the arithmetic would be simpler and faster.