HW8.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Programming/Coding Assignment
% LaTeX Template
%
% This template has been downloaded from:
% http://www.latextemplates.com
%
% Original author:
% Ted Pavlic (http://www.tedpavlic.com)
%
% Note:
% The \lipsum[#] commands throughout this template generate dummy text
% to fill the template out. These commands should all be removed when
% writing assignment content.
%
% This template uses a Perl script as an example snippet of code, most other
% languages are also usable. Configure them in the "CODE INCLUSION
% CONFIGURATION" section.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass{article}

%\usepackage{lmodern}
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage{fancyhdr} % Required for custom headers
\usepackage{lastpage} % Required to determine the last page for the footer
\usepackage{extramarks} % Required for headers and footers
\usepackage[usenames,dvipsnames]{color} % Required for custom colors
\usepackage{graphicx} % Required to insert images
\usepackage{listings} % Required for insertion of code
\usepackage{courier} % Required for the courier font
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage{pdfpages}
\usepackage{color}
\usepackage{float}
\usepackage{tabularx}
\PassOptionsToPackage{hyphens}{url}\usepackage{hyperref}
\usepackage{subfig}
\usepackage{scalefnt}
\restylefloat{table}

% Margins
\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1} % Line spacing

% Set up the header and footer
\pagestyle{fancy}
\lhead{\hmwkAuthorName} % Top left header
\chead{\hmwkClass: \hmwkTitle} % Top center head
\rhead{\firstxmark} % Top right header
\lfoot{\lastxmark} % Bottom left footer
\cfoot{} % Bottom center footer
\rfoot{Page\ \thepage\ of\ \protect\pageref{LastPage}} % Bottom right footer
\renewcommand\headrulewidth{0.4pt} % Size of the header rule
\renewcommand\footrulewidth{0.4pt} % Size of the footer rule

\setlength\parindent{0pt} % Removes all indentation from paragraphs

%----------------------------------------------------------------------------------------
%	CODE INCLUSION CONFIGURATION
%----------------------------------------------------------------------------------------

\definecolor{MyDarkGreen}{rgb}{0.0,0.4,0.0} % This is the color used for comments
\lstloadlanguages{Perl} % Load Perl syntax for listings, for a list of other languages supported see: ftp://ftp.tex.ac.uk/tex-archive/macros/latex/contrib/listings/listings.pdf
\lstset{language=Python, % Use Perl in this example
        frame=single, % Single frame around code
        basicstyle=\small\ttfamily, % Use small true type font
        keywordstyle=[1]\color{Blue}\bf, % Perl functions bold and blue
        keywordstyle=[2]\color{Purple}, % Perl function arguments purple
        keywordstyle=[3]\color{Blue}\underbar, % Custom functions underlined and blue
        identifierstyle=, % Nothing special about identifiers
        commentstyle=\usefont{T1}{pcr}{m}{sl}\color{MyDarkGreen}\small, % Comments small dark green courier font
        stringstyle=\color{Purple}, % Strings are purple
        showstringspaces=false, % Don't put marks in string spaces
        tabsize=5, % 5 spaces per tab
        %
        % Put standard Perl functions not included in the default language here
        morekeywords={rand},
        %
        % Put Perl function parameters here
        morekeywords=[2]{on, off, interp},
        %
        % Put user defined functions here
        morekeywords=[3]{test},
       	%
        morecomment=[l][\color{Blue}]{...}, % Line continuation (...) like blue comment
        numbers=left, % Line numbers on left
        firstnumber=1, % Line numbers start with line 1
        numberstyle=\tiny\color{Blue}, % Line numbers are blue and small
        stepnumber=5 % Line numbers go in steps of 5
}

% Creates a new command to include a perl script, the first parameter is the filename of the script (without .pl), the second parameter is the caption
\newcommand{\pythonscript}[2]{
\begin{itemize}
\item[]\lstinputlisting[caption=#2,label=#1]{#1.py}
\end{itemize}
}

%----------------------------------------------------------------------------------------
%	DOCUMENT STRUCTURE COMMANDS
%	Skip this unless you know what you're doing
%----------------------------------------------------------------------------------------

% Header and footer for when a page split occurs within a problem environment
\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak
}

% Header and footer for when a page split occurs between problem environments
\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak
\nobreak\extramarks{#1}{}\nobreak
}

\setcounter{secnumdepth}{0} % Removes default section numbers
\newcounter{homeworkProblemCounter} % Creates a counter to keep track of the number of problems

\newcommand{\homeworkProblemName}{}
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]{ % Makes a new environment called homeworkProblem which takes 1 argument (custom name) but the default is "Problem #"
\stepcounter{homeworkProblemCounter} % Increase counter for number of problems
\renewcommand{\homeworkProblemName}{#1} % Assign \homeworkProblemName the name of the problem
\section{\homeworkProblemName} % Make a section in the document with the custom problem count
\enterProblemHeader{\homeworkProblemName} % Header and footer within the environment
}{
\exitProblemHeader{\homeworkProblemName} % Header and footer after the environment
}

\newcommand{\problemAnswer}[1]{ % Defines the problem answer command with the content as the only argument
\noindent\framebox[\columnwidth][c]{\begin{minipage}{0.98\columnwidth}#1\end{minipage}} % Makes the box around the problem answer and puts the content inside
}

\newcommand{\homeworkSectionName}{}
\newenvironment{homeworkSection}[1]{ % New environment for sections within homework problems, takes 1 argument - the name of the section
\renewcommand{\homeworkSectionName}{#1} % Assign \homeworkSectionName to the name of the section from the environment argument
\subsection{\homeworkSectionName} % Make a subsection with the custom name of the subsection
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]} % Header and footer within the environment
}{
\enterProblemHeader{\homeworkProblemName} % Header and footer after the environment
}

%----------------------------------------------------------------------------------------
%	NAME AND CLASS SECTION
%----------------------------------------------------------------------------------------

\newcommand{\hmwkTitle}{Homework\ 8} % Assignment title
\newcommand{\hmwkDueDate}{Thursday,\ October 30,\ 2014} % Due date
\newcommand{\hmwkClass}{Advanced Algorithmics} % Course/class
\newcommand{\hmwkClassTime}{} % Class/lecture time
\newcommand{\hmwkClassInstructor}{} % Teacher/lecturer
\newcommand{\hmwkAuthorName}{Martin Valgur} % Your name

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \hmwkClassTime}}
\vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{\today} % Insert date here if you want it to appear below your name

