Dynamic Programming. You$$ve been assigned to your company$$s Do$-$

main Name System $($DNS$)$ team. DNS is a hierarchical decentralized naming system for

computers, services, or other resources connected to the Internet or a private network. It

associates various information with domain names assigned to each of the participating

entities. Most prominently, it translates more readily memorized domain names to the

numerical IP addresses needed for locating and identifying computer services and devices

with the underlying network protocols.

Your team lead has assigned you to the task of ensuring the DNS look$-$ups are as fast as

possible. After a lengthy discussion with your tech director, you$$ve decided to store do$-$

mains names alphabetically in a binary search tree $($BST$)$ along with their IP addresses,

because look$-$ups are relatively fast. But to improve performance, you want to optimally

arrange the BST according to the probability a given domain name is looked up$.$

$($a$)$ Given a list of domain names and their associated IP addresses and the probability

of a look$-$up for that domain name, write a pseudo$-$code algorithm that creates an

optimally arranged BST$.$

$($b$)$ Apply your algorithm to these data:

web site google.com boisestate.edu irs.gov wikipedia.com cat$-$bounce.com

IP $74\mathrm{.}125\mathrm{.}28\mathrm{.}100132\mathrm{.}178\mathrm{.}214\mathrm{.}91166\mathrm{.}123\mathrm{.}218\mathrm{.}220198\mathrm{.}35\mathrm{.}26\mathrm{.}96205\mathrm{.}186\mathrm{.}179\mathrm{.}214$

prob. $0\mathrm{.}150\mathrm{.}050\mathrm{.}20\mathrm{.}10\mathrm{.}5$

CS $421-$ Fall $2024$