$1.$ In controlled prefix expansion with variable stride, what is the minimum number of trie nodes we need so that no more than two memory accesses are needed to perform an IP lookup $($i$.$e$.,$ longest prefix match$)$ against the rule set below. Please show some dynamic programming steps if you would like

to receive partial credits.

P$1=0000*$

P$2=0001*$

P$3=0010*$

P$4=001*$

P$5=01*$

P$6=1*$

P$7=110*$

P$8=111*$

$2.$ Spell out the digital logic of the following $4-$bit digital$-$to$-$analog converter

we mentioned in class that is roughly equivalent to the bit$-$mask function.

The inputs are i$1($the least significant bit$),$ i$2,$ i$3,$ and i$4.$ The outputs are

j$1,$ j$2,,$ j$15.$ If the binary number $($i$4$i$3$i$2$i$1)2$ has value k$,$ then j$1=$ j$2=$

$=$ jk $=1$ and the rest is $0.$ You need to spell out the formula for each jl

$(1<=$ l $<=15)$ as a logic function of the inputs. Please use notations $($for

OR$),($for AND$),$ and $($for NOT$).$

$3.$ Suppose $1$ million nodes are hashed into a hash table that contains $1$ mil$-$

lion buckets. On average, what is the total number of overflows if each bucket

can hold at most $3$ nodes. You may assume that the hash function is strictly

uniform $($across the $1$ million indices$/$buckets$).$ You may also approximate

the Bernoulli random variable you will encounter in this case with a Poisson

random variable $($since $1$ million is a large enough number$).$ Please write the

$($approximate$)$ formula and calculate the numerical value $($say using Matlab$).$