Problem $1.$

In the tree above perform $($a$)$ inorder, $($b$)$ preorder, $($c$)$ postorder traversals. Show your results.

Problem $2.$

Compress the text below $($alphabetic characters only$)$ using Huffman coding. What is the total number of bits used

for the compressed text $($ignore table storage requirements$)?$

ABR.ACADABR.AZABR.AZEBRA

Problem $3.$

Solve the following recurrence relations by providing asymptotically tight bounds. You only need to provide the

bound, intermediate derivations are not required. If no boundary case is given, the choice of the constants is

yours. You may assume that $T(n)$ is positive and monotonically increasing, if you need to do so$.$

$(1)T(n)=4T(\frac{n}{2})+n^2.$

$(2)T(n)=8T(\frac{n}{2})+n$

$(3)T(n)=T(n-1)+\frac{n}{2}.$