Problem $1(10$ marks$).$ A binary ponga is a binary tree whose leaves are labelled with integers and Problem $1(10$ marks$).$ A binary ponga is a binary tree whose leaves are labelled with integers and

every internal node is labelled with the sum of its immediate children.

a$)$ Describe an algorithm that, given a list of integers $a,$ constructs a binary ponga whose leaves

are the elements of $a,$ in the same order they are given. Explain why the algorithm is correct

and compute its running time. To obtain full marks your algorithm should run in linear time.

b$)$ Describe an algorithm that, given the binary ponga corresponding to a list of integers $a,$ and

indices i and $j,$ outputs the sum $a[i]+a[i+1]+$cdots$+a[j].$ Explain why the algorithm is

correct. To obtain full marks your algorithm should make use of the information stored on

internal nodes and not merely sum the leaves.

Represent the binary ponga with an array and implicit pointers, analogously to how a binary heap

is represented with an array. You may assume for simplicity that the size of $a$ is a power of $2$ and

hence the tree is complete.

Bonus $($not marked$)$: Show that the sum algorithm runs in logarithmic time.

every internal node is labelled with the sum of its immediate children.

a$)$ Describe an algorithm that, given a list of integers $a,$ constructs a binary ponga whose leaves

are the elements of $a,$ in the same order they are given. Explain why the algorithm is correct

and compute its running time. To obtain full marks your algorithm should run in linear time.

b$)$ Describe an algorithm that, given the binary ponga corresponding to a list of integers $a,$ and

indices i and $j,$ outputs the sum $a[i]+a[i+1]+$cdots$+a[j].$ Explain why the algorithm is

correct. To obtain full marks your algorithm should make use of the information stored on

internal nodes and not merely sum the leaves.

Represent the binary ponga with an array and implicit pointers, analogously to how a binary heap

is represented with an array. You may assume for simplicity that the size of $a$ is a power of $2$ and

hence the tree is complete.

Bonus $($not marked$)$: Show that the sum algorithm runs in logarithmic time.