# Modelling a DNS

<div class=ribbon> <a href="https://github.com/MarcScott/7-CS-Internet">Fork me on GitHub</a> </div>

## 1 Learning Objectives…

• In this lesson you will develop an understanding of the learning strand Algorithms on your progress ladder, working towards yellow/green level.

### Understanding and being able to:

• Explain what a DNS is and why we use them
• Contruct a Scratch program to demonstrate a DNS
• How to use loops (Iteration) in Sratch
• How to use the ask and answer blocks in Scratch to receive user input in Scratch
• Know how a Linear Search operates and how it is used in a list

## 2 Modelling a DNS table

### Research It

• A Domain Name Server has a table stored on it, that will look something like this:
bbc.co.uk 212.58.246.90
• It is a simplication of the actual data on a DNS
• If you want to find out more, here is a good article on this.

### Code It

• We're going to have to build a DNS Table to begin with. This is going to be made up of two lists.
• In Scratch, create a new list called `Domain Names` and then another list called `IP Addresses`

### Code It

• We're going to need a few Domain names and IP Addresses to populate our table. About 1000 of each should do the trick.
• This would take ages by hand, but luckily Scratch allows us to import text files.
• In your Scratch window, right click on the gray box that represents the Domain Names list and choose import from the context menu.
• Do the same for the IP Addresses list and you should end up with something that looks like this.

## 3 Linear Search

### Research It

• When you type in a URL into a web-browser address bar, your computer consults the DNS server, to find the IP address.
• The DNS server has to look up the domain name and find the corresponding IP address
• To do this the server needs to use a searching algorithm.

### Learn It

• A linear search is a method of going through a list of items, one by one, and checking each item.
• Imagine we had a list of 'things'

`[cat,dog,horse,mouse,rabbit,parrot,elephant]`

• If we wanted a computer to program to find the position of the element

`parrot` it would check from left to right

• The program would check what was at position 1, see if it was parrot and if it wasn't it would move onto position 2, and so on.
• Luckily, computers can do this exceptionally quickly.

## 4 Indexing a list

### Learn It

• As a computer reads through a list, it needs to keep track of where it is. This is what an index is for.
• Imagine we have the following two lists:
```OperatingSystems = ['Mac OSX','Windows 8','Android','iOS','Ubuntu']
Rating = ['4/5','2/5','4/5','3/5','5/5']
```
• The items in the first list are Operating systems.
• The items in the second list give a user rating out of 5.
• Imagine we wanted to find out the rating out of 5 for Android.
• We could step through the list of operating systems until we found Android.
• This would not tell us where to find the rating out of five in the second list though. It would just tell us that Android exists in the first list.
```OperatingSystems = ['Mac OSX','Windows 8','Android','iOS','Ubuntu']
Rating = ['4/5','2/5','4/5','3/5','5/5']
```
• As we move through (iterate) the first list searching for 'Android', we keep a count of our position. The position is called the index of the list.
• The algorithm looks something like this:
```1. index = 1
2. Is Android at index (position 1)
3. No, so add 1 to index
4. Is Android at index (position 2)
5. No, so add 1 to index.
6. Is Android at index (position 3)
7. Yes. So look up index of the second list
8. index (position 3) of the second list is 4/5
9. So Android has a rating of 4/5
```

## 5 Using a linear search in our DNS.

• In our Scratch program so far we have a list of domain names and a list of IP addresses.
• We need to be able to conduct a linear search on the list of domain names to find the index of any given name.

### Code It

• Start by adding in a When `green flag` clicked block
• Now we'll ask the user for the domain name they're looking for.
• Next you'll need a couple of variables:
• Create a variable called `domain`
• Create a variable called `index`
• You should set the domain to be the answer of the `ask` block and the index to be the integer `1`

### Code It

• Our linear search algorithm could possibly need to search right to the end of the list. So we'll need to use a loop that keeps going until the index is at 1001.
• Currently `index` is `1`. So the algorithm needs to check the 1st item in domain names, and see if it matches the domain that the user is looking for. We can do this with a conditional `if/else` inside the `repeat until` loop.
• If the domain names do not match, then we want `index` to become `2`, and the algorithm to go back to the start of the loop.
• If however there is a match, then we know that the index of the IPs list will contain the IP address we're looking for.

### Run It

• Pick some random domain names from the list and use your algorithm to search for their IP addresses.
• Once you have an IP address you can copy and paste it into your browser's URL bar, and you should get directed to the site
• Not all of them will work however, as some sites use redirects and other trickery that will fool your browser.

### Document It

• Use screen shots and some text to try to explain how your Linear Search algorithm works.

### Learn It

Here's a quick recap of what you've covered so far.

• Domain names are easy for humans to read and remember.
• Each domain name links to an IP address that computers use to send messages to each other.
• A Domain Name Server (DNS) stores a table of domain names and IP addresses.
• When you type in a URL, your computer asks the DNS what the IP address is for the domain name.
• An item in a list can be referenced by its position, which is called it's index.
• Linear search is one method of finding an element in a list.