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

(1) Assume that we have an algorithm whose expected/average case runtime
    can be described as:

                 n-1
            n +   Σ T(min(i,n-1))
                 i=1
                -------------------
                       (n-1)

    HINT: Inequality chains will be very uesful...


    example solution






(2) A binary tree has a branching factor of 2.  The best height
    of such a tree is log2n.   If we change the branching
    factor, we change the best-case height of the tree.  For each of
    the following branching factors, what is the best-case tree height?
    Simplify your answer where possible.

    i)   branching factor of 3 answer
    ii)  branching factor of log2n  answer
    iii) branching factor of sqrt(n) hint
    iv)  branching factor of n1/4 hint









(3) An AVL tree is a binary search tree where for any node the heights 
    of its TWO subtrees differ by at most 1.  What if we changed this 
    and created an AVL3 tree which was a trinary tree where for any node 
    the heights across all THREE subtrees differed by at most 1?  

    What would the worst-case height of an AVL3 tree be?

       hint

       standard AVL proof example








(4) In class we looked at the cost of "heapifying" a complete tree,
    into a MAX-HEAP by processing it bottom-up.  The total runtime
    cost was linear.  For this question you need to analyze the runtime
    to harvest a max-heap to create a sorted list n elements by 
    repeatedly calling the regular HEAP::Remove() method.

    You can use inequality chains to simplify dealing with summations, 
    but do not reduce to just Big-O.







(5) In class we looked at the cost of "heapifying" a complete tree,
    into a MAX-HEAP by processing it bottom-up.  The total runtime
    cost was linear.  For this question you need to analyze the runtime
    to build a tree from a list of n elements by repeatedly calling
    the regular HEAP::Add(val) method (ie: insert the value at the leaf
    level and bubble it up the tree as needed.  You can use inequality
    chains to simplify dealing with summations, but do not reduce to
    just Big-O.