Compsci 06, Spring 2011, Recursive FUN, April 4

Name____________________   net-id _________       

Name____________________   net-id _________       

Name____________________   net-id _________

    SpreadingNews

    Consider the SpreadingNews APT for the following questions.

  1. You're the boss. You have three direct reports none of whom has any reports, e.g., the input is [-1,0,0,0]. How much time is needed for everyone to know the news?

    1. 4 minutes

    2. 3 minutes

    3. 2 minutes

  2. The input is [-1,0,1,2,3,3,3]; here's a diagram: 
       0
   |
   1
   |
   2
   |
   3
   |
 +-+-+
 | | |
 4 5 6
    Once the person with index 3 hears the news, how many more minutes before all his direct reports hear?

    1. 4 minutes

    2. 3 minutes

    3. 2 minutes

  3. Same input: [-1,0,1,2,3,3,3], what's the final answer?

    1. 7 minutes

    2. 6 minutes

    3. 5 minutes

  4. The input is [-1,0,0,2,2,1,0,6,1,8,3]. Diagram below. For the best schedule, how many minutes after the process starts does person 7 get all the news? 
             0
         |       
   +-----+-----+
   1     2     6
  +-+   +-+    +
  | |   | |    |
  5 8   3 4    7
    +   +
    |   |
    9   10

    1. 5 minutes

    2. 4 minutes

    3. 3 minutes