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...

1 answer below »

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 isrecommendedto upload justone.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/ XXXXXXXXXXpdf(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

Page Rank (1) (1)Page Rank (1) (1)
CriteriaRatingsPts
This criterion is linked to a Learning OutcomeImplementation
75to >0.0ptsTest Cases5 point per correct test case0ptsNo test cases passed
75pts
This criterion is linked to a Learning OutcomeData Structure used
2.5ptsFull MarksStates Data Structure used and the rationale1ptsPartial PointsStates Data Structure used only0ptsNo Marks
2.5pts
This criterion is linked to a Learning OutcomeReflectionWhat would you do differently?
2.5ptsFull MarksReflection on what you would do differently0ptsNo Marks
2.5pts
This criterion is linked to a Learning OutcomeComments
2.5to >0.0ptsFull MarksCode has appropriate comments0ptsNo Marks
2.5pts
This criterion is linked to a Learning OutcomeWhitespace
2.5to >0.0ptsFull MarksCode has appropriate whitespace0ptsNo Marks
2.5pts
This criterion is linked to a Learning OutcomeNaming convention
2.5to >0.0ptsFull MarksCode follows a naming convention that is coherent and consistent0ptsNo Marks
2.5pts
This criterion is linked to a Learning OutcomeModularityCode is modular with thought out design
2.5to >0.0ptsFull MarksCode has appropriate functions0ptsNo Marks
2.5pts
This criterion is linked to a Learning OutcomeComputational Complexity (Main)
5to >0.0ptsDescribing Complexity of main method1. Big O complexity of main method 2. Best case, Worst case and Average case described 3. The variables used in Big O are correct and same as in implementation0ptsNo Marks
5pts
This criterion is linked to a Learning OutcomeComputational Complexity (Methods)
5to >0.0ptsDescribing Complexity of each method1. Big O complexity of each method 2. Best case, Worst case and Average case described 3. The variables used in Big O are correct and same as in implementation0ptsNo Marks
5pts
Total Points:100
Answered 4 days AfterApr 11, 2022

Solution

Ashutosh answered on Apr 15 2022
11 Votes
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here