diff -r f94c11c455e8 -r 359c996c91a2 exercises/solutions/sol04.tex
--- a/exercises/solutions/sol04.tex	Thu May 31 17:36:51 2012 +0200
+++ b/exercises/solutions/sol04.tex	Fri Jun 01 00:00:25 2012 +0200
@@ -21,13 +21,14 @@
 \newcommand{\R}{\mathcal{R}}
 \newcommand{\N}{\mathbb{N}}
 \newcommand{\C}{\mathcal{C}}
+\newcommand{\bo}{\mathcal{O}}
 
 %\include{pythonlisting}
 
 \pagestyle{empty}
 \begin{document}
 \maketitle
-
+%
 \section*{Exercise 4.1}
 (a) The zebra problem is the constraint network $N=\langle V,D,C\rangle$ with
 \begin{align*}
@@ -186,5 +187,11 @@
 
 We have shown, that all initial not arc-consistent constraints are made arc-consistent and the same holds for all newly introduced inconsistencies by the domain reduction. It follows that all remaining domains of $\C'$ form an arc-consistent network. \qed\\\\
 %
-(c)
+(c) All trivial assignments with complexity of $\bo(1)$ are left out of this analysis. Further it is assumed that set containment can be tested in $\bo(1)$, while is is only true for fully expanded sets with exponential space requirements. We can, however, archieve $\bo(1)^*$ using hash tables and amortized analysis in linear space. The natural tree-based approach yields $\bo(\log n)$. For the queue, we assume a stack is used with $\bo(1)$ insertion and removal (last inserted value). Let $n$ be the number of variables, all domains have size $\leq k$ and $e$ is the number of constraints.
+
+The initialisation of the counters consists of an iteration over all constraints $R_{ij}$ and values $a_i\in D_i$, $a_j\in D_j$, this takes $\Theta(e\cdot k^2)$ time.
+
+Next we initialise the set $S[v_j,a_j]$ with the supported tuples, adjust the counters and move unsupported tuples into $Q$ for each constraint $R_{ij}$ and values $a_i\in D_i$, $a_j\in D_j$, again this takes $\Theta(e\cdot k^2)$ time. We notice that each set $S[v_j,a_j]$ and $Q$ have at most $e\cdot k$ elements, also the counter value for any variable-value pair is $\leq e\cdot k$.
+
+The while loop needs some special treatment, due to limited time I have to skip this part for now.
 \end{document}