Question

4 Applications a. Let us invent a new game, called Siz degrees of Tim Berners-Lee. The goal is, given a Twitter handle say @cab203 find a chain of at most six Twitter handles, starting at @cab203 and ending at etimberners_lee, where every pair of adjacent Twitter handles in the chain appear on some web page together. The questions below are concerned with building a program that plays the game. (To be clear, you will not have to play this game or build any programs!) i. Discuss a reasonable use of regular expressions in building such a program ii. Discuss a reasonable use of graphs in building such a program. iii. Discuss a graph theoretic problem that relates to building such a program iv. Would you use breadth-first or depth-first traversal in solving the above problem? What are the reasons for your choice?

Answer 1

I can help you with answering question 2 through 4.

2:- Represent the problem in the form of graphs. By graphs here I mean a set of vertices connected together by a set of edges. In this case, represent each username in the form of vertices/nodes. Now as the question suggests we scan every webpage and in each webpage, we connect the usernames present in those webpages directly by an edge. For-ex:- if a webpage contains the usernames A, B, and C. Then we connect A and B directly with an edge, A and C with an edge and B and C directly with an edge. Then once we have built the graph from the usernames we can use various available algorithms(discussed in the upcoming sections) to find a six-degree of separation from the username - "timberners_lee".

3:- The graph-theoretic problem that is related to this problem is given a pair of nodes (source and destination) find whether they are most a given distance apart from each other or not. To do this, we calculate the minimum distance from the source node to the destination node. If the minimum distance from the source node to the destination node is greater than the given distance then there is no shorter path available and hence we cannot reach the destination node in at most the given distance length.

4:- We will use breadth-first search to solve this problem. Since we are interested in finding the shortest path between a given pair of nodes, breadth-first search on a graph calculates the shortest path from a given node to any other node. For this problem, what we do is that given the starting user name from that we can find its corresponding node in the graph and that becomes the source node, now the destination node remains the same. So we start breadth-first search from the source node and calculate the minimum distance to all the other nodes(breadth-first search calculates this by default). Once we have calculated the minimum distance we can then check whether the minimum distance is less than or equal to six or not, if so then the two usernames are six-degree length separated else they are not. One important thing we can notice that the shortest distance property is symmetric in nature and instead of calculating the shortest distance every time for different source nodes we can just use breadth-first once with the destination node as the source this time and calculate the minimum distance from the destination node instead. This would save us time in reducing the overall complexity of the problem because whether we use A to calculate the minimum distance from A to B or we use B to calculate the minimum distance from B to A, the concept and the idea remains the same.

Thank you. I hope I have explained it the way I intended to and if you have any problem feel free to ask them in the comment section and I will be more than happy to help you out. Have fun.