Problem Statement In this project you will be programming a simplified version of the Google's PageRank algorithm using an Adjacency List or equivalent implementation of the web graph. The project...

Problem Statement

In this project you will be programming a simplified version of the Google's PageRank algorithm using an Adjacency List or equivalent implementation of the web graph. The project description handout can be found here:Project Handout.

Testing

• Test your code on Stepik before submitting your implementation. You have three available test cases and you can submit any number of times. Thefourthtest case is fake to prevent you from accessing your peer's code. Link to Stepik:https://stepik.org/lesson/672839/step/1?unit=671091(Links to an external site.)
  


• Create your own tests and test as much as possible. Our recommendation is you spendat least 3-4 hourson testing extensively. Instead of using the submit button, use theRunbutton next to submit to test your own test cases on Stepik. This is strongly encouraged and it is a good practice to create your own test cases. Anyone who creates them and needs help on verification, feel free to contact the Instructor or use slack to verify a test cases with your peers.


• 
  We will stick to the input format.No need to test for off-input statement such as inputting one url instead of two in a line or testing whether a url is valid or not.

Grading

• 
  Implementation [75 points]
  
  
  
  • Your code will be tested on 15 test cases each worth 5 points:
    
    
    • 3 publicly available test cases.
    
    
    • 12 test cases that will be added by the course staff and are not shown to the students.
    
    
    • On Stepik, test case 4 is fake. So if your code passes test case 1-3. That means you will get 15/75 points automatically.
    
    
    
    
  
  
  
  

• 
  Documentation [15 Points]
  
  
  
  • Submit a document addressing all these prompts:
    
    
    • Describe the data structure you used to implement the graph and why? [2.5 points]
    
    
    • What is the computational complexity of each method in your implementation? Reflect for each scenario: Best, Worst and Average. [5 points]
    
    
    • What is the computational complexity of your main method in your implementation? Reflect for each scenario: Best, Worst and Average. [5 points]
    
    
    • What did you learn from this assignment and what would you do differently if you had to start over? [2.5 points]
    
    
    
    
  
  
  
  

• 
  Code Style and Design [10 Points]
  
  
  
  • 2.5 points for design decisions and code modularity
  
  
  • 2.5 points for appropriate comments
    
  
  
  • 2.5 points for white-spaces
  
  
  • 2.5 points for consistent naming conventions
  
  
  
  

Submission

• One or more .cpp or.h files that have your implementation. It is
  recommended
  to upload just
  one
  .cpp or .h file that has all your implementation. Remember this code should be the same that you tested on Stepik.


• One pdf file that has your documentation preferably between 1 - 3 pages.

Frequently Asked Questions

• Based on the number of repeated questions we got in Project 1 on Slack, the course staff will now maintain an active FAQ Google document to answer your questions. Post your questions in Slack, but this time we will answer in this document and send you the link. The link to the document is:https://docs.google.com/document/d/1a9hR1Ep2IYK-MnsXwl2VxyotO1Yd-XCC8NWUkdp24JM/(Links to an external site.)
  

Additional Optional Resources

• Page Rank Paper:http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf(Links to an external site.)
  


• Videos on Page Rank (The assignment is based on these videos):Lectures 5-8(Links to an external site.)
  


• Extended Videos (Not required for Project):Lecture 9-11(Links to an external site.)
  

Rubric