Node merging

Questions 1 to 5 of 6

1. 1. Predict the output of this program. ``python from dataclasses import dataclass @dataclass(frozen=True) class Info: total: int prefix: int suffix: int best: int def leaf(value): return Info(value, value, value, value) def merge(left, right): if left is None: return right if right is None: return left total = left.total + right.total prefix = max(left.prefix, left.total + right.prefix) suffix = max(right.suffix, right.total + left.suffix) best = max(left.best, right.best, left.suffix + right.prefix) return Info(total, prefix, suffix, best) x = merge(leaf(-4), leaf(5)) y = merge(x, leaf(-2)) print(y) a = merge(leaf(-3), leaf(-1)) print(a.best) print(merge(None, a) is a) print(a.total, a.prefix, a.suffix) ``

   Info(total=-1, prefix=1, suffix=3, best=5) -1 False -4 -3 -1Info(total=-1, prefix=1, suffix=5, best=5) -1 True -4 -3 -1Info(total=-1, prefix=1, suffix=3, best=5) -1 True -4 -3 -1Info(total=-1, prefix=1, suffix=3, best=5) 0 True -4 -3 -1
2. 2. Predict the output of this program. ``python from dataclasses import dataclass @dataclass(frozen=True) class Info: total: int prefix: int suffix: int best: int def leaf(value): return Info(value, value, value, value) def merge(left, right): if left is None: return right if right is None: return left total = left.total + right.total prefix = max(left.prefix, left.total + right.prefix) suffix = max(right.suffix, right.total + left.suffix) best = max(left.best, right.best, left.suffix + right.prefix) return Info(total, prefix, suffix, best) a = merge(leaf(2), leaf(-5)) b = merge(a, leaf(4)) print(a) print(b.best, b.prefix) ``

   Info(total=-3, prefix=2, suffix=-3, best=2) 4 4Info(total=-3, prefix=2, suffix=-3, best=4) 4 2Info(total=1, prefix=2, suffix=4, best=4) 4 2Info(total=-3, prefix=2, suffix=-3, best=2) 4 2
3. 3. In the merge of a left child L and a right child R, which expression gives the prefix of the parent?

   max(L.prefix, R.prefix)max(L.prefix, L.total + R.prefix)L.total + R.prefixmax(L.prefix, R.total + L.suffix)
4. 4. Which expression gives the best run that crosses the middle of a parent node?

   L.suffix + R.prefixL.prefix + R.suffixL.total + R.totalL.best + R.best
5. 5. Read this claim: a leaf sets best to max(0, value), which is correct because an empty run is always allowed. Is the claim true or false, and why?

   True, because an empty run always has sum 0, so it can be the best answer for any arrayFalse, because every run must hold at least one value, so a leaf's best must be its own valueTrue, because max(0, value) makes the tree skip negative leaves without an errorFalse, because the merge would then change the total of the parent