## 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*