CMSC 351 - "Thought Questions" - CMSC 351
Not Graded but Should be Done

Question #1
In class we defined a list as "k-away-sorted" to mean that each element
in the list is at most k positions away from where it would go if the list
were fully sorted.

For example, the following array is "4-away-sorted" by these rules:
   3, 2, 1, 5, 4, 6, 10, 8, 9, 7, 11, 16, 12, 14, 15, 13 


For this thought question, figure out a way to use a min-heap as a buffer 
to support sorting this type of list as efficiently as possible (note, this
will be in less than n log n asymptotic time).  You'll need to think about
how to use the min-heap as well as the smallest possible min-heap that would
work (they are inter-related).




Question #2
Trace the algorithm on Slide Set #19, Page #3 on the following graph:
   







Question #3
Imagine you are given a jumbled list containing all of the integers
between 1 and n EXCEPT ONE IS MISSING.

Create a linear-time algorithm in terms of reading values from memory
that doesn't use any temporary data structures (so no arrays or trees
or things like that, but a small number of things like long ints are
fine) that is able to tell you which value is missing.





Question #4
Imagine you are given a jumbled list containing all of the integers
between 1 and n EXCEPT TWO ARE MISSING.  Do the same as with Q#3.

   Q4 solution core





Question #5
We want an 8-digit number 
   digit7, digit6, digit5, digit4, d
igit3, digit2, digit1, digit0
such that for digits "i" going from 0 through 6, the value in digiti 
is the number of "i"s in the 8-digit number
and that digit7 the number of DISTINCT DIGITS  in the 8-digit number.

Write the algorithm for a program to generate the solution (not for a 
program that generates all possible 8-digit numbers and then tests each 
one for corectness).  

You do not implement this, but you should be able to hand-trace the
algorithm to check that it works.

   Q5 solution core