\documentclass[12pt]{article}   

\newcommand{\arc}[2]{#1\!\longrightarrow\!#2}

\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 

\renewcommand{\reading}{Week 4 Notes.}

\begin{document}
\problemset{3}                  % !! Start the problem set with its number


\begin{problem}  %part(a) from F03, PS2

\begin{problemparts}


\problempart

List all the different binary relations on the set $\set{0,1}$.

\solution{There are altogether 16 binary relations.

\( \begin{array}{ll}
1. &  \emptyset\\
2. &  \{(0,0)\}\\
3. &  \{(0,1)\}\\
4. &  \{(1,0)\}\\
5. &  \{(1,1)\}\\
6. &  \{(0,0),(0,1)\}\\
7. &  \{(0,0),(1,0)\}\\
8. &  \{(0,0),(1,1)\}\\
9. &  \{(0,1),(1,0)\}\\
10. &  \{(0,1),(1,1)\}\\
11. &  \{(1,0),(1,1)\}\\
12. &  \{(0,0),(0,1),(1,0)\}\\
13. &  \{(0,0),(0,1),(1,1)\}\\
14. &  \{(0,0),(1,0),(1,1)\}\\
15. &  \{(0,1),(1,0),(1,1)\}\\
16. &  \{(0,0),(0,1),(1,0),(1,1)\}
\end{array} \)
}


\problempart Over the domain $\set{0,1}$, which of these relations are
weak partial orders? strict partial orders? equivalence relations?
%reflexive? symmetric? antisymmetric? transitive?

\solution{
We first list the relations that satisfy each of the following
properties: \\
\begin{itemize}
\item reflexive: $8, 13, 14, 16$\\
\item symmetric: $1, 2, 5, 8, 9, 12, 15, 16$\\
\item antisymmetric: $1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14$\\
\item transitive: $1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16$\\
\end{itemize}

From this we can see that the weak partial orders are  $\{8,13,14\}$,
the strict partial orders are $\{1,3,4\}$, and the equivalence relations are 
$\{8,16\}$.
}

\end{problemparts}

\end{problem}


% S02 PS3, S01 ps4
% source Problem Repository
% last used, Karger spring 00
% added some parts, RAD

\begin{problem} 
We partially order the power set, $\power(\set{1,2,\dots,n})$, by the
subset relation, $\subseteq$.

\bparts

\ppart Describe a maximum length chain in $\power(\set{1,2,\dots,n})$.
Briefly explain why there can't be a longer chain than the one you
described.
 
\solution{The length $n+1$ chain
\[
\emptyset, \set{1}, \set{1,2}, \set{1,2,3},\dots, \set{1,2,\dots,n}
\]
is a maximum length chain.  There can't be a longer one: any longer chain
would have to contain two subsets of the same size (think about why!), and
no finite set is contained in any other set of the same size.}
  
\ppart Describe a topological sort of $\power(\set{1,2,\dots,n})$,
with a brief justification that your sort is correct.

\solution{All sets of size $0$, followed by all sets of size $1$ (in any
order), followed by all sets of size $2$ (again, in any order), $\ldots$,
followed by all sets of size $n$.  See Figure~\ref{figure1} for the case
of $n=3$.  $\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\},
\{1,2,3\}$ is a topological sort of this relation.

\begin{figure}[ht]
\begin{center}
\unitlength=0.5pt
\input{figures/ps3-1.pic}
\end{center}
\caption{DAG for Problem 4(c) with $n=3$.}
\label{figure1}
\end{figure}
Note that not all chains and antichains are labelled.  A chain is any
group that is connected in some manner with arrows.  Antichains are groups
of elements where no two members are connected.}

\ppart Use Dilworth's Lemma to show that there must be an antichain of
size $\geq 2^n/(n+1)$.  Describe the biggest antichain that you can find.

