Question $1(1$ point$)$

Consider the functions power $($base$,$ exp$)$ and betterPower $($base$,$ exp$)$ that recursively calculate

the value of base raised to exp

def power $(b,x)$ :

if $(x==0)$ :

return $1$

return $b^{**}$ power $(b,x-1)$

def betterPower$1($b$,x$ :

if $(x==0)$ :

return $1$

if $x\%2==0$ :

return betterPower $1(b,\frac{x}{\frac{?}{?}}2),**$ betterPower $)$

else:

return $b**$ betterPower $1(b,\frac{x}{\frac{?}{?}}2)**$ betterPower $)$

Compared to power $(b,x),$ betterPower$1(b,x)$ is:

has worse Big$-$O time complexity

has the same Big$-$O time complexity

has better Big$-$O time complexity

not comparable

Question $2(1$ point$)$

Consider an alphabet containing only the following $5$ characters, with the given

frequencies:

A Huffman tree was constructed with the following rules. When pairing $2$ items, the

one with the smaller frequency goes on the left. The left edge has label $0,$ and the

right edge has a label $1.$ If two items with the SAME frequency are being paired, then

this is how you must determine which one goes on the left:

if both items are characters in the alphabet above, then the one that is smaller, in

alphabetical order, as given above, goes on the left.

if one is a character of the alphabet, and the other is a created node, then the

created goes on the left

if both are created nodes, then the one was the one created first goes on the left.

What is the compression ratio between Huffman code and the most efficient bit

code that can represents these $5$ characters?

None of the other answers are correct

$1$:$2\mathrm{.}32$

$1$:$1$

$1$:$1\mathrm{.}36$

$1$:$1\mathrm{.}92$

Question $3(1$ point$)$

Using a stack to perform a pre$-$order traversal of an AVL tree will have a time

complexity of:

$O(log(n))$

$O(2^n)$

$O(n)$

$O(n*log(n))$