1 [5 pts]. Solution

                 11111100
           ______________
     10011 | 111011000100
             10011
             -----
              11101
              10011
              -----
               11100
               10011
               -----
                11110
                10011
                -----
                 11010
                 10011
                 -----
                  10011
                  10011
                  -----
                   00000
                   00000
                   -----
                    00000
                    00000
                    -----
                     0000

It is acceptable because the remainder is 0000.
The data bit sequence is 11101100 (111011000100 minus last 4 bits).

GRADING:

• 4 points for the division, 1 point for the data sequence.

2 [10 pts]. Solution

Time    At B, distance to D      At C, distance to D
           via node C              via node B  via node D

0.1           4*                      6        2*
1.0           4*                      6*      11

1.1           8*                      6*      11

2.1           8*                     10*      11

3.1          12*                     10*      11

4.1          12*                     14       11*

5.1          13*                     14       11*

6.1          13*                     15       11*

* indicates the minimum distance entry

Stable at time 6.1.

GRADING:

• Entry at time 1.0 did not count toward grade.
• Max 2 points for stating that stable by time 2.1 or 3.1.
• Max 6 points for not getting it correct but showing that the min distance decreases by 4 every iteration.
• Lose 1 point if everything correct but stabilization time.
• Lose 2 points if only one line is wrong.

3 [10 pts]. Solution

a.

b.

          

          

c.

GRADING:

• Part a: 2 points for spanning tree. 2 points for aggregate flows.
• Part b: 1 point for each spanning tree.
• Part c: 2 points for aggregate flows.

4 [5 pts]. Solution

Below, * denotes multiplication and ** denotes exponentiation.

For slotted-ALOHA of N nodes, the throughput (as fraction of successful slots) is N*p*[(1-p)**(N-1)], where p is transmission probability. Thus maximum throughput is (1-p)**(N-1), which is achieved when p=1/N.

The 4-user group and even slots form a 4-node slotted-ALOHA system. Thus its max throughput is achieved when p=(1/4), and equals (1 - (1/4))**3, which equals (3/4)**3, which equals 27/64.

The 26-user group and odd slots form a 26-node slotted-ALOHA system. Thus its max throughput is achieved when p=(1/26), and equals (1 - (1/26))**25, which practially equals (1/e).

Thus the overall throughput is (1/2)[(27/64) + (1/e)]

GRADING:

• 1 point for noting that the transmission probability for the two groups are different, say p for the 4-user and q for the 26-user group.
• 2 points for obtaining the expressions 4p(1-p)**3 and 26q(1-q)**25.
• 3 points for obtaining the expression (1/2)[4p(1-p)**3 + 26q(1-q)**25]
• 4 points for above expression with probabilities (1/4) and (1/26)
• 5 points for above expression and noting that (1 - (1/26))**25 is practically equal to (1/e)