\solution{Since a maximum length chain is of size at most $n+1$, and the
powerset has $2^n$ elements, Dilworth's Lemma tells us that there must be
an antichain of size at least $2^n/(n+1)$.

A maximum length antichain is the set of all subsets containing exactly
$\ceil{n/2}$ elements; the only other one is the set of all subsets
containing exactly $\floor{n/2}$ elements (of course these are the same if
$n$ is even).  A proof of this is actually tricky.  The size of this
antichain is about $2^n/\sqrt{2 \pi n}$.  We can't present proofs of
either of these facts yet, because they depend on concepts that won't be
introduced for another month.}

\eparts
\end{problem}

\iffalse

\begin{problem}
Remember that a partial function, $g$, is an injection iff
\[
g(a_1) = g(a_2) \qimplies a_1 = a_2
\]
for all $a_1,a_2$ in the domain of definition of $g$.

Prove that a relation, $R$, on a set, $A$, is a \emph{weak} partial order
providing there is an \emph{injection}, $g$, from $A$ to a collection of
sets such that
\begin{equation}\label{wk-eqn}
a_1\,R\, a_2 \qiff g(a_1) \subseteq g(a_2)
\end{equation}
for all $a_1, a_2 \in A$.

Also, give an example showing that this result would not hold if the
condition that $g$ is an injection was dropped.

(From Week 4 Notes, Problem 2(b-c).) %weak po iff \subseteq
\end{problem}
\fi


\begin{problem}
Consider the natural numbers partially ordered by divisibility.

\begin{problemparts}

\ppart Prove that this partial order has an infinite chain.

\solution{1 2 4 8 16 \dots is a chain with infinite length.}

\ppart Prove that this partial order has an infinite antichain.

\solution{The set of prime numbers is infinite.  Since no prime divides
another, any two primes are incomparable.  So the set of prime numbers is
an antichain.}

\ppart\label{fl} Now restrict the domain to the natural numbers $\le n$. 
Consider the chain
$1\preceq_R2\preceq_R4\preceq_R\ldots\preceq_R2^{\lfloor\log_2 n\rfloor}$.
Prove that it is maximal.

\solution{
%The sequence
%$1\preceq_R2\preceq_R4\preceq_R\ldots\preceq_R2^{\lfloor\log_2 n\rfloor}$
%is a chain with length $\lfloor\log_2 n\rfloor+1$.  
Suppose there is a
longer chain $a_0\preceq_R a_1\preceq_R a_2\preceq_R \ldots\preceq_R
a_m$. Since this chain is longer, $m\geq\lfloor\log_2 n\rfloor+1$. For
$i\in\{1, 2, 3, \ldots, m\}$, let $a_i=p_ia_{i-1}$, where $p_i$ is an
integer greater than 1. Then $a_m=p_1p_2\ldots p_ma_0$. Since each
$p_i\geq2$ and $a_0\geq1$, we have

\begin{eqnarray*}
a_m&=&p_1p_2\ldots p_ma_0\\
&\geq&2^{m}a_0\\
&\geq&2^{m}\\
&\geq&2^{\lfloor\log_2 n\rfloor+1}\\
&>&2^{\log_2 n}\\
&=&n,
\end{eqnarray*}

which is a contradiction since $a_m\leq n $ as $a_m\in A$.
}

\problempart 
Let $c$ be the length of the power of 2 chain.  By Dilworth's
Lemma there is an antichain of length $n/c$.  Describe one.
%Use Dilworth's Lemma and part~(\ref{fl}) to derive a lower
%bound on the largest anitchain. Construct an antichain which is as large
%as the lower bound.

% Conclude something about $\card{\set{\text{primes} \le n}}$?

\solution{
%Part (b) implies there is no chain with length
%$\geq\lfloor\log_2 n\rfloor+2$. Therefore, by Dilworth's Theorem, the size
%of the largest antichain is at least $\frac{n}{\lfloor\log_2
%n \rfloor+2}$. 
The set $\{\lfloor\frac{n}{2}\rfloor+1,
\lfloor\frac{n}{2}\rfloor+2,\ldots,n\}$ is an antichain with size
$\lceil\frac{n}{2}\rceil$, which is no less than the lower bound.}


\end{problemparts}

\end{problem}

