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

Some more practice on "old" topics:

(1) Solve the following...

   (log1/2n)-1
       Σ2i
      i=0

You can see a math hint after you've thought about the problem 
for a while if you aren't sure how to approach it.






(2)
    Use the quantified definitions of Ω and Ο to determine 
    the values that can be used to show that    
        0.1n4+50n2-7n is in Ω(n4)
    and that   
        0.1n4+50n2-7n is in Ο(n4)






(3) 
    In class, one of the problems had us in the middle of proving whether
         (ck+14k)log(0.75k)+k <=? cklogk
    continue the proof until you can pick a c and determine an n0.

    TQ4-3 solution example details





Some practice on "new" topics:

(4)
    Imagine the following algorithm for finding the smallest number
    in a list:
        If the list is size 1, return that value.
        If the list is size 2, compare them and return the smaller.
        Otherwise, split the list into two parts of 1/3rd and 2/3rds.
            Find the smallest in each part via a recursive call.
            Take the two return values and return the smallest of them.

    This recursive algorithm's runtime can be described as:
       T(1) = 1, T(2) = 2
       T(i) = T(1/3 i) + T(2/3 i) + 1 for i>=1

    For this problem you can assume that the input size will be a power of 3
    and assume we'd round up/down to make the algorithm work as needed.

    Prove T(n)∈Ω(n) using the techniques we've seen. 

    NOTE: With all problems like this, we would need to find a base
          case that works.  In class we haven't done that part since
          it's the "easier" part to do, but it's worth noting that 
          on occasion a base case can't be found because the whole
          statement was actually false.  We haven't seen those yet. 

    TQ4-4 partial solution


    




(5) Using the limit rules, what is the "little" asymptotic relationship 
    between functions
        2sqrt(n) and 1.5n

    This is an interesting one because it uses an asymptotic proof in the
    middle of an asymptotic proof.        

    TQ4-5 "core" details





(6) Determine Big-O and Big-Omega bounds runtime of each of the 
    following recurrences based the recursion tree technique:

        (a) T(1)=1
            T(n) = 6T(n/4) + 1

        (b) T(1)=1
            T(n) = 6T(n/4) + n

        (c) T(1)=1
            T(n) = 6T(n/4) + n2

    TQ4-6 partial solution about structure and pattern





(7) Imagine you are given a device that will turn red if it is dropped
    from more than a certain height, and you have been asked to design 
    and algorithm that will determine to the nearest foot what that 
    height is if it is guaranteed to be below a certain limit.

    For example, they might ask "Given the height will never be more than
    100 feet, give us a way to find the threshold by dropping the device 
    the fewest number of times."

    The will also tell you how many devices you can waste in this testing.
    It turns out that once the device turns red, it's useless since it 
    cannot be reset.

    If they only give you one, there's really only one way to do it.  Drop
    it from 1 foot, then if it didn't turn red drop it from 2 feet, then if
    if still didn't turn red drop it from 3 feet, etc.

    For this thought question, limit yourself to the situation where they 
    have given you TWO devices and a upper limit of n feet.  As a function
    of n, can you do this in asymptotically fewer than n drops in the worst 
    case scenario?  

    



----you might want to save this last one for an Exam #2 practice problem----


(8) Determine the Big-O and Big-Omega runtime of each of the 
    following recurrences using the recursion tree technique:


     a) T(1)=1
        T(n)=T(n/4)+T(3n/4)+n
           



     b) T(1)=1
        T(n)=T(n/4)+T(3n/4)+1
           



     c) T(1)=1
        T(n)=T(n/4)+T(3n/4)+n2