Routing Tree

Today, when we want to access a website on the Internet, we do not need to know its IP address and type it into our browsers. Websites are identifiable by their domain name. For example ‘fau.de’ is the domain name of our university’s main web page. However, ‘fau.de’ is the name we as humans can understand. Our computers cannot assign any meaning to this and would not be able to go to the location on the internet where it is located. For this, there is the so-called Domain Name System or short DNS.

The Domain Name System is on a basic level similar to a phone book. You know the name of a person which you then look up in the phone book, and you can then find out that person’s address. With the DNS it works as per the following. Us the user sends a request for the domain name ‘fau.de’ into the internet. The DNS then transforms the domain name into the corresponding IP address, the location where our computer can find the ‘fau.de’ web page. So when we type ‘fau.de’ into our browser what will happen is we will send a request for the IP address of this domain. The DNS will then return “2001:638:a000:1080::209” Which is the IP address of the requested domain.

In this exercise, we want to store domain names, and their corresponding IP addresses an inefficient data structure to create our DNS. To do so we have provided you with some starter code.

routing

Getting Started

Log into the CS50 IDE and then, in a terminal window, execute each of the below

  1. Execute cd to ensure that you’re in ~/ (i.e., your home directory).
  2. Execute mkdir Graphs_Trees to make (i.e., create) a directory called Graphs_Trees in your home directory.
  3. Execute cd Graphs_Trees to change into that directory
  4. Execute wget introcs.is.rw.fau.de/assets/pdfs/routing_tree.zip to download a (compressed) ZIP file with this problem’s distribution.
  5. Execute unzip routing_tree.zip to uncompress that file.
  6. Execute rm routing_tree.zip followed by yes or y to delete that ZIP file.
  7. Execute cd Routing to change into the extracted directory.
  8. Execute ls. You should see this problem’s distribution: routing_tree.py, dns.py and do_ip.csv

Do not change anything in dns.py.

Specification

To create our DNS, we have to store our domain names with their corresponding IP addresses in a data structure. We will use a Binary Search Tree (BST), which you will have to implement in routing_tree.py. dns.py is a controller script that takes care of minor things for you. You can run it to validate your routing_tree.py file.

Let’s walk through dns.py. Its main task is to fetch the data used to build the tree and then execute commands to work with the tree on completion. The most relevant thing in dns.py is the read_csv method, which takes the do_ip.csv file and then returns the domain name and the corresponding IP address. These pairs are then used to build a BST. You can always run dns.py to see whether you’re implementing routing_tree.py correctly.

Let’s get to the critical bits! The actual routing tree. You should be familiar with the concept of the BST from the lecture. If you do not know what a BST is, please watch the lecture and corresponding shorts first.

You only need to modify ‘routing_tree.py’. Let’s look at your tasks. We have created a class BST that has a class attribute root that is set to None initially. Furthermore, we have some attributes in the class constructor. The domain and the IP, which are the only arguments we give when creating an instance of class BST. Furthermore, there are the left and right children which are always initiated with the value None. Now that being said, the BST here can also be treated as a Node with specific attributes. However, the root node should be accessible from any instance of class BST, which is why it is a class attribute.

All the methods of BST are static methods. In our case, we assign them to the class since all their operations relate to the routing BST.

Be aware that you can not change anything about the parameters and arguments a method can take.

You can add as many helper methods (static or object-oriented) as you like, which might come in handy if you want to implement your tree recursively.

add()

This is where we start building our DNS-BST in Python. You should build the tree by the alphabetical comparison of domain names! Once you call add(), make sure that root exists, then navigate through your tree according to the domain name and add a Node as either a left or right child of its preceding Node.

Hint: Be aware of the difference between class and instance attributes. Remember to call class attributes by referencing the class first. For example use the command Person.identity to access the class attribute “identity”.

Hint: Remember to use the constructor to create new nodes.

find()

Find takes a domain name and searches the tree for it. If the domain name you are looking for exists in the tree, this method should return the corresponding Node. If not, it should return false.

bfs()

This method returns a list with all Nodes in the BST according to the breadth-first search. The start for your BFS should always be the root of your tree.

If implemented correctly, the BFS should return the following list.:

['pinterest.com', 'facebook.com', 'yahoo.com', 'google.com', 'twitter.com', 'youtube.com', 'geeksforgeeks.org', 'instagram.com', 'reddit.com', 'w3schools.com', 'quelle.de']

preorder()

This method should return a list of a DFS in pre-ordered fashion. It would be best if you again started at the root.

If implemented correctly, the DFS should return the following list.:

['pinterest.com', 'facebook.com', 'google.com', 'geeksforgeeks.org', 'instagram.com', 'yahoo.com', 'twitter.com', 'reddit.com', 'quelle.de.com', 'w3schools.com', 'youtube.com']

delete_method()

Your delete method should delete a node you specify in your tree. It takes the domain name and searches for it, then safely deleting it while keeping the properties and the BST intact.

As a hint, recall that there are 3 cases:

  1. A node has no child

  2. A node has one child

  3. A node has two children

check50

To check your program you can run this line in your terminal.

check50 fau-is/IntroCS/PyGraphsTrees/RoutingTree

submit50

To submit your program use this line of code.

submit50 fau-is/IntroCS/PyGraphsTrees/RoutingTree