Added final sol04.
authorEugen Sawin <sawine@me73.com>
Mon, 04 Jun 2012 05:00:02 +0200
changeset 18c4cbf19866b3
parent 17 60edc408c19e
child 19 9f72ba296485
Added final sol04.
exercises/solutions/sol04.pdf
exercises/solutions/sol04.tex
     1.1 Binary file exercises/solutions/sol04.pdf has changed
     2.1 --- a/exercises/solutions/sol04.tex	Sun Jun 03 20:13:56 2012 +0200
     2.2 +++ b/exercises/solutions/sol04.tex	Mon Jun 04 05:00:02 2012 +0200
     2.3 @@ -193,5 +193,5 @@
     2.4  
     2.5  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$.
     2.6  
     2.7 -The while loop needs some special treatment, due to limited time I have to skip this part for now.
     2.8 +The while loop needs some special treatment based on the observation that $|S[v_j,a_j]|+|Q|=e\cdot k$ and others. But, due to limited time, I have to skip this part this time.
     2.9  \end{document}