Tex source for a homework assignment with code and math

gistfile1.txt

\documentclass[a4paper,english]{article}

%% Use utf-8 encoding for foreign characters
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{babel}
\usepackage{graphicx}
\usepackage{siunitx}

%% Vector based fonts instead of bitmaps
\usepackage{lmodern}

%% Useful
\usepackage{fullpage} % Smaller margins
\usepackage{enumerate}

%% Theorem
\usepackage{amsthm}

%% More math
\usepackage{amsmath}
\usepackage{amssymb}

%% Commands
\newcommand{\sups}[1]{\ensuremath{^{\textrm{#1}}}}
\newcommand{\subs}[1]{\ensuremath{_{\textrm{#1}}}}

\usepackage{float}
\usepackage{algpseudocode}

%% Document Header
\title{COMP 251 Homework 6}
\author{Matthew Wetmore \\ 260405087}
\date{November 29, 2012}

\begin{document}

\maketitle

\begin{enumerate}

% Number 1
\item{

\begin{enumerate}[1]

% Part 1
\item{
Consider 3 matrices: $A : 5 \times 2, B : 2 \times 3, C : 3 \times 10$. The matrix product of an $a \times b$ matrix and a $b \times c$ matrix requires $a \cdot b \cdot c$ scalar multiplications. So computing $AB$ takes $30$ operations, hence $(AB)C$ takes $30 + 150 = 180$ multiplications. By similar reasoning, $A(BC)$ takes $60 + 100 = 160$ multiplications. Clearly choosing the right order of matrix multiplications changes the amount of computation required.
}

%Part 2
\item{
Since matrix multiplication is a binary operation, the general idea behind optimizing a sequence of multiplications is to subdivide the sequence into two sequences, trying every possible division and finding the one with the lowest cost. Using recursion on each interval, we can solve the problem. Obviously this is brute force, but we can apply dynamic programming (specifically memoization) to speed it up. The algorithm follows:


\begin{algorithmic}
\State matrix $C$ = $k \times k$ matrix to hold cost of multiplying matrices $M_i$ to $M_j$
\State matrix $I$ is a $k \times k$ matrix to hold the indexes of parens
\State set all diagonal entries of $C$ to 0
\For {$l$ from 2 to $k$}

\For {$i$ from 1 to $k-l$}

\State $j$ = $i + l - 1$
\State $C[i, k] = \infty$

\For {$x$ from $i$ to $j - 1$}

\State cost = $C[i, x] + C[x+1, j] + n_i \times n_{x+1} \times n_{j+1}$
\If {cost < $C[i, j]$}
\State $C[i, j] = q$
\State $I[i, j] = x$

\EndIf


\EndFor

\EndFor

\EndFor
\end{algorithmic}

In order to recover the positions of the parentheses, we just use the matrix $I$.
}

\end{enumerate}
}

% Number 2
\item{
This problem is solved pretty easily by applying network flow to maximal matching. There are $n$ switches and $n$ lights, and we create a set of nodes for each. Now we create edges between these nodes: there is an edge $(u,v)$ from light switch $u$ to light $v$ if the line segment connecting them doesn't intersect any walls. Each edge has capacity 1. Now we create two nodes, $s$ and $t$. There is an edge from $s$ to all switch nodes, and an edge from every light node to $t$. All of these edges also have capacity 1. Finally, we run the max flow algorithm to find the maximum flow through our network. If this flow is equal to $n$, there is a possible ergonomic floorplan. If max flow is less than $n$, there is not an ergonomic floorplan.

The algorithm takes $\Theta(n^2)$ to make edges between lights and switches, and $n^2 \log n$ ($n^4 \log n$ for a dense graph) with the modified FF discussed in class, as max flow is $n$ and there are, worst case, $n^2$ edges between the switch nodes and the light nodes. The runtime of the FF algorithm "absorbs" the time to set up the graph. The time is polynomial as needed.

The reason we can set up the graph like this is because we want to count the amount of ergonomically-connected lights and switches - unless we connect all $n$ lights to a switch, we've failed and return false. So each switch can send out only one "unit", and the light it sends its single unit to is the one it is wired to. Since the flow out of the station nodes is maximum $1$ (because of the outbound edge capacity), only one switch can connect to a light. Thus our formulation solves the problem as posed.
}

% Number 3
\item{
One (extremely) simple protocol consists of a number or rounds. Each round, every processor "flips the coin," obtaining a value of either 1 or 0. Afterwards, if there is a processor with a unique value (for example, if two processors have a 1, and one has a 0, the processor with a 0 has a unique value) that processor is the leader. If not, another round commences. This continues until a leader is chosen.

An analysis for 3 processors follows. At each round, there are 8 possible outcomes, 2 of which have no unique values. The remaining 6 outcomes all have a unique value, and therefore a leader is chosen. Each outcome has probability $(0.5)^3$, so all 8 possibilities have a total probability of 1, as required. How many rounds do we expect there to be before a leader is chosen? At each round there is a possibility of success $\alpha$ and failure $1 - \alpha$. If $N$ is a random variable that counts the number of steps until success, we have:

$$ \mathbb{E}[N] = \alpha + \alpha(1-\alpha) \cdot 2 + \alpha(1-\alpha)^2 \cdot 3 + \ldots = \alpha \sum_{n=1}^{\infty} n(1-\alpha)^{n-1} $$

If we define $x := (1-\alpha)$ then this is equal to:

$$ \alpha \frac{d}{dx}\sum_{n=0}^{\infty} x^n =  \alpha \frac{d}{dx}\left(\frac{1}{1-x}\right) = \alpha \frac{1}{(x-1)^2} = \alpha \frac{1}{\alpha^2} = \frac{1}{\alpha} $$

In our case, $\alpha = 6 \cdot (0.5)^3$ so the expected value for $N$ is $8/6 = 4/3$.

By similar reasoning, for $n$ processes $\alpha = 2n\cdot(0.5)^{n}$ thus expected value is $2^n/2n$.
}

% Number 4
\item{
The algorithm for producing $X'$, a sorted set of the integer set $X$ using convex hull is as follows - create a set of points $S := \{(x, y) : y = x^2, x \in X\}$. Run the convex hull algorithm, producing a stack of points creating the convex hull. The stack will be in the proper order to draw the convex hull. To recover $X'$, simply take the $x$ coordinate of each point in the stack, in the order the stack is in.

To give some rationale for this method we give the following facts. First of all, the stack will contain every point in $S$. The points $(x, y)$ are plotted according to a proper function, therefore they pass the vertical line test. Therefore there will be no non-left turns between points, so the convex hull algorithm will not pop any point out of the stack containing the hull. Alternatively, $x^2$ is a convex function, so it makes sense the convex hull contains all points. Therefore $X'$ will contain every element of $X$.  

Now the rationale for the actual sorting. The convex hull algorithm starts by choosing the leftmost point $p_0$ with the lowest y-value. By our construction of $S$, this will be the point with the lowest $x$, corresponding to the smallest element of $X$. This point is the first in the convex hull stack, and therefore the first in $X'$. So the first point is correct. As the convex hull algorithm works with the points sorted by polar angle with $p_0$, and $x^2$ is a strictly increasing function, the convex hull will contain points in order of $x$. So the set $X'$ will contain the points sorted by $x$ value.

Finally, this algorithm assumes nonnegative integers in the set (the professor confirmed this is an acceptable assumption), but it can be extended to negative numbers by shifting all numbers over to positive by some constant.
}

\end{enumerate}

\end{document}