CompSci 06/101, Fall 2011, Lab 11

By entering your name/net-id below you indicate you are present for this lab to answer these questions and that you were part of the process that resulted in answers being turned in.

Name: ______________    Net id: _____________ || Name: ______________    Net id: _____________

Name: ______________    Net id: _____________ || Name: ______________    Net id: _____________

RSG Questions

Explain, in English, how the sentence below was generated from the grammar given on the RSG HOWTO page:
I gave up working on this week's APT assignment. The problems were really , really , so impossible and I got h1n1 .
```
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
```

Explain, in Python-ish pseudocode, how the sentence above was generated from the grammar given on the RSG HOWTO page and using the dictionary data structure described there.

Explain, in Python-ish pseudocode, the base case for the generate function.
```
  
  
  
  
  
  
  
  
  
  
```
Explain, in Python-ish pseudocode, the general case for the generate function.
```
  
  
  
  
  
  
  
  
  
  
```

SpreadingNews Questions

You are 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?
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?
Same input: [-1,0,1,2,3,3,3], what's the final answer?

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

If you created a dictionary to represent the supervisor/employee structure, what would be the keys and what would be the values?
```
  
  
  
  
  
  
  
  
  
  
```
Describe, in English, how to determine the total number of minutes needed for a supervisor to notify all his employees.
```
  
  
  
  
  
  
  
  
  
  
```
Describe, in English, the base case in this computation.
```
  
  
  
  
  
  
  
  
  
  
```
Describe, in English, the general case in this computation.
```
  
  
  
  
  
  
  
  
  
  
```
Describe, in English, how to minimize the time needed to notify employees (i.e., how to combine the results of the recursive function calls and report them to the calling function).
```
  
  
  
  
  
  
  
  
  
  
```