%----------------------------------------------------------------------------------------

\begin{document}

%\maketitle=
%\thispagestyle{empty}

%----------------------------------------------------------------------------------------
%	TABLE OF CONTENTS
%----------------------------------------------------------------------------------------

%\setcounter{tocdepth}{1} % Uncomment this line if you don't want subsections listed in the ToC

\newpage
%\tableofcontents
%\newpage

%----------------------------------------------------------------------------------------
%	PROBLEM 1
%----------------------------------------------------------------------------------------

% To have just one problem per page, simply put a \clearpage after each problem

\begin{homeworkProblem}
\textit{Use the same graph as from last week. Make the SCC component graph, and provide it's topological sort order.}\\

Sage worksheet with the source code of this solution: \url{https://cloud.sagemath.com/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/files/HW8/Task\%201.sagews}.

\begin{figure}[H]
\label{fig:scc}
  \centering
    \includegraphics[width=1\textwidth]{T1_SCCs.pdf}
  \caption{The graph with its vertices colored by the SCC they belong to.}
\end{figure}
\begin{figure}[H]
\label{fig:scc_topo}
  \centering
    \includegraphics[width=0.6\textwidth]{T1_toposort.pdf}
  \caption{Topological ordering of the SCCs.}
\end{figure}


\end{homeworkProblem}

\clearpage

\begin{homeworkProblem}
\textit{Take the same graph as from task 1 (last week). Represent it in Adjacency Matrix presentation. Calculate the versions with exactly 2 hops and 3 hops. $G*G$ and $G*G*G$ respectively. Draw the "3-hop graph". Calculate the transitive closure by 1) $G*G*G*\cdots*G$ ; 2) Power steps: $G_2=G*G$ ; $G_4=G_2*G_2$ ; $G_8=G_4*G_4$ ; $G_{16}=G_8*G_8$, and 3) Warshall algorithm.}\\

