18.06 Spring 2006 : Problem Set #2

due 4PM Wednesday 2/22

(Asterisk means the solution is in the back of the book)

Section 2.6:   6*, 13, 16, 28
Section 2.7:   4*, 7, 11, 13, 17, 19
Section 3.1:   10, 19, 23*, 25*, 27

MATLAB PROBLEM: I hope this will be fun. Grab the surfer.m and pagerank.m files from http://www.mathworks.com/moler/ncmfilelist.html .

I was just playing with surfer.m. It's not as robust as I would have liked. When I run it on the 18.06 web page, it hangs on the java applets, and on other web pages it does not distinguish real links from little gif's for bullets. If anyone writes, borrows, or steals a better surfer.m, please send to me (edelman@Mit.edu) and I will post. Note MATLAB has a jdk inside so it can be written in matlab or java.

This one ran more cleanly: [u,g]=surfer('http://web.mit.edu/newsoffice',50)

It's fun to watch. A dot in (i,j) means that link j points to link i. The internet is a huge sparse matrix. g(i,j) is 1 or 0, there is a link or there is not. u(i) contains the name of the link.

Here is a poor man's pagerank. What is it doing?:

[a,b]=sort(full(sum(g,2)),'descend'); u(b)

In pagerank there is a line

x = (I - p*G*D)\e;

which is the solution of an nxn system with a sparse matrix.

See if you can find another link that gives a nice matrix: sparse but still lots of links, not just junky links or ones that hang. Compare this with pagerank's answer which uses fancy linear algebra algorithms. Is pagerank in your opinion significantly better than the poor man's algorithm? Note there is no right answer here. Main point is to have fun and see how useful linear algebra can be.

Copyright © 2003 Massachusetts Institute of Technology