\begin{problem}[30]
We consider DAG's where each vertex represents a task to be completed.  If
there is a path from one vertex, $v$, to another vertex, $w$, then the $v$
task must be completed before the $w$ task.  Assuming all tasks take unit
time to complete, we showed in the Notes that the minimum time schedule to
complete all the tasks is the size (number of vertices), $t$, of the
longest path (chain) in the DAG.

Formally, a \emph{schedule} for a DAG is a partition of the vertices.
Each block of the partition is supposed to correspond to a set of tasks
that are to be performed simultaneously.  The \emph{number of processors
required} by a schedule is the maximum number of tasks that are scheduled
to be performed simultaneously.
\bparts

\ppart Describe purely in terms of graph, partition, and partial order
properties (no informal descriptions in terms of ``jobs,'' ``parallel
processing,'' etc.):

\begin{itemize}
\item exactly the properties a vertex partition of a DAG must satisfy in
order to represent a possible schedule for the vertex tasks,
\item the total time required to complete a schedule,
\item the number of processors required by a schedule.

\end{itemize}

\solution{
\begin{itemize}

\item A schedule for a DAG, $G$, is a partition of the edges of $G$ into a
sequence of blocks, $B_1,B_2,\dots, B_k$ such that if $a \in B_i$, $b\in
B_j$, and $a < b$ (that is, there is a path of positive length from vertex
$a$ to vertex $b$), then $i < j$.  Another way to say this is that the
blocks are anti-chains, and the sequence consisting of the elements in
$B_1$ in any order, followed by the elements of $B_2$ in any order,
through the elements of $B_k$, is a topological sort of the partial order
defined by $G$.

\item The total time required to complete a schedule is the number, $k$,
of blocks it has.

\item The number of processors required by a schedule is the size of the
largest block.
\end{itemize}
}

\ppart Give a small example of a DAG with more than one minimum time
schedule.

\solution{
$V= \set{1,2,3}, E= \set{\arc{1}{2}}$.  There are two minimum time
schedules: $\set{\set{1,3}\set{2}}$ and $\set{\set{1}\set{2,3}}$.
}

\ppart Explain why any schedule that requires only $p$ processors to
complete $n$ tasks must take time at least $\ceil{n/p}$.

\solution{ If there are $k < \ceil{n/p}$, then the integer $k$ is less
than $n/p$.  So if there are $k$ blocks and each block has at most $p$
vertices, the total number of vertices is $\leq kp < (n/p)\cdot p = n$, a
contradiction.}

\ppart\label{timeD} Let $D_{n,t}$ be the DAG with $n$ vertices that
consists of a directed path of $t-1$ vertices ending with edges from the
final, $(t-1)$st, vertex on the path directly to each of the remaining
$n-(t-1)$ vertices, as in the following figure:

\mfigure{!}{2.5in}{pset3-hasse.pdf}

What is the minimum time schedule for $D_{n,t}$?  Explain why it is
unique.  How many processors does it require?

\solution{There's no choice but to schedule each of the $t-1$ vertices on
the path one at a time in order.  A minimum time schedule then does all
the remaining $n-(t-1)$ vertices at the $t$th time interval.  The number
of processors required is therefore $n-t+1$.  The time is $t$, the number
of vertices on the longest chain in the graph.}

\ppart Describe a minimum time $p$-processor schedule for $D_{n,t}$.
Write a simple formula for this minimum time, $M(n,t,p)$.

\solution{As in part~\eqref{timeD}, there's no choice but to schedule each
of the $t-1$ vertices on the path one at a time in order.  A minimum time
schedule then does all the remaining $n-(t-1)$ vertices $p$ at a time, for
a total time of
\begin{equation}\label{tnp}
M(n,t,p) \eqdef (t-1) + \ceil{\frac{n-(t-1)}{p}}.
\end{equation}}

\ppart Show that \emph{every} DAG with $n$ vertices and maximum chain
size, $t$, has a $p$-processor schedule that runs in time $M(n,t,p)$.

\textit{Hint:} Induction -- you decide on what variable.  You may find it
helpful to use the fact that if $a\geq b\geq 0$, then
\begin{equation}\label{cab}
\ceil{a-b} \leq 1 + \ceil{a} - \ceil{b}
\end{equation}
for all real numbers $a,b$.

