Added first version of sol05.
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/exercises/solutions/sol05.tex Sat Jun 09 23:45:57 2012 +0200
1.3 @@ -0,0 +1,85 @@
1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
1.5 +\usepackage{graphicx}
1.6 +%\usepackage[latin1]{inputenc}
1.7 +\usepackage{amsmath, amsthm, amssymb}
1.8 +\usepackage{typearea}
1.9 +\usepackage{algorithm}
1.10 +\usepackage{algorithmic}
1.11 +\usepackage{fullpage}
1.12 +\usepackage{mathtools}
1.13 +\usepackage[all]{xy}
1.14 +\usepackage{tikz}
1.15 +\usepackage{tikz-qtree}
1.16 +\usetikzlibrary{decorations.pathmorphing} % noisy shapes
1.17 +\usetikzlibrary{fit} % fitting shapes to coordinates
1.18 +\usetikzlibrary{backgrounds} % drawin
1.19 +\usetikzlibrary{shapes,snakes}
1.20 +\addtolength{\voffset}{-20pt}
1.21 +\title{CSP Exercise 05 Solution}
1.22 +\author{Eugen Sawin}
1.23 +\renewcommand{\familydefault}{\sfdefault}
1.24 +\newcommand{\R}{\mathcal{R}}
1.25 +\newcommand{\N}{\mathbb{N}}
1.26 +\newcommand{\C}{\mathcal{C}}
1.27 +\newcommand{\bo}{\mathcal{O}}
1.28 +
1.29 +%\include{pythonlisting}
1.30 +
1.31 +\pagestyle{empty}
1.32 +\begin{document}
1.33 +\maketitle
1.34 +%
1.35 +\section*{Exercise 5.1}
1.36 +(a) The following table shows the states during the iterations.\\\\
1.37 +\begin{tabular}{r l l l}
1.38 +Iteration & Queue & Revise & Domains\\\hline
1.39 + $0$ & $\{(v_1,v_2),(v_2,v_1),
1.40 + (v_2,v_3),(v_3,v_2),
1.41 + (v_1,v_3),(v_3,v_1)\}$
1.42 + & $$
1.43 + & $(\{1,2,3,4,5\},
1.44 + \{1,2,3,4,5\},
1.45 + \{1,2,3,4,5\})$\\
1.46 + $1$ & $\{(v_1,v_2),(v_2,v_1),
1.47 + (v_2,v_3),(v_3,v_2),
1.48 + (v_1,v_3)\}$
1.49 + & $(v_3,v_1)$
1.50 + & $(\{1,2,3,4,5\},
1.51 + \{1,2,3,4,5\},
1.52 + \{1,2,3,4,5\})$\\
1.53 + $2$ & $\{(v_1,v_2),(v_2,v_1),
1.54 + (v_2,v_3),(v_3,v_2)
1.55 + \}$
1.56 + & $(v_1,v_3)$
1.57 + & $(\{1,2,3,4,5\},
1.58 + \{1,2,3,4,5\},
1.59 + \{1,2,3,4,5\})$\\
1.60 + $3$ & $\{(v_1,v_2),(v_2,v_1),
1.61 + (v_2,v_3)\}\cup\{(v_1,v_3)\}$
1.62 + & $(v_3,v_2)$
1.63 + & $(\{1,2,3,4,5\},
1.64 + \{1,2,3,4,5\},
1.65 + \{1,2\})$\\
1.66 + $4$ & $\{(v_1,v_2),(v_2,v_1),
1.67 + (v_2,v_3)\}\cup\{\}$
1.68 + & $(v_1,v_3)$
1.69 + & $(\{1,2\},
1.70 + \{1,2,3,4,5\},
1.71 + \{1,2\})$\\
1.72 + $5$ & $\{(v_1,v_2),(v_2,v_1)\}$
1.73 + & $(v_2,v_3)$
1.74 + & $(\{1,2\},
1.75 + \{1,2\},
1.76 + \{1,2\})$\\
1.77 + $6$ & $\{(v_1,v_2)\}$
1.78 + & $(v_2,v_1)$
1.79 + & $(\{1,2\},
1.80 + \{1,2\},
1.81 + \{1,2\})$\\
1.82 + $7$ & $\{\}$
1.83 + & $(v_1,v_2)$
1.84 + & $(\{1,2\},
1.85 + \{1,2\},
1.86 + \{1,2\})$\\
1.87 +\end{tabular}
1.88 +\end{document}