$[30$ points $]$ assignPageRanks and computeRanks

The method computeRanks is a helper method for assignPageRanks. We specifically ask you to implement it so that our grader will be able to assign partial marks to your implementation. The purpose of assignPageRanks is to assign a rank to each vertex in

$6$

the web graph. It will only be called after crawlAndIndex has been executed. Here are the principles we will be using to assign a rank to a web page:

Good web pages are cited by many other pages. If we think about it in terms of the webgraph, this means that we should prefer web pages $($i$.$e$.$ vertices$)$ with a large in$-$degree.

Web pages that link to a large number of other pages are less valuable. In terms of webgraph, this means that we will value less web pages $($i$.$e$.$ vertices$)$ with a large out$-$degree.

A link from a web page is more valuable if the web page is itself a good one. In graph terms, higher the rank of a web page $($i$.$e$.$ vertex$),$ more valuable an in$-$edge from it would be$.$

Note that the rank of a page depends solely on the structure of the graph we have created while crawling. To represent the ideas just described, let

the $pr(w)$ be the page rank of a vertex $w$

the out $(w)$ be the out$-$degree of a vertex $w$

$w_1,w_2,$dots,$w_k$ be all the vertices in the graph that have an out edge going into $v.$

Then, the following equation determines the page rank of a vertex $v$ :

$pr(v)=(1-d)+d**(\frac{pr(w_1)}{\text{o}\text{u}\text{t}(w_1)}+\frac{pr(w_2)}{\text{o}\text{u}\text{t}(w_2)}+$dots$\frac{pr(w_k)}{\text{o}\text{u}\text{t}(w_k)})$

The constant $d$ is called the damping factor and it is added for technical reasons to account for the probability that an imaginary surfer who is randomly clicking on links will eventually stop clicking. For this project, we will be using a damping factor of $0\mathrm{.}5.$ As you may notice, $pr(v)$ is defined as a function of $pr(w_i).$ If $N$ is the total number of vertices in the graph $(v_1,v_2,$dots,$v_N),$ then we have a system of $N$ linear equations in $N$ variables. The unknown values, i$.$e$.$ our variables, are the $pr(v_i).$ To determine their values, we should solve the system of linear equations described above. To do so$,$ we could use linear algebra, but the implementation of gaussian elimination runs in $O(n^3).$ To improve the efficiency, we can instead use an iterative algorithm that approximate the result. The idea is the following:

Start by initializing $pr(v_i)$ to $1$ for all $0iN$

Repeat the following until convergence:

compute $pr(v_i)$ for all i using the formula above.

This single step is what the helper method computeRanks should be doing. The method takes as input an ArrayList