\solution{
\begin{proof}
Induction on $t$.  Induction hypothesis:
\begin{quote}
$P(t) \eqdef \forall \text{ DAGs } G, \forall n,p \in \naturals^+$, if $G$
has $n$ vertices and maximum chain size $t$, then there is a $p$-processor
schedule for $G$ that takes time $M(n,t,p)$.
\end{quote}

\textbf{Base case $t=1$:} In this case there are $n$ vertices and no edges
between them.  So any partition of the vertices into $\ceil{n/p}$ blocks
of size at most $p$ will be a $p$-processor schedule taking time
$\ceil{n/p} = 0 + \ceil{(n-0)/p} = M(n,1,p)$.

\textbf{Inductive step:}
Assume $P(t)$ and conclude $P(t+1)$ where $t \geq 1$.

Let $G$ be any DAG with $n$ vertices and maximum chain size $t+1$.
Suppose $k$ vertices are endpoints of maximum-size chains in $G$.  Note
that no edge can leave any of these endpoint vertices, for otherwise there
would be a chain of length one more than the maximum chain size.  Let $H$
be the subgraph of $G$ obtained by removing these $k$ vertices.

Now $H$ is a DAG with $n-k$ vertices and maximum chain size $t$, so by
Induction Hypothesis, there is a $p$-processor schedule for $H$ taking
time $M(n-k,t,p)$.

This $p$-processor schedule for $H$ can be extended to one for $G$ by
adding $\ceil{k/p}$ disjoint blocks of the endpoints, all of size $\leq p$.
So the time for this schedule for $G$ is
\begin{align}
\lefteqn{M(n-k,t,p) + \ceil{\frac{k}{p}}}\notag\\
  & = (t-1) + \ceil{\frac{n-k-(t-1)}{p}} + \ceil{\frac{k}{p}} & \text{(def of $M$)}\notag\\
  & = (t-1) + \ceil{\frac{n-t}{p} - \frac{k-1}{p}} + \ceil{\frac{k}{p}}
\label{t1}
\end{align}

We complete the proof by showing that the expression~\eqref{t1} is $\leq
M(n, t+1, p)$.  To do this, we consider two cases:

\begin{itemize}

\item \textbf{Case 1} ($k-1$ is not a multiple of $p$):
We have
\begin{equation}\label{k1}
\ceil{\frac{k-1}{p}} = \ceil{\frac{k}{p}},
\end{equation}
so
\begin{align*}
\text{\eqref{t1}}
   & \leq (t-1) + \left(1+ \ceil{\frac{n-t}{p}} -
   \ceil{\frac{k-1}{p}}\right) + \ceil{\frac{k}{p}} & \text{(by~\eqref{cab})}\\
   & = (t-1) + \left(1+ \ceil{\frac{n-t}{p}} -
      \ceil{\frac{k}{p}}\right) + \ceil{\frac{k}{p}} & \text{(by~\eqref{k1})}\\
   & = t + \ceil{\frac{n-t}{p}}\\
   & = M(n, t+1, p). & \text{(def of $M$)}
\end{align*}

\item \textbf{Case 2} ($k-1$ is a multiple of $p$): 
Now we have
\begin{equation}
\ceil{\frac{k}{p}}=1+\frac{k-1}{p},\label{k+}
\end{equation}
so
\begin{align*}
\text{\eqref{t1}}
  & = (t-1) + \left(\ceil{\frac{n-t}{p}} - \frac{k-1}{p}\right) +
       \ceil{\frac{k}{p}} & \text{(since $(k-1)/p \in \integers$)}\\
  & = (t-1) + \ceil{\frac{n-t}{p}} - \frac{k-1}{p} +
  \left(1+\frac{k-1}{p}\right) & \text{(by~\eqref{k+})}\\
   & = t + \ceil{\frac{n-t}{p}}\\
   & = M(n, t+1, p). & \text{(def of $M$)}
\end{align*}

\end{itemize}

\end{proof}
}
\eparts

\end{problem}
\end{document}












