Input format
• Needed to structure the info in input files
• Assume there are n web pages numbered from 0 to n-1 90-10 rule
• Assume 90% of the time the
o Represent links with ordered pairs of these numbers random surfer clicks a random
1. Page containing the link link on the current page (each
2. Page to which it refers with = probability)
• Input format = input stream of integer (n) + sequence of pairs of integers • 10% of the time the random
surfer goes directly to a
• StdIn → treats all sequences of whitespace characters as a single delimiter
random page (all pages on web
o Can put one link per line or several links in one line have = probability)
Transition matrix
• 2D matrix to specify behaviour of random
surfer
o n web pages
o n-by-n matrix
▪ Value in row i & column j =
probability that random surfer
moves to page j when on page i
• Write code that can create this matrix for any
given input
o Read n & create arrays counts[][] and
outDegrees[]
o Read links & build counts so counts[i][j]
counts the links from I to j &
outDegrees[i] counts the links from i to
anywhere
o Use 90-10 rule to compute the
probabilities
• Program 1.6.1: filter that reads a graph from
standard input & prints associated transition
matrix to standard output
• Significant because each row represents a
discrete probability distribution (elements fully
specify behaviour of surfing to each page)
• Output defines file format for matrices
(numbers of rows & cols + values of matrix
elements in row-major order)
1
• Needed to structure the info in input files
• Assume there are n web pages numbered from 0 to n-1 90-10 rule
• Assume 90% of the time the
o Represent links with ordered pairs of these numbers random surfer clicks a random
1. Page containing the link link on the current page (each
2. Page to which it refers with = probability)
• Input format = input stream of integer (n) + sequence of pairs of integers • 10% of the time the random
surfer goes directly to a
• StdIn → treats all sequences of whitespace characters as a single delimiter
random page (all pages on web
o Can put one link per line or several links in one line have = probability)
Transition matrix
• 2D matrix to specify behaviour of random
surfer
o n web pages
o n-by-n matrix
▪ Value in row i & column j =
probability that random surfer
moves to page j when on page i
• Write code that can create this matrix for any
given input
o Read n & create arrays counts[][] and
outDegrees[]
o Read links & build counts so counts[i][j]
counts the links from I to j &
outDegrees[i] counts the links from i to
anywhere
o Use 90-10 rule to compute the
probabilities
• Program 1.6.1: filter that reads a graph from
standard input & prints associated transition
matrix to standard output
• Significant because each row represents a
discrete probability distribution (elements fully
specify behaviour of surfing to each page)
• Output defines file format for matrices
(numbers of rows & cols + values of matrix
elements in row-major order)
1
