463 views
2 votes
2 votes
Draw a complete binary tree $T$ with $(N − 1)$ nodes where $N = 2^n$. Suppose each node in $T$ is a processor and each edge of $T$ is a physical link between two processors through which they can communicate. Given $M$ arrays $A_i = \{e_{1i}, e_{2i}, \dots, e_{Ni} \}$ for $1 \leq i \leq M$, develop an algorithm for the given architecture to compute the sum of each array $SUM_i = \Sigma^N_{j=1} e_{ji}$ for all $i$ in $O(\log  N + M)$ time.

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
go_editor asked Jun 1, 2016
513 views
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source...