\documentclass{article}

% Packages required to support encoding
\usepackage{ucs}
\usepackage[utf8x]{inputenc}

% Packages required by code


% Packages always used
\usepackage{hyperref}
\usepackage{xspace}
\usepackage[usenames,dvipsnames]{color}
\hypersetup{colorlinks=true,urlcolor=blue}

\input{preamble.tex}


\begin{document} 
\hypertarget{homework_2_1}{}\section*{{Homework 2}}\label{homework_2_1}

\hypertarget{due_friday_october_7th_2011_by_5pm_printed_in_my_office_or_via_email_2}{}\subsection*{{Due Friday, October 7th, 2011 by 5pm printed in my office or via email.}}\label{due_friday_october_7th_2011_by_5pm_printed_in_my_office_or_via_email_2}

\hypertarget{problem_1_shortest_path_computations_3}{}\subsection*{{Problem 1: Shortest path computations}}\label{problem_1_shortest_path_computations_3}

\textbf{from the in-class quiz} In class we saw how to compute single-source shortest path distances by using a matrix-over-a-semiring. Recall the algorithm from class:

\begin{displaymath}
\mA^{\circ k} \ve_i = \underbrace{\mA \circ \mA \circ \cdot \mA}_{k \text{ times}} \circ \ve_i.
\end{displaymath}
\textbf{a)} Show how to adapt this to the problem of all-pairs shortest paths.

\textbf{b) just think about it} The following question is open-ended. I don'{}t have an answer, nor do I think there is one right answer.\newline Just write down some of your thoughts about the question. This is a chance for you to explore the material yourselfs.

If you wanted to approximate all pairs shortest paths less expensively, what would you do? (Please don'{}t describe how to implement the Floyd-Warshall procedure, think about approximating the shorest paths and doing so in a matrix sense.)

\hypertarget{problem_2_4}{}\subsection*{{Problem 2}}\label{problem_2_4}

Kleinberg'{}s HITS algorithm on a graph computes a hub-score and an authority-score for each vertex. Let $G=(V,E)$ be a directed graph. Then a hub should point to many authorities, and so we set the hub-score of a vertex to:

\begin{displaymath}
h_i = \sum_{(i,j) \in E} a_j.
\end{displaymath}
Likewise, an authority should be pointed to by many hubs:

\begin{displaymath}
a_i = \sum_{(j,i) \in E} h_j.
\end{displaymath}
Let $\mA$ be the adjacency matrix, then

\begin{displaymath}
\vh = \mA \va \text{ and } \va = \mA^T \vh.
\end{displaymath}
If we iterate these two, we find:

\begin{displaymath}
\vh = \mA \mA^T \vh \text{ and } \va = \mA^T \mA \va.
\end{displaymath}
In other words, we are looking for eigenvalues of the matrices $\mA \mA^T$ and $\mA^T \mA$, respectively. As we'{}ve stated these, the eigenvalue would have to be $1$. In the HITS algorithm, we keep iterating the updates:

\begin{displaymath}
\vh\itn{k+1} = \mA \va\itn{k} \text{ and } \va\itn{k+1} = \mA^T \vh\itn{k}
\end{displaymath}
and then \emph{normalizing} the results so that $\vh\itn{k+1}$ and $\va\itn{k+1}$ have unit 2-norm. What this does is run the \emph{power method} on the matrices $\mA \mA^T$ and $\mA^T \mA$, simultaneously. We can use the Perron-Frobenius theorem to help us understand when this will have a unique solution.

Recall that a matrix has a unique Perron vector (positive eigenvalue equal to its spectral radius) when it is irreducible and aperiodic.

\textbf{a)} Give an example that shows an irreducible graph where $\mA \mA^T$ or $\mA^T \mA$ is reducible.

\textbf{b)} Give an example that shows an irreducible, aperiodic graph where $\mA \mA^T$ or $\mA^T \mA$ is reducible.

\textbf{c)} What this means is that it may be easy for the HITS algorithm to get into trouble with respect a unique solution because the Perron vector of $\mA \mA^T$ or $\mA^T \mA$ may not be unique, even if it is for $\mA$. So let'{}s see what happens: Implement the HITS algorithm for graph.

\textbf{d)} Try at least four or five small graphs. Can you find a graph that is sensitive to the starting vector? If not, show that these graphs have a unique Perron vector by computing their eigenvalues.

\hypertarget{problem_3_5}{}\subsection*{{Problem 3}}\label{problem_3_5}

Read \url{http://www.ces.clemson.edu/~shierd/Shier/markov.pdf} about how to check if a graph is aperiodic.

\textbf{a)} Describe an $O(|E| d)$ algorithm to check if a graph is aperiodic where the only possible operation with the graph is a matrix-vector product: $\mA \vv$.

\textbf{b)} Describe how to use this algorithm to check whether or not $\mA^T \mA$ is irreducible.

\textbf{c)} Design an improved HITS algorithm that returns the hubs and authority vectors along with a flag that indicates whether or not the vectors are unique. Use as little extra work and memory as possible.

\textbf{b) Open question} Think about this question and write down your thoughts, or come chat with me about it. Is there a semi-ring operation that will check if a graph is aperiodic? Note that the operations greatest common divisor = $\otimes$ and least common multiple = $\oplus$ form a semi-ring over the non-negative intergers. At the very least, work out what the $0$ and $1$ elements are in this semi-ring. See \url{http://marcpouly.ch/pdf/internal_100712.pdf} for some other semirings that might be useful.

\hypertarget{problem_4_more_semirings_6}{}\subsection*{{Problem 4: More semi-rings}}\label{problem_4_more_semirings_6}

In this problem, we'{}ll show how a few things with semi-rings.

\textbf{a)} Show that $a \oplus b = \max(a,b)$ and $a \otimes b = \min(a,b)$ is a semi-ring and identify the $0$ and $1$ elements.

\textbf{b)} Show that a $n$-by-$n$ permutation matrix is an orthogonal matrix in any semi-ring.

\textbf{c) Open question} Is there a semi-ring to implement Boruvka'{}s algorithm for finding the minimum spanning tree? This would be a nice algorithm to implement in Hadoop or Pregel. Note that there is a semi-ring algorithm to compute minimum spanning trees using the semi-ring from part (a). This was described in MINIMUM-COST SPANNING TREE AS A PATH-FINDING PROBLEM by Maggs and Plotkin.

\hypertarget{problem_5_markov_chain_state_space_classification_7}{}\subsection*{{Problem 5: Markov chain state space classification}}\label{problem_5_markov_chain_state_space_classification_7}

In this problem, you'{}ll get some experience classifying the state of a Markov chain.

I'{}ll update this with the example soon, check back on Tuesday the 27th.

\hypertarget{problem_6_find_a_paper_8}{}\subsection*{{Problem 6: Find a paper}}\label{problem_6_find_a_paper_8}

Find a paper on networks and matrix computations that you'{}d like to present on for 30 minute in-class presentation. Please contact me with questions.


\end{document}
