Computational Advertising  Homework 1

CS 498: Computational Advertising 
Homework 1

1 General Instructions
• This assignment is due at 11:59 PM on the due date. We will be using Gradescope for collecting the
non-programming part of this assignment and Compass (http://compass2g.illinois.edu) for collecting
the coding part of this assignment.
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.
• It is OK to discuss with your classmates and TAs regarding the methods, but it is NOT OK to
work together or share code. Plagiarism is an academic violation to copy, to include text from other
sources, including online sources, without proper citation. To get a better idea of what constitutes
plagiarism, consult the CS Honor code (http://cs.illinois.edu/academics/honor-code) on academic
integrity violations, including examples, and recommended penalties. There is a zero tolerance policy
on academic integrity violations; Any student found to be violating this code will be subject to
disciplinary action.
• Please use Piazza if you have questions about the homework. Also, feel free to send TAs emails and
come to office hours.
Questions 1, 2 and 3 are based on Chapter 6 on Games1
.
2 Question 1 (2 points)
In Section 6.11 (Exercises), solve Problem (3).
1https://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch06.pdf
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