Add assignment text to the template

1 files changed, 88 insertions, 1 deletions

diff --git a/part1.tex b/part1.tex
index 45279ff..d5036bf 100644
--- a/part1.tex
+++ b/part1.tex
@@ -4,6 +4,7 @@
 \usepackage{amssymb}
 \usepackage{epic}
 \usepackage{graphicx}
+\usepackage{gensymb}
 %\pagestyle{empty}
 \newcommand{\tr}{\mbox{\sf true}}
 \newcommand{\fa}{\mbox{\sf false}}
@@ -16,8 +17,94 @@
 \begin{document}
 \maketitle
 
-\section*{Problem: Trucks}
+\section*{Problem: Packing pallets in trucks}
 
+Eight trucks have to deliver pallets of obscure building blocks to a magic factory. Every
+truck has a capacity of 8000 kg and can carry at most eight pallets. In total, the
+following has to be delivered:
+
+\begin{itemize}
+\item Four pallets of nuzzles, each of weight 700 kg.
+\item A number of pallets of prittles, each of weight 400 kg.
+\item Eight pallets of skipples, each of weight 1000 kg.
+\item Ten pallets of crottles, each of weight 2500 kg.
+\item Twenty pallets of dupples, each of weight 200 kg.
+\end{itemize}
+
+Skipples need to be cooled; only three of the eight trucks have facility for cooling
+skipples.
+
+Nuzzles are very valuable: to distribute the risk of loss no two pallets of nuzzles may
+be in the same truck.
+
+% (a) Investigate what is the maximum number of pallets of prittles that can be delivered,
+% and show how for that number all pallets may be divided over the eight trucks.
+
+% (b) Do the same, with the extra information that prittles and crottles are an explosive
+% combination: they are not allowed to be put in the same truck.
+
+\subsection*{Solution:}
+
+\section*{Problem: Chip design}
+Give a chip design containing two power components and ten regular components satisfying the following constraints:
+
+\begin{itemize}
+\item Both the width and the height of the chip is 30.
+\item The power components have width 4 and height 3.
+\item The sizes of the ten regular components are $4 \times 5$, $4 \times 6$,
+    $5 \times 20$, $6 \times 9$, $6 \times 10$, $6 \times 11$, $7 \times 8$,
+    $7 \times 12$, $10 \times 10$, $10 \times 20$, respectively.
+\item All components may be turned $90\degree$, but may not overlap.
+\item In order to get power, all regular components should directly be connected
+    to a power component, that is, an edge of the component should have at least
+    one point in common with an edge of the power component.
+\item Due to limits on heat production the power components should be not too close:
+their centres should differ at least 17 in either the x direction or the y direction
+(or both).
+\end{itemize}
+
+\subsection*{Solution:}
+
+\section*{Problem: Job scheduling}
+Twelve jobs numbered from 1 to 12 have to be executed satisfying the following requirements:
+\begin{itemize}
+\item The running time of job $i$ is $i + 5$, for $i = 1, 2, \ldots , 12$.
+\item All jobs run without interrupt.
+\item Job 3 may only start if jobs 1 and 2 have been finished.
+\item Job 5 may only start if jobs 3 and 4 have been finished.
+\item Job 7 may only start if jobs 3, 4 and 6 have been finished.
+\item Job 8 may not start earlier than job 5.
+\item Job 9 may only start if jobs 5 and 8 have been finished.
+\item Job 11 may only start if job 10 has been finished.
+\item Job 12 may only start if jobs 9 and 11 have been finished.
+\item Jobs 5, 7 en 10 require a special equipment of which only one copy is available, so
+no two of these jobs may run at the same time.
+\end{itemize}
+
+% (a) Find a solution of this scheduling problem for which the total running time is
+% minimal.
+
+% (b) Do the same with the extra requirement that job 6 and job 12 need a resource of
+% limited availability, by which job 6 may only run during the 17 time units in which
+% job 12 is running.
+
+\subsection*{Solution:}
+
+\section*{Problem: Integer sum from neighbors}
+Eight integer variables $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, $a_7$, $a_8$
+are given, for which the initial value of
+$a_i$ is $i$ for $i = 1$, \ldots, 8. The following steps are defined: choose $i$
+with $1 < i < 8$ and execute
+\[
+    a_i := a_{i-1} + a_i+1,
+\]
+that is, $a_i$ gets the sum of the values of its neighbors and all other values remain
+unchanged.
+
+% (a) Show how it is possible that $a_3 = a_7$ after a number of steps.
+
+% (b) Show how it is possible that $a_3 = a_5 = a_7$ after a number of steps.
+% For this problem both try to use an SMT solver and NuSMV, and discuss how they perform.
 
 \subsection*{Solution:}