CS50x Week 8

Trees

We learned trie last week, trie is a type of data structure called tree. Tree has a node at the top, called root, then it has 0 or more nodes, called children. If a node does not have any child, it is called leaf.

Tree data structure
Tree data structure

Binary tree

When each node of a tree has at most 2 children, we call it binary tree. In a binary tree, the left children of a node is smaller than itself while the right children is bigger.

Binary tree can be implemented using structure below as a node:

n is the value of the node, and each node contains a pointer to the left children and a pointer to the right children.

Binary tree has some characteristics that allows us to implement the below search function:

The function takes two arguments, n is the value we want to search in the binary tree, tree is a pointer to the root node. If the pointer to the root node is NULL, signifying there is nothing in the binary tree, we return false. If the value we want to search is less than tree->n (which is the root node’s n  value), we proceed to search the tree on the left side. This is the special characteristics of binary tree, the left children is always less than the parent. Next, if the value we want to search is more, we search the right side. Lastly, if the value we want to search is equals to tree->n, then we return true immediately.

LIFO and FIFO

LIFO (Last In, First Out) and FIFO (First In, First Out) are two ways to store and retrieve data

LIFO

Stack uses the LIFO concept. Stack has two operations, push and pop, push means adding data, pop means removing data. When we push data to the stack, it is added on top, when we pop data from the stack, it is removed from the top, so the last data added gets removed first.

To implement a stack, we can make use of structure:

size is the number of elements currently on the stack, CAPACITY is a constant defined as the maximum number of elements allowed on the stack. Let’s take an example, CAPACITY = 3. When we push an element into the stack, say 37, size will become 1, and elements[0] becomes 37. Then, we add a second element, 45, size becomes 2, elements[1] becomes 47. We continue pushing data onto the stack until it hits the CAPACITY. This implementation of stack is not useful because the number of elements that we can push is limited by the CAPACITY. We can improve this implementation by introducing linked list replacing the array.

FIFO

Queue uses the FIFO concept. Queue has two operations, enqueue and dequeue. Enqueue adds data to the queue and dequeue removes data from the queue. We can think of queue as people lining up for a movie. The first person that is enqueue gets to dequeue first while the last person dequeue last.

To implement queue, we can use the following structure:

size is the number of elements currently on the queue, and front keeps track of the next element to be dequeue. Say we enqueue the following elements, 35, 89, 17. The size will be 3, front will be 0, elements[0] = 35, elements[1] = 89, and elements[2] = 17. When we wants to dequeue an element, we refer to front. Since front is 0, elements[0] gets dequeue first. front now becomes 1, size becomes 2. If we dequeue again, front is 1, hence elements[1] gets dequeued, front becomes 2, size becomes 1. If we now wants to enqueue data, it will be added to elements[0], because there is no elements[3], so we have to wrap around and put at 0th index. After enqueuing, the next data to be dequeue will be 2, eventhough elements[0] might appear to be in front of elements[2]. This is because elements[0] arrives later than elements[2].

The internet

HTTP (Hyptertext transfer protocol) defines the protocol/ rule of communication between browser and web server. We send HTTP requests from our browser to the server, and server may respond by sending us HTML file that displays the website. Servers has different port for different services, the default port number for HTTP request is 80, which accesses the website. Port 25 is used for mail. Whenever we type a website, say facebook.com, we are actually typing http://facebook.com:80, http:// is automatically added and 80 is the default port.

To see HTTP traffic, you can go to tools>Developer tools, click on the network tab. Go and type http://google.com in your browser and hit enter, you will receive HTTP response from Google, click on headers to see your request and their response. Click on the view source of response header, if you see HTTP/1.1 200 OK, this means everything is working ok, 200 is the “all is well” HTTP status code. You may know some other HTTP status code such as 404, which is “not found” HTTP status code.

IP stands for internet protocol, is an identifier for a computer on the internet. Each web server is associated with IP, How does our browser know which web server is associated to which IP? DNS. Domain name system translates website name to IP.

TCP/ IP  defines the protocol/ rule of how information transfer through the internet. Information travels from source to us through several routers in between. We can type traceroute www.facebook.com to see which router our request went through and the time in milliseconds it took. Besides router sitting between the source and us, there are firewalls. Our source may be sitting behind the firewall, but our access is restricted. Firewall may reject our HTTP request by looking at our IP, or the firewall may reject us from accessing certain port, say port 25, restricting us from sending email to the source.

For efficiency, HTTP requests are broken up into pieces called packets.These packets may not follow the same path, some may be dropped during the journey. Since the packets is numbered in order, the receiving end can know if they had received all our packets, if not, a request is sent again.

Other posts in the series: Harvard CS50x 2014

Leave a Reply