TIFR CSE 2023 | Part B | Question: 8

Question

Let $U$ be a finite set and let $h$ be a function mapping $U \times U$ to $U$. Consider the following process that assigns values to all nodes of a complete binary tree with $128$ leaves. Initially, the leaf nodes are assigned arbitrary values from $U$. Then, the value that is assigned to an internal node is the output of $h$ on the values assigned to this node's children. The value of the tree is given by the value assigned to the root.

Once you have computed the value of the tree, you realize that the initial value that was assigned to the $53^{r d}$ leaf was incorrect and you therefore need to use a different value for the $53^{r d}$ leaf. Given this incorrect tree as input, at most how many times would an optimal algorithm need to recompute $h$ in order to obtain the correct value of the tree?

• A. $7$
• B. $8$
• C. $53$
• D. $127$
• E. $255$

Answer 1

Say,  a pair of leaves has been assigned 1 and 3 respectively. The parent of the pair is accordingly assigned (1,3) -> 5 (considering 1 and 3 maps to 5 given h). So 53rd ( or any ) leaf changed to a different value, say, 4, eventually maps to (1,4) so the h must be recomputed for the parent once. The change is parent requires another recomputation for the parent above, and so on till the root is recomputed. So the height of the tree is the number of times, the value is recomputed.

Comments

this 53^rd node is the main point right?had itbeen given any leaf then in worst caseit would have been B right

---

@AGNIDEB MUKHERJEE i think 7 will be the answer for every leaf node, recomputation depends on the level currently we are on, suppose if you were on level 6 then you have to compute till you reach to the root so in this case 6 will be the answer, and so on for inner levels.

---

so 128 leaves means the height of the tree is 7 right so  in tot there are 255 nodes.now is it correct?

---

since it's complete binary tree,yes you are correct.