1.1 --- a/exercises/solutions/sol04.tex	Thu May 31 17:36:51 2012 +0200
     1.2 +++ b/exercises/solutions/sol04.tex	Fri Jun 01 00:00:25 2012 +0200
     1.3 @@ -21,13 +21,14 @@
     1.4  \newcommand{\R}{\mathcal{R}}
     1.5  \newcommand{\N}{\mathbb{N}}
     1.6  \newcommand{\C}{\mathcal{C}}
     1.7 +\newcommand{\bo}{\mathcal{O}}
     1.8  
     1.9  %\include{pythonlisting}
    1.10  
    1.11  \pagestyle{empty}
    1.12  \begin{document}
    1.13  \maketitle
    1.14 -
    1.15 +%
    1.16  \section*{Exercise 4.1}
    1.17  (a) The zebra problem is the constraint network $N=\langle V,D,C\rangle$ with
    1.18  \begin{align*}
    1.19 @@ -186,5 +187,11 @@
    1.20  
    1.21  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\\\\
    1.22  %
    1.23 -(c)
    1.24 +(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.
    1.25 +
    1.26 +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.
    1.27 +
    1.28 +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$.
    1.29 +
    1.30 +The while loop needs some special treatment, due to limited time I have to skip this part for now.
    1.31  \end{document}