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

We define the term "a block-of-k-sorted array" to mean that the given 
array of length n, has the property that if you look at it as being the
concatenation of n/k continiguous sub-arrays each of length k, then
the elements within any of these sub-arrays are all smaller than any
elements in any later sub-arrays.

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



(a) Using a comparison-based model, design an algorithm that could take 
    an n-element block-of-k-sorted array and fully sort it in runtime of 
    at most 3nlogk.
        You can assume things such as "k is a power of 2" or "n is a 
        multiple of k" if that would be of use.
   
(b) Assume that the fastest asymptotic runtime possible to block-of-k-sort 
    an array of random values in the first place were Θ(n log (n/k)), is it
    possible to accomplish (a) any faster (asymptotically speaking) than 
    the solution you came up with?  Why or why not?







Given the following search pattern:
     P: AABAAC
create the KMP sp[] array as we did in class.

Using that search pattern and the sp[] array you created, perform a search 
on the following block of text:
     T: AACAABAABAACAACB

     solution SP array and pattern search trace





Given the following search pattern:
     P: AACAAABA
create the KMP sp[] array as we did in class.

     solution SP array


Using that search pattern and the sp[] array you created, perform a search 
on the following block of text:
     T: AACAACAAABAY








Given the following search pattern:
     P: ABXABYABXZ
create the KMP sp[] array as we did in class.

     solution for SP array

Using that search pattern and the sp[] array you created, perform a search 
on the following block of text:
     T: ABXABYABXABYABXZABC