Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_______ final_______)

A (directed) forest is a graph that consists of one or more disjoint (directed) trees. Note that in a forest, every node has either zero or one parent node. A node with zero parents is the root of some tree, and all non-root nodes have a unique parent. We can represent a forest by an array $P$ of length $n$ where $P[i] = j$ means that node $i$'s parent is node $j$, unless $j = -1$, in which case $i$ is a root node. See the image to the right to see an example drawn out.

Your job: draw the forest defined by

Problem 1 (assessment: self_______ final_______)

A node $s$ in a forest is said to have a "unique destination" if $s$ and all of its descendents have a single, unique child until you get to a node with no children, which is the "destination". Consider the following problem:
Problem: Unique Destination
Input: $P, n, s$ — where $P$ is an array of $n$ integers representing a forest on nodes $\{0,\ldots,n-1\}$, and $s$ is a node (the "starting node")
Output: TRUE if $s$ has a unique destination, and FALSE otherwise.
The following algorithm solves the Unique Destination problem. Note: The outer while loop does indeed terminate, as long as the input really is a forest (i.e. no loops). If it were to go on too long, you would eventually hit a node you'd already visted, which would mean there was a loop.
Your Job: Analyze $T_w(n)$ and $T_b(n)$, this algorithm's best and worst case running time functions, in terms of $n$.
Algorithm: uniqueDest(P,n,s)
Inputs: P,n,s --- an input instance of the Unique Destination problem
Output: TRUE/FALSE a solution to the Unique Destination problem

next = s, count = 1

while count == 1 do
  curr = next
  count = 0, i = 0
  while i < n do     ← this loop counts the number of children of curr and sets next to the most recently seen child
    if P[i] == curr
      count = count + 1
      next = i
    i = i + 1

if count == 0
   return TRUE
   return FALSE

Problem 2 (assessment: self_______ final_______)

One might note in uniqueDest that in the inner loop we don't really need the exact number of children of node "curr". We just need to know whether there are 0, 1 or more than one. So we could cut out of that inner while loop early by changing it to:
  while i < n and count < 2 do
Your job: Tell me how that changes the best and worst case running time functions? I.e. what can we say about $T_w(n)$ and $T_b(n)$ now?