$[$Goodrich$-$Tamassia, C$-3\mathrm{.}23,$ C$-3\mathrm{.}24,$ p$.215]$ Let $T$ be a Splay Tree consisting of the $n$ sorted keys $($:$x_1,x_2,$dots,$x_n$:$).$ Consider arf arbitrary sequence $s$ of $m$ successful searches on items in $T.$ Let $f_i$ be the access frequency of $x_i$ in $s.$ Assume each item is searched at least once $($i$.$e$.,f_{i}1$ for each $i=1..$n$).$

$($a$)$ Show that the total execution time for sequence $s$ on the Splay tree starting with $T$ is

$O(m+{\displaystyle \underset{i=1}{\overset{n}{}}}{f}_{i}log(\frac{m}{f_i})).$

$[$Hint: Modify the potential function by redefining the weight of a node as the sum of access frequencies of its descendants including itself.$]$

$($b$)$ Design and analyze an algorithm that constructs an off$-$line static $($i$.$e$.,$ fixed$)$ Binary Search Tree $T^{\text{'}}$ consisting of the same items $($:$x_1,x_2,$dots,$x_n$:$),$ such that depth of item $x_i$ in $T^{\text{'}}$ is $O(log(\frac{m}{f_i})).$ Your algorithm should take at most $O(nlogn)$ time, and for an extra credit, it should take $O(n)$ time. $[$Hint: Let $x_i$ be the root, where $i$ is the smallest index such that $f_1+f_2+$dots$+f_i\frac{m}{2}.$ Recurse on that idea over the subtrees.$]$

$($c$)$ How do parts $($a$)$ and $($b$)$ above compare the execution times over the access sequence s on the online self$-$adjusting Splay tree $T$ versus the off$-$line static binary search tree $T^{\text{'}}?$

$[$Hint: You may also consult $[$CLRS $14\mathrm{.}5],$ AAW, and my EECS$3101$ Lecture Note $9$ and Slide $7$ on Knuth's dynamic programming algorithm that constructs the optimal static binary search tree.$]$

$25$