\documentclass[twocolumn]{article}
% \documentclass{article}

\setlength{\oddsidemargin}{-0.5in}
\setlength{\evensidemargin}{-0.5in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{7.0in}
\setlength{\textheight}{9.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}
\setlength{\columnseprule}{0.3pt}

\setlength\columnsep{25pt}

\usepackage{fancyvrb}
\usepackage{relsize}
\usepackage{hyperref}

\usepackage{listings}
\usepackage{amsmath}

\begin{document}

\lstset{xleftmargin=5mm,framexleftmargin=10mm,basicstyle=\footnotesize}

Name: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

Directions: MAKE SURE TO COPY YOUR ANSWERS TO A SEPARATE SHEET FOR SENDING
ME AN ELECTRONIC COPY LATER.

{\bf 1.} (20) Fill in the blanks:  One can often get good speed with R
code by using vectorization.  The reason R is slow without using such
devices is that it is a(n) blank (a) language.  The basic programming
construct that is of particular concern in terms of slowness is blank
(b).  (Note: Examples of programming constructs are functions, loops,
if-else, arrays, strings etc., NOT types of programming, e.g.,
simulation.)

{\bf 2.} (10)  Consider Equation (2.60), p.21, numerator.  Which
``mailing tube'' justifies the fact that 0.4 multiplies something?  Cite
a specific equation number among mailing tubes.

{\bf 3.} (20)  Consider the ALOHA network model.  Say we have two such
networks, A and B.  In A, the network typically is used for keyboard
input, such as a user typing e-mail or editing a file.  But in B, users
tend to do a lot of file uploading, not just typing.  Fill in the
blanks:  In B, the model parameter blank (a) is blank (b) than in A, and
in order to accommodate this, we should set the parameter blank (c) to
be relatively blank (d) in B.

{\bf 4.} Consider the ALOHA network model with $n = 2$, $p = 0.4$ and $q
= 0.8$.  We are interested in $P(X_1 = 2 \textrm{ or } X_2 = 2)$.

\begin{itemize}

\item [(a)] (10) Find that probability.  (You should probably make use of
existing computations, to save time.)

\item [(b)] (10) Suppose we were to actually do the ``notebook''
process, shown in Table 2.3, p.14.  We observe the network for many
2-epoch stints, 10000 of them, yielding 10000 lines in our notebook.
And say we store our notebook data in an R data frame named {\bf
notebook}, with 10000 lines and 4 columns.  (Of course, the column
labeled ``notebook line'' is not stored.)  We enter 1s and 0s instead of
Yes's and No's.  State an R expression which would give us the
approximate value of $P(X_1 = 2 \textrm{ or } X_2 = 2)$.
 
\end{itemize}

{\bf 5.} (15) A famous graph model is {\it Preferential Attachment}.
Think of it as a social network, with each edge representing a
``friend'' relation.  (The graph is undirected, i.e.\ friendships are
mutual.) The number of vertices grows over time, one vertex per time
step.  At time 0, we have just two vertices, $v_1$ and $v_2$, with a
link between them.

In any graph, the {\it degree} of a vertex is its number of edges.  Thus
at time 0, each of the two vertices has degree 1.  Whenever a new vertex
is added to the graph, it randomly chooses an existing vertex to {\it
attach to}, creating a new edge with that existing vertex.  In making
that random choice, it follows probabilities in proportion to the
degrees of the existing edges.  

For instance (just an example!), suppose that at time 2, when $v_4$ is
added, the adjacency matrix for the graph is

$$
\left (
\begin{array}{rrr}
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 0 & 0 \\
\end{array}
\right )
$$

Then there will be an edge created between $v_4$ with $v_1$, $v_2$ or
$v_3$, with probability 2/4, 1/4 and 1/4, respectively.  

Find $P(v_4 \textrm{ attaches to } v_1)$.

{\bf 6.} (15) Consider the simulation of the bus ridership model, p.26.  Give
a single R statement that replaces lines 8-10, by calling {\bf
sample()}.

\onecolumn

\newpage

{\bf Solutions:}

{\bf 1.} interpreted; for loops

{\bf 2.} (2.5)

{\bf 3.} q; larger; p; low

{\bf 4a.} One way is to use (2.3).  From quantities already caculated in
the text, this is

$$
0.52 + 0.47 - 0.27 = 0.72
$$

{\bf 4b.}

\begin{lstlisting}
mean(notebook[,1] + notebook[,2] > 0)
\end{lstlisting}

{\bf 5.} Let $N_i$ denote the node that $v_i$ attaches to, i = 3,4,...
Then

\begin{eqnarray}
P(N_4 = 1)
&=& P(N_3 = 1 \textrm{ and } N_4 = 1) \
+ P(N_3 = 2 \textrm{ and } N_4 = 1) \\ 
&=& (1/2) (2/4) + (1/2) (1/4) \\
&=& 3/8
\end{eqnarray}

{\bf 6.}

\begin{lstlisting}
passengers <- passengers - sum(sample(0:1,passengers,replace=T,prob=c(0.8,0.2)))
\end{lstlisting}

\end{document}

