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

Question #1
    Can you write an algorithm that will find the 3rd smallest 
    element in a group of 5 with a worst case that is better 
    than 8 comparisons?  Think about how to use a decision
    tree to try to design an optimal set of questions.

       some solution information for 1



Question #2
You have an algorithm that is given a list of n values and:
        IF n is fewer than 3 values, it will perform 1 calculation and
                   return an answer.
        OTHERWISE it will do the following:
            * perform 3n preprocessing calculations on the list that 
              results in three non-empty sublists: L1, L2, L3
            * recursively calls itself on list L2
            * there are no postprocessing calculations

    Determine and prove the expected asymptotic runtime of this algorithm.
    You should assume that all splitting in terms of the size of list L2 
    is uniformly distributed.  For example, it is equally likely that L2 
    will have 1 element as it is that L2 will have n/3 elements, etc., etc.

       some solution information for 2
   
 

Question #3
Given the correct greedy algorithm for activity scheduling
    that we saw in class, what would the runtime when counting
    only the comparisons that involve start or finish times be in 
    terms of the number of requests?  Explain your answer.



Question #4
Define an imbalanced tree using rules you make up in terms of the
    branching factor and amount of imbalanc allowed.

    Then calculate the best-case situation in terms of values-vs-height
    and then calculate the worst-case situation as well.




Question #5
a) How were we able to both prove sorting had a lower-bound of n log n 
       and also have Radix Sort with its runtime in class?  Why don't the
       two create a paradox?

           some solution information for 5a


b) If you have a k-away-sorted list, and we could show that it could be
        completely sorted using Insertion Sort in O(nk) time, what would that
        tell us about the amount of time it would take to start from an
        arbitrary list of n values and make it k-away-sorted?

           some solution information for 5b



   
Question #6
Use the DFS method to identify the largest strongly connected 
    components in a graph with the following vertex set V and 
    edge set E:

        V = {A,B,C,D,E,F}
        E = {(A,B),(A,D),(B,C),(C,E),(C,F),(D,A),(D,E),(E,B),(E,F)}

   Your answer should be the graphs with the DFS values, and the
   components circled on the second graph.

       some solution information for 6



Question #7
There is a new zoo being designed.  However, due to the budget
    problems they want to have as few habitat areas to build and deal
    with as possible.  It was pointed out that even zoo animals revert 
    to instinct, so they have to be VERY careful about which animals 
    are placed within the same enclosure.  

    You have been hired to write a program that will take as input 
    information about which pairs of animals will fight or eat 
    one-another if placed in the same space.  Your program will 
    then output a set of lists where each list is a listing of 
    animals that can live together.  The zoo designers want the 
    fewest lists of course since each list ends up being another 
    habitat to build.
 
    - How would you implement a solution to this problem?
    - What would its runtime be?

       some solution information for 7



Question #8
Use the 2-CNF SAT-solving algorithm to determine whether each of
    the following can be satisfied:


        (A∨B)∧(~A∨C)∧(~B∨~C)∧(~B∨D)∧(D∨E)∧(~E∨F)∧(~F∨~E)∧(~D∨~F)


    You should show the full trace of the algorithm, not just give a 
    yes/no answer.

       some solution information for 8



Question #9
   (a) Create a recurrence relation with at least three recursive calls
       and some local work and then use the recurrence tree technique to 
       find Big-Omega and Big-O bounds, and then use constructive induction
       to find a tight constant on the Big-O bound.


   (b) Create a recurrence relation where all of the work is at the leaves
       and then determine the Big-O bound for it.

  



Question #10
(a) What does it mean for a problem to be "NP"?

(b) What does it mean for a problem to be "NP-Complete"?

(c) Can an algorithm be NP-Complete?

       some solution information for 10