5,323
edits
Parallel Algorithms: Difference between revisions
→Tree Contraction
| Line 482: | Line 482: | ||
Step 2 takes <math>O(\log n)</math> rounds. Each leaf gets raked only once.<br> | Step 2 takes <math>O(\log n)</math> rounds. Each leaf gets raked only once.<br> | ||
In total we take <math>O(\log n)</math> time and <math>O(n)</math> work. | In total we take <math>O(\log n)</math> time and <math>O(n)</math> work. | ||
===Evaluating an Arithmetic Expression=== | |||
Consider a binary tree where each internal node is an operator: | |||
Either addition or multiplication.<br> | |||
Each leaf is a number<br> | |||
Assign each internal node 4 numbers: a,b,c,d<br> | |||
These are initialized to (1,0,1,0)<br> | |||
The internal node will be (a*l+b) \times (c*r+d) where \times is either addition or multiplication.<br> | |||
If we delete one leaf and it's parent (stem), we will modify these variables of the stem's parent. | |||
==Resources== | ==Resources== | ||