Tree Computations

Question 1

How do you represent a tree using the array pool we used for linked lists?

Answer 1

• Number the nodes and convert the undirected edges to directed edges that point towards node parents
• Create an array P which stores the parent of each node (if node 1’s parent is 8, then P[1] = 8). P[root] = NULL

Question 2

Describe the sequential algorithm for finding the root of a tree, assuming you have the array pool representation?

Answer 2

if n < 1: return 0
node <- pick_any_node(P[:])
while P[node] != 0:
node = P[node]
return node

i.e., Pick a random node, then follow the pointers to the root (node with no parent).

Question 3

What is the worst case running time of the sequential algorithm for finding the root of a tree?

Answer 3

O(n)

It’s linear because in the worst case we could have an extremely unbalanced tree, where each node has one child, and we might randomly pick the very bottom node in the tree.

Question 4

Describe the algorithm for finding the root of a tree in parallel, given an array pool representation?

Answer 4

Inspired by jump lists, explore all nodes in parallel and change each node to point to its grandparent (rather than parent) if the grandparent exists. Iterating this process, eventually all nodes will point to their root.

We need two auxiliary functions:

hasGrandparent(k, P[:])
return (k > 0) && (P[k] > 0) && (P[P[k]] > 0)
i.e., make sure that neither node k, k’s parent, nor k’s grandparent are a NULL, i.e., k has a grandparent

adopt(P[:], G[:])
par-for i=1:n
if hasGrandparent(i, P[:])
G[i] = P[P[i]]
else
G[i] = P[i]
i.e., the jump step. for every node, check if it has a grandparent. if yes, set G[node] to that grandparent, otherwise set to parent

Overall algorithm:

findRoots(P[1:n], R[1:n])
P_cur = P
P_next = empty list of size n
for i=1 to ceil(log n) }
adopt(P_cur, P_next)
P_cur = P_next
}
R = P_cur

Question 5

When finding the root of a tree in parallel, why can’t you immediately terminate the search as soon as you realize some node has no grandparent (i.e., its parent is the root)?

Answer 5

There may be more than one root! i.e., this algorithm works on forests, not just trees.

Question 6

Is the parallel root-finding algorithm work-optimal?

Answer 6

No! The adopt() function requires O(n) work, and it is repeated ceil(log n) times. So I guess the overall algorithm is O(n log n).

Question 7

Given a linked list of size n, Wyllie’s algorithm for parallel list-ranking has work O(n log n). We can try to make this work-optimal (get it down to O(n)) by “shrinking” the list to size m < n then running Wyllie on that. This gives us work O(m log m).

What choice of m would make O(m log m) = O(n)?

Answer 7

n/logn

We can prove this by plugging it in:

m log m = (n/logn) log(n/logn) = (n/logn) (log n - log^2 n)
= n - (log^2n / logn) = O(n)

Question 8

What is an independent set (with respect to a linked list)?

Answer 8

A set of nodes such that none of them are successors of each other, i.e.,

A set I of vertices such that i in I => N[i] is NOT in I

Question 9

Describe the randomized algorithm for finding independent sets in parallel

Answer 9

Basically, flip a coin for each node (in parallel of course). Then, for each node, check if its successor has the same value (heads or tails): if so, change it (symmetry breaking)! Bam, done.

ParIndSet(N[1:n], I[:])
let C[1:n] and C_hat[1:n] be space for coins
par-for i=1 to n:
C[i] = coin flip (H or T)
C_hat = C (make a copy)
par-for i=1 to n:
if (C_hat[i] == H) and (N[i] != NULL) and (C_hat[N[i]] == H):
C[i] = T
gatherIf(1:n, C[1:n]) (where heads counts as TRUE, i.e. we gather all heads that remain after symmetry breaking)

Question 10

What are the work and span of our algorithm for finding independent sets in parallel?

Answer 10

W(n) = O(n) (each step is O(n))
D(n) = O(log n) (each step is ultimately a par-for, which is O(log n))

Question 11

Given a list of size n, how many nodes wind up in the independent set on average?

Answer 11

n/4

My reasoning: On average, half the nodes will be heads when you flip the coins. Then for each of those nodes that came up the heads, the probability that their successor is heads is ALSO 1/2. 1/2 * 1/2 = 1/4.

Prof’s reasoning: For each coin there are four possible outcomes for itself and it’s successor. These are HH, HT, TH, TT. In the case of HH we will change it to TH. So that leaves only one case out of four in which a node will be heads at the end of the process.

Question 12

What is the (three-step) “trick” for work-optimal parallel list-scan/prefix-sum?

Answer 12

1) Shrink list to size m = O(n/logn)
2) Run Wyllie’s algorithm on the shrunken list: O(m log m) = O(n)
3) Restore full list and ranks

Question 13

How do we shrink the list (for work-optimal list scan)?

Answer 13

Use the independent set!

