Description

1 General Instructions
Contact TAs if you face technical difficulties in submitting the assignment. We shall NOT accept any late submission!
• The non-programming part of homework MUST be submitted in pdf format on gradescope. Please register yourself on gradescope with your illinois.edu email. The course entry code is: 9B524G
Please make sure to appropriately map/assign the pages of your submitted pdf to each sub-question listed in the homework outline. Handwritten answers are not acceptable. Name your pdf file as YourNetid-HW1.pdf
• For Questions 1, 2 and 3, you need to explain the logic of your answer/result for every sub-part. A result/answer without any explanation will not receive any points.
• For the programming question of the assignment, you must (a) submit written answers with plots, etc. along with questions 1 to 3, and (b) submit your code in compass. Name your compass submission as YourNetid-LastName.zip.
Questions 1, 2 and 3 are based on Chapter 6 on Games .
2 Question 1 (2 points)
In Section 6.11 (Exercises), solve Problem (3).
1
3 Question 2 (4 points)
In Section 6.11 (Exercises), solve Problem (4). In part (b), you must show the precise steps to arrive at your answers. Each part carries 2 points.
4 Question 3 (9 points)
In Section 6.11 (Exercises), solve Problem (6). You must show precise steps on how you arrive at your answer for each part. Each part carries 3 points.
5 Programming Question (15 points)
The objective of the programming assignment is to give you a better understanding of page rank. We have provided you two graphs with 100 nodes each. You can find the list of the node ids and their categories in the file nodes.txt. The edges for the graphs can be found in the files network1 edges.txt and network2 edges.txt respectively.
Apply the page rank algorithm on the graphs separately for 100 iterations. You are free to use methods from existing libraries like NetworkX (https://networkx.github.io), SNAP (https://snap.stanford.edu/snappy/), etc.
Now, answer the following questions based on your result of Page Rank Algorithm.
1. For a search query on category Sports, list out the top-10 nodes in decreasing order of pagerank for network1.
2. For a search query on category Politics, list out the top-10 nodes in decreasing order of pagerank for network2.
3. Plot a graph showing the variation in page rank value of node with id 2 for network1 over 100 iterations.
4. Plot a graph showing the variation in page rank value of node with id 2 for network2 over 100 iterations.
5. Explain the difference in the page rank of Node 2 for the two networks.
Include the answers for the questions in the pdf for the non-programming part. You need to submit the code for page rank in Compass.
2