Sage worksheet containing the source code of this solution: \url{https://cloud.sagemath.com/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/files/HW8/Task\%202.sagews}.

%\noindent\null\hfill\includegraphics[width=0.4\textwidth]{T2_G.pdf} \hfill
%$$\input{T2_G.tex}$$ \hfill\null

\begin{figure}[H]
\hfill
\vcenter{\subfloat{
$\input{T2_G.tex}$
}}
\hspace*{-3in}
\vcenter{\subfloat{\includegraphics[width=0.4\textwidth]{T2_G.pdf} }}
\hfill
\caption{Adjacency matrix $G$.}
\end{figure}

\begin{figure}[H]
\hfill
\vcenter{\subfloat{
$\input{T2_G2.tex}$
}}
\hspace*{-3in}
\vcenter{\subfloat{\includegraphics[width=0.4\textwidth]{T2_G2.pdf} }}
\hfill
\caption{Adjacency matrix $G*G$.}
\end{figure}

\begin{figure}[H]
\hfill
\vcenter{\subfloat{
$\input{T2_G3.tex}$
}}
\hspace*{-3in}
\vcenter{\subfloat{\includegraphics[width=0.4\textwidth]{T2_G3.pdf} }}
\hfill
\caption{Adjacency matrix $G*G*G$.}
\end{figure}

\begin{figure}[H]
\hfill
\vcenter{\subfloat{
$\input{T2_tc.tex}$
}}
\hspace*{-3in}
\vcenter{\subfloat{\includegraphics[width=0.4\textwidth]{T2_tc.pdf} }}
\hfill
\caption{Transitive closure (calculated with either $((G+I)^N-I)$ or the Warshall algorithm).}
\end{figure}

\end{homeworkProblem}

\begin{homeworkProblem}
\textit{Take the same graph and run the simple random walk procedure along the graph. Treat all outbound links with equal probability. Report the proportion of time spent in each node. Add some edges to get rid of dead ends (to node C, for example K-C, I-C, G-C). And some edges to get into nodes that had no incoming links (D-J, D-L). Interpret the effect of those added links.}\\

See the Sage worksheet for this task: \url{https://cloud.sagemath.com/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/files/HW8/Task\%203.sagews}.\\


The addition of edges to dead-end nodes got rid of all absorbing states. As a result the random walk can continue indefinitely and the probability of finishing the walk on a specific node does not depend on the starting node anymore.

\end{homeworkProblem}

\begin{homeworkProblem}
\textit{Explore the real graphs from here: \url{https://courses.cs.ut.ee/2013/algorithmics/spring/Main/HW8}. Select two graphs by your own choice. Describe the graphs - what they are about? Analyse the degree distribution; find how many components.}\\

See the Sage worksheet for this task: \url{https://cloud.sagemath.com/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/files/HW8/Task\%204.sagews}.\\

\begin{itemize}
\item Enron -- directed graph of emails sent from person to person in the Enron company.
\item Students -- undirected graph of collaboration between students during a course, edges have different types to mark different types of collaboration.
\item US airlines -- directed graph of the number of flights between US airports. Surprisingly has many SCCs. The degree distribution obeys inverse power law.
\item Karate -- a small undirected graph of relationships between people who belong to either or both of two clubs.
\end{itemize}

\end{homeworkProblem}

\begin{homeworkProblem}
\textit{What is the diameter of your graphs (components) from 2? (you can estimate it also by running shortest distance not from all nodes, if computationally too slow. How slow?).}\\

See the Sage worksheet for this task (same as in task 4): \url{https://cloud.sagemath.com/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/files/HW8/Task\%204.sagews}.\\

\end{homeworkProblem}

\begin{homeworkProblem}
\textit{Continue task nr 3. Represent it as a adjacency matrix with real-valued probabilities. Compare whether the matrix multiplication yields similar stationary distributions. Both on original and modified graph (with no dead ends or unreachable nodes). }\\

See the Sage worksheet for task 3: \url{https://cloud.sagemath.com/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/files/HW8/Task\%203.sagews}.\\

\end{homeworkProblem}


%----------------------------------------------------------------------------------------

\end{document}