CMSC 351 - Homework #3 - Due by 11:59pm on February 15th

You are encouraged to try to finish this before class on Wednesday, and some partial solutions or hints will be presented then but for the full learning experience, you should have tried (and possibly completed) these problems before hearing those.

Write clearly. Write your name and section clearly on the top of the first page. Scan/photograph clearly. If we can't read it, we will grade it as incorrect.

After you finish your answers, scan or carefully photograph your answer sheets and create a single PDF with those images to upload to the ELMS entry.

You cannot e-mail them to me.

We will only grade some subset of these, but we want you to do all of them as homework (ie: not working with others) as good practice for the exam.

Question #1
    Use constructive induction to prove that
        T(1)=0
        T(i)=2T(i/2) + 5i  for i>1
    is in Ο(nlogn) using the definition of Ο.
       [That means T(n) <= c*nlogn for some positive real number c
          for all n greater than or equal to some n0 starting point.]

   hint






Question #2
   The Marvel and DC heroes and sidekicks and support staff have decided 
   to get together and have a friendly scavenger hunt game mix-and-mingle 
   event to get to know each other better.

   Wonder Woman will captain one team and Ton Stark will captain the other.  

   The teams don't need to be the same size.  However, there are certain 
   strong "grudges" between certain individuals (Tony and Steve Rogers are
   still not seeing eye to eye and Vision still doesn't trust Superman, for
   example) so if anyone has others who will be coming with whom they refuse
   to play on the same team, they will give you a set of cards identifying 
   who (of the other n-1 people who are coming) those people are.  

   Each card has their own name and the name of one other person
   with whom they don't want to be on a team.  

   Not all people coming will have grudges, so not every one of them will 
   give us cards at all.  Some have many such grudges, so will give us 
   many cards.  Everyone has decided in advance that Deadpool doesn't get to 
   play because nobody would want to be on that team.  

   All together, there are c cards given to us.

   Write an algorithm that runs in O(n+c) time and...
      (a) determines whether there is a way to divide the people up 
              into two teams
      (b) if there is, says who should be on each team

   NOTE: You don't need to give pseudocode, you can write a detailed
         English description of the steps of your algorithm.  It needs
         to provide enough details that I could then implement this in
         actual code and know what the code is testing for, etc.

   hint






Question #3
   Create a graph representing the following constraints for shipping
   parts of an order to a customer that will not annoy the customer:

        Photoshop before Ink
        Ink before Printer
        Paper before Printer
        Paper before Album
        Album before Storage Box
        Album before Shipping Box

   Perform (and show this on your homework sheet) a topological sort 
   on this graph to determine a sequence of item shipments that do 
   not violate the constraints (and thus hopefully lead to a happier 
   customer).

   Your answer should be an ordered list of items.  There might be more
   than one valid solution.  If there is, you only have to provide one.











Question #4
    For each of the following, use the quantified definitions for the 
    specified relationship to formally prove the relationship - show
    your detailed proof and present the c and the n0 at which things 
    start working.  

   (a) Is (4n2+n)12 ∈ Ω(n18)?
   (b) Is 6n2-log3(9n) ∈ Ο(n2)?