JAVA PROGRAM

The task is two write two Java program which read from the standard input and write to the standard output. One program provides the input to the other. This illustrate the power of good design and the significance of the standard IO package.

task 1

Modify the Java program Transition.java.

Use Scanner and System.out as usual. (No advantage in using the books private Java IO library, StdIO.)

As usual, follow cse1002 style guidelines and good design practices. Put your name in the header as usual, but give credit to the textbook.

Comment the program as if was your own code, and you know what you are doing. (Can you find any good places to use an assert statement?)

Extend the program to handle pages with no outgoing links, by filling in rows corresponding to such pages with the probability 1/n, where n is the number of columns.

Extend the program by taking a JVM argument leap as a parameter. The leap probabilty is a decimal fraction between 0.0 and 1.0. The default value is 0.1.

Extend the program by taking a JVM argument format as a parameter for the output forment of the matrix elements. The default value is " %.2f". (Note the space.)

Task 2

Modify the Java program RandomSurfer.java much like in Task 1.

Use Scanner and System.out as usual. (No advanatage in using the books private Java IO library.)

As usual, follow cse1002 style guidelines and good design practices. Put your name in the header as usual, but give credit to the textbook.

Comment the program as if was your own code, and you know what you are doing. (Can you find any good places to use an assert statement?)

Modify the program to create reproduciable sequences of random numbers in the manner of the last few Monte Carlo labs.

Do not use Math.random(). (Do you know why not?) But keep and observe carefully the manner of making a choice between weighted possibilities.

Extend the program by taking a JVM argument trials as a parameter for the number of steps the random surfer takes. The default number of trials is 1,000.

Modify the output of the program to print both the page number and the probability of landing on the page after the given number of trials. Use the format string "%2d: %6.3f%n".

INPUT & OUPUT:

//In Unix systems: java '-Dformat= %.2f' -Dleap=0.1 Transition < medium.txt | java -Dseed=1234 -Dtrials=1000 RandomSurfer //In windows systems: java "-Dformat= %.2f" -Dleap=0.1 Transition < medium.txt | java -Dseed=1234 -Dtrials=1000 RandomSurfer 

Note: here 0.1 is the leap probability this is the 90-10 rule. The 'format' is a string value, note that specifying %a for the string will convert the numbers into hexadecimal format

The first two lines of output for the command above are:

 0: 0.000 1: 0.010 

This means page 1 will rank higher than page 0 in all queries in which the page 0 and page 1 are found to be relevant.

The actual values computed by the power method (Markov.java) are closer to:

 0: 0.00223 1: 0.01855 

You are encouraged to experiment with the code in order to better understand the page rank algorithm. Why does it work so well?!

Transition.java public class Transition { public static void main(String[] args) { int n = StdIn.readInt(); // number of pages int[][] counts = new int[n][n]; // counts[i][j] = # links from page i to page j int[] outDegree = new int[n]; // outDegree[i] = # links from page i to anywhere // Accumulate link counts. while (!StdIn.isEmpty()) { int i = StdIn.readInt(); int j = StdIn.readInt(); outDegree[i]++; counts[i][j]++; } StdOut.println(n + " " + n); // Print probability distribution for row i. for (int i = 0; i < n; i++) { // Print probability for column j. for (int j = 0; j < n; j++) { double p = 0.90*counts[i][j]/outDegree[i] + 0.10/n; StdOut.printf("%7.5f ", p); } StdOut.println(); } } }

randomsurfer.java

public class RandomSurfer { public static void main(String[] args) { int trials = Integer.parseInt(args[0]); // number of moves int m = StdIn.readInt(); // number of pages - ignore since m = n int n = StdIn.readInt(); // number of pages if (m != n) { StdOut.println("m does not equal n"); return; } // Read transition matrix. double[][] p = new double[n][n]; // p[i][j] = prob. that surfer moves from page i to page j for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) p[i][j] = StdIn.readDouble(); int[] freq = new int[n]; // freq[i] = # times surfer hits page i // Start at page 0. int page = 0; for (int t = 0; t < trials; t++) { // Make one random move. double r = Math.random(); double sum = 0.0; for (int j = 0; j < n; j++) { // Find interval containing r. sum += p[page][j]; if (r < sum) { page = j; break; } } freq[page]++; } // Print page ranks. for (int i = 0; i < n; i++) { StdOut.printf("%8.5f", (double) freq[i] / trials); } StdOut.println(); } } 

medium.txt

50 0 7 0 34 1 14 1 22 1 22 1 45 2 19 2 25 2 33 3 4 3 17 3 27 3 36 3 42 4 17 4 17 4 27 4 27 5 43 6 13 6 13 6 28 7 41 8 19 8 48 9 11 9 30 9 46 10 0 10 7 10 28 10 28 10 28 10 29 10 29 10 41 11 21 11 30 12 9 12 11 12 21 12 21 12 26 12 26 13 22 13 23 13 47 14 8 14 48 15 34 15 49 16 9 17 20 17 24 17 38 18 6 18 28 18 32 18 42 19 15 19 40 20 3 20 35 20 36 20 46 21 1 21 14 21 22 22 6 23 11 23 21 23 22 24 4 24 5 24 38 25 34 26 9 26 26 26 48 27 5 27 24 27 31 28 22 28 39 28 44 29 49 29 22 30 23 30 37 31 18 31 32 32 5 32 6 32 13 32 27 32 37 32 47 33 8 33 19 34 2 34 19 34 40 35 9 35 46 36 42 37 5 37 9 37 35 37 35 37 47 38 35 38 37 39 18 39 42 40 15 41 28 41 44 42 31 43 24 43 37 43 38 44 7 44 39 45 8 45 14 45 14 45 15 45 49 46 16 47 23 47 30 48 12 48 21 48 33 48 33 49 1 49 34 49 22