COSC 511 10/16/2014  In class assignment. Closed book.

1. Consider this undirected graph:

   | a | b | c | d
--------------------
a  |   | 2 | 4 | 1
b  | 2 |   | 3 |
c  | 4 | 3 |   | 2
d  | 1 |   | 2 |

Which of the following is an MST?

A.  
   | a | b | c | d
--------------------
a  |   | 1 |   | 1
b  | 1 |   |   |
c  |   |   |   | 1
d  | 1 |   |   | 1


B.
   | a | b | c | d
--------------------
a  |   |   |   | 1
b  |   |   |   | 1
c  |   |   |   | 1
d  | 1 | 1 | 1 |

C.
   | a | b | c | d
--------------------
a  |   | 1 |   | 1
b  | 1 |   | 1 |
c  |   | 1 |   | 1
d  | 1 |   | 1 |


2. Consider this directed graph. 

   | a | b | c | d
--------------------
a  |   | 1 |   | 
b  |   |   | 1 |
c  | 4 |   |   | 1
d  |   | 2 |   |

2. A. What is the shortest path from a to d?

2. B. What is the shortezst path from c to b?

3. Consider this function definition

f(n) {
  if (n == 0 || n == 1) return 1;
  return f(n/2) * f(n/2) + n;
  }

T(0) = T(1) = 1

What is the recurrence? (pick A or B or C)

3.A. T(n) = (T(n/2) + T(n/2)) / 2
3.B. T(n) = T(n/2) + T(n/2)
3.C. T(n) = T(n/2) + T(n-2) + n


4. Consider this recurrence
T(0) = T(1) = 1
T(n) = 2 * T(n-2) + 1

Give T(n) in terms of T(n-2) (i.e., the right habnd side has T(n-2) terms, 
it does not have T(n-2) terms.