1) Initialize our rank array like for Wyllie’s, 0 for the list head and 1 for everything else.
2) Then identify an independent set (by flipping coins and removing double heads)
3) Remove the independent set by rewiring nodes around those in the independent set (jump list!) and updating ranks accordingly, propagating the ranks of nodes in the ind set to their successors.
4) Repeat the last two steps until you have m = n / log n nodes.
5) Now, all remaining nodes should have the correct ranks! Run the above process backwards to fill in the ranks of other nodes (see lecture notes for pseudocode and more explanation!)

Question 14

How many times do you have to shrink the list to get it to the desired size, O(n / log n)?

Answer 14

O(log log n)

Our method for finding an independent set finds a set that is roughly size n/4. After we remove this set, that leaves a set with an expected size of 3/4 * n. So we can express the expected size of the remaining set after k passes as (3/4)^k * n, and we want to find k such that:

(3/4)^k *n <= n / log n

This implies (3/4)^k <= 1 / log n

Which implies log n <= (4/3)^k

and log log n <= roughly k

Question 15

Describe the sequential postorder numbering algorithm

Answer 15

First of all, in postorder traversal is when you visit the left subtree, then the right subtree, then the root.

The algorithm is recursive. We need the root, a vector V to hold the numbering, and an initial count v_0 (probably zero). Basically do DFS and count the nodes as you go, starting with the bottom left most node.

postorder(root, V[1:n], v_0):
v = v_0
foreach child of root:
v = postorder(child, V[:], v) + 1
V[root] = v
return v

(You should add preorder traversal when you have time)

Question 16

Describe postorder traversal vs preorder traversal

Answer 16

These are BOTH types of DFS.

Postorder traversal is when you visit the left subtree, then the right subtree, then the root.

Preorder traversal is when you visit the root, then the left, then the right subtree. Though the left vs right part is ambiguous.

Question 17

What is an Euler graph?

Answer 17

A graph where in-degree = out-degree for each node.

Question 18

What is an Euler circuit?

Answer 18

A closed path on a graph that uses every edge once.

Question 19

Describe the Euler Tour technique

Answer 19

BIG PICTURE
Euler Tour obtains the postorder numbering for a tree by
1) converting the tree into a linked list
2) strategically setting initial rank values
3) then using a prefix-sum to get the final ranks

MORE DETAIL
1) Tree -> List
- Take every undirected edge in the tree and replace it with two directed edges, one in each direction. This results in an Euler Graph.
- Starting and ending at the root node, the new directed edges form an Euler Circuit. This circuit gives you a linked list, where each endpoint of a directed edge is a node in the list (i.e., there are more nodes than in the tree!)
2) Set initial rank values in the list so that all “sink” (or target, or endpoint) nodes for a parent to child target are 0, and all sink nodes for child to parent edges are 1. These ones correspond to the recursive (+1) call in postorder traversal
3) Use prefix-sum to the final ranks!

Question 20

What is the work of the Euler Tour technique?

Answer 20

The same as prefix-sum! (look up exactly what that is)

The first two steps of the Euler Tour, converting from tree to linked list and setting initial rank values, are constant time (??why??). So it’s all about prefix-sum (I THINK! check the notes or EdStem).

Question 21

The span of list prefix sum is O(log n). This is the last step of the Euler Tour technique. Is the overall span for Euler Tour O(log n) too, or does it depend on tree shape?

Answer 21

Assuming that you have already converted the Tree to a list, then yes, the overall span is still O(log n)!

My instinct tells me that the span of converting the Tree to a list probably depends on tree shape. Ask about this on Ed!

Question 22

How do you compute the levels of a tree using an Euler Tour?

Answer 22

1) Compute an Euler Circuit, which gives you a tree traversal in list form.
2) Initialize you parent to child sink nodes so they equal 1 and your child to parent sink nodes so they equal -1, i.e., as you go up a level you add one and down a level subtract 1. Initialize the root to zero.
3) Prefix sum! Now your child to parent SOURCE nodes have the correct level.

Question 23

How do you store the tree for an Euler Tour?

Answer 23

Using an adjacency list. For each node, the adjacency list includes all its children plus its parent.

v in the adjacency list represents a node, and u_i represents v’s ith neighbor.

Question 24

What special function do we use to compute the Euler Tour?

Answer 24

A successor function defined as s(u_i, v) := (v, u_((i+1) mod d_v))

i.e., the successor of edge (u_i, v) (from u_i to v) is the edge (v, u_((i+1) mod d_v)) (from v to the NEXT node in v’s adjacency list, where “next” includes looping back around from the end to the beginning). We treat each adjacency list a circular.

Question 25

Is the successor function we use for Euler Tour W(n) = O(n)?

Answer 25

Yes, as long as you add cross-pointers! Cross-pointers connect the entry for edge (0, 1) to the entry for edge (1, 0).

See the end of https://edstem.org/us/courses/32930/lessons/52177/slides/295032 if you don’t remember the image clearly