# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1337373464 -7200
# Node ID b5c5ecd64f6a26cdadb48565fbb32ab71103bbc7
# Parent  07d59c14c71250400a48c314bfccae6f1ece5676
Added first part of ex3.

diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/pgfsubpic.sty
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/pgfsubpic.sty	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,4 @@
+\RequirePackage{pgf}
+
+\input{pgfsubpic.tex}
+\endinput
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/pgfsubpic.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/pgfsubpic.tex	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,209 @@
+%    pgfsubpic.tex
+%    Version 1.1, 25 Dec 2009
+
+%    Copyright 2009 by David Chiang
+
+%    This program is free software; you can redistribute it and/or modify
+%    it under the terms of the GNU General Public License as published by
+%    the Free Software Foundation; either version 2 of the License, or
+%    (at your option) any later version.
+
+%    This program is distributed in the hope that it will be useful,
+%    but WITHOUT ANY WARRANTY; without even the implied warranty of
+%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+%    GNU General Public License for more details.
+
+%    You should have received a copy of the GNU General Public License along
+%    with this program; if not, write to the Free Software Foundation, Inc.,
+%    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+% New in version 1.1:
+% - the ability to save a subpicture in local variables
+% - nodes in subpictures are tracked if the subpicture is placed with arbitrary transforms
+% - new \pgffitsubpicture macro to transform a subpicture (preserving aspect) to fit in a desired box
+
+\newdimen\pgf@subpicminx
+\newdimen\pgf@subpicminy
+\newdimen\pgf@subpicmaxx
+\newdimen\pgf@subpicmaxy
+
+% Special virtual node for current subpicture's bounding box
+\expandafter\def\csname pgf@sh@ns@current subpicture\endcsname{rectangle}
+\expandafter\def\csname pgf@sh@np@current subpicture\endcsname{%
+  \def\southwest{\pgfqpoint{\pgf@subpicminx}{\pgf@subpicminy}}%
+  \def\northeast{\pgfqpoint{\pgf@subpicmaxx}{\pgf@subpicmaxy}}%
+}
+\expandafter\def\csname pgf@sh@nt@current subpicture\endcsname{{\pgf@pt@aa}{\pgf@pt@ab}{\pgf@pt@ba}{\pgf@pt@bb}{\the\pgf@pt@x}{\the\pgf@pt@y}} % the transformation at invocation time
+\expandafter\def\csname pgf@sh@pi@current subpicture\endcsname{\pgfpictureid}
+
+% Create a pgfpicture inside an hbox for delayed placement
+\def\pgfsubpicture{%
+\expandafter\global\expandafter\setbox\pgf@hbox=\hbox\bgroup
+\pgfinterruptpicture
+\pgfpicture
+\relax % not sure why. otherwise a curly brace immediately after causes an error
+}
+
+\def\endpgfsubpicture{
+\global\pgf@subpicminx=\pgf@picminx
+\global\pgf@subpicminy=\pgf@picminy
+\global\pgf@subpicmaxx=\pgf@picmaxx
+\global\pgf@subpicmaxy=\pgf@picmaxy
+\global\edef\subpictureid{\pgfpictureid}%
+\pgfsetbaseline{\pgf@picminy}%
+\endpgfpicture%
+\endpgfinterruptpicture%
+\egroup
+}
+
+% Allocate registers for saving a subpicture. #1 is text, not a control sequence.
+\def\pgfnewsubpicture#1{%
+\expandafter\newbox\csname pgf@subpic@hbox@#1\endcsname
+\expandafter\newdimen\csname pgf@subpic@minx@#1\endcsname
+\expandafter\newdimen\csname pgf@subpic@miny@#1\endcsname
+\expandafter\newdimen\csname pgf@subpic@maxx@#1\endcsname
+\expandafter\newdimen\csname pgf@subpic@maxy@#1\endcsname
+}
+
+% saved subpictures are local to the current group
+\def\pgfsavesubpicture#1{%
+\expandafter\setbox\csname pgf@subpic@hbox@#1\endcsname\box\pgf@hbox
+\csname pgf@subpic@minx@#1\endcsname\pgf@subpicminx
+\csname pgf@subpic@miny@#1\endcsname\pgf@subpicminy
+\csname pgf@subpic@maxx@#1\endcsname\pgf@subpicmaxx
+\csname pgf@subpic@maxy@#1\endcsname\pgf@subpicmaxy
+\expandafter\edef\csname pgf@subpic@id@#1\endcsname{\subpictureid}%
+}
+
+% place current subpicture into named subpicture
+\def\pgfmergesubpicture#1{%
+\begin{pgfsubpicture}
+% place current subpicture
+\pgfplacesubpicture
+% override containing picture
+\expandafter\xdef\csname pgf@sh@pi@\subpictureid\endcsname{\csname pgf@subpic@id@#1\endcsname}%
+% copy contents of #1
+\pgfrestoresubpicture{#1}
+\pgflowlevelobj{\pgftransformshift{\pgfqpoint{\the\pgf@subpicminx}{\the\pgf@subpicminy}}}{\pgfqbox\pgf@hbox}
+\pgfpathrectanglecorners{\pgfqpoint{\the\pgf@subpicminx}{\the\pgf@subpicminy}}{\pgfqpoint{\the\pgf@subpicmaxx}{\the\pgf@subpicmaxy}}%
+\pgfusepath{use as bounding box}%
+%
+\end{pgfsubpicture}
+\expandafter\setbox\csname pgf@subpic@hbox@#1\endcsname\box\pgf@hbox
+\csname pgf@subpic@minx@#1\endcsname\pgf@subpicminx
+\csname pgf@subpic@miny@#1\endcsname\pgf@subpicminy
+\csname pgf@subpic@maxx@#1\endcsname\pgf@subpicmaxx
+\csname pgf@subpic@maxy@#1\endcsname\pgf@subpicmaxy
+% but don't save the new picture id, keep the existing one
+}
+
+\def\pgfrestoresubpicture#1{%
+\edef\act{\global\noexpand\setbox\pgf@hbox\noexpand\box\csname pgf@subpic@hbox@#1\endcsname}\act
+\expandafter\global\expandafter\pgf@subpicminx\csname pgf@subpic@minx@#1\endcsname
+\expandafter\global\expandafter\pgf@subpicminy\csname pgf@subpic@miny@#1\endcsname
+\expandafter\global\expandafter\pgf@subpicmaxx\csname pgf@subpic@maxx@#1\endcsname
+\expandafter\global\expandafter\pgf@subpicmaxy\csname pgf@subpic@maxy@#1\endcsname
+\xdef\subpictureid{\csname pgf@subpic@id@#1\endcsname}%
+}
+
+% Place a previously-created subpicture, lining up its origin with the current origin
+\def\pgfplacesubpicture{
+\pgfscope
+% expand current bounding box to accommodate subpicture
+\pgfpathrectanglecorners{\pgfqpoint{\the\pgf@subpicminx}{\the\pgf@subpicminy}}{\pgfqpoint{\the\pgf@subpicmaxx}{\the\pgf@subpicmaxy}}%
+\pgfusepath{use as bounding box}%
+%
+% make the subpicture a node in the containing picture
+\expandafter\gdef\csname pgf@sh@ns@\subpictureid\endcsname{rectangle}%
+\expandafter\xdef\csname pgf@sh@np@\subpictureid\endcsname{%
+  \noexpand\def\noexpand\southwest{\noexpand\pgfqpoint{\the\pgf@subpicminx}{\the\pgf@subpicminy}}%
+  \noexpand\def\noexpand\northeast{\noexpand\pgfqpoint{\the\pgf@subpicmaxx}{\the\pgf@subpicmaxy}}%
+}%
+\pgfgettransform\pgf@temp
+\expandafter\xdef\csname pgf@sh@nt@\subpictureid\endcsname{\pgf@temp}%
+\expandafter\xdef\csname pgf@sh@pi@\subpictureid\endcsname{\pgfpictureid}%
+%
+% align origin of subpicture with origin
+\pgftransformshift{\pgfqpoint{\the\pgf@subpicminx}{\the\pgf@subpicminy}}%
+\pgfqboxsynced{\pgf@hbox}%
+\endpgfscope
+}
+
+% Hook onto existing macro \pgf@shape@interpictureshift.
+% This is called whenever we look up an anchor of a node.
+% This hook recursively checks to see if the node's picture
+% is a subpicture of another, and if so, adjusts its position accordingly.
+
+% This is slow. It makes drawing trees O(n^2) in the depth of the tree.
+% The alternative is to store, for each picture, a list of the nodes
+% inside it. But this way doesn't require us to hijack \pgfnode, and
+% is robust to re-placement of a subpicture. A compromise would be
+% to store, for each picture, a list of the *subpictures* inside it.
+
+\let\orig@pgf@shape@interpictureshift\pgf@shape@interpictureshift
+\def\unwind@subpic#1{%
+% is #1 the current picture?
+\edef\subpicid{#1}%
+\ifx\subpicid\pgfpictureid
+% yes, we're done
+\else
+% does #1 have a parent picture?
+\expandafter\ifx\csname pgf@sh@pi@#1\endcsname\relax
+% no, the original node was not inside the current picture
+\fallback
+\else
+% yes, apply transform and move up to parent picture
+{%
+  \pgfsettransform{\csname pgf@sh@nt@#1\endcsname}%
+  \pgf@pos@transform{\pgf@x}{\pgf@y}%
+  \global\pgf@x=\pgf@x
+  \global\pgf@y=\pgf@y
+}%
+\unwind@subpic{\csname pgf@sh@pi@#1\endcsname}%
+\fi
+\fi
+}
+\def\pgf@shape@interpictureshift#1{%
+\edef\fallback{\pgf@x=\the\pgf@x\pgf@y=\the\pgf@y\noexpand\orig@pgf@shape@interpictureshift{#1}}%
+\unwind@subpic{\csname pgf@sh@pi@#1\endcsname}%
+}
+
+% \pgffitsubpicture{sw}{ne}
+% Make the subpicture fit in the rectangle from sw to ne, preserving its aspect ratio.
+\def\pgffitsubpicture#1#2{%
+% current size
+\pgfpointdiff{\pgfpointanchor{current subpicture}{south west}}{\pgfpointanchor{current subpicture}{north east}}%
+\pgf@xa=\pgf@x \pgf@ya=\pgf@y
+% desired size
+\pgf@process{\pgfpointdiff{#1}{#2}}%
+\pgf@xb=\pgf@x \pgf@yb=\pgf@y
+\pgfmathparse{min(\pgf@xb/\pgf@xa,\pgf@yb/\pgf@ya)}%
+\pgfmathparse{min(1,\pgfmathresult)}%
+\pgftransformscale{\pgfmathresult}%
+%
+% current position
+\pgfpointanchor{current subpicture}{center}%
+\pgf@xa=\pgf@x \pgf@ya=\pgf@y
+% desired position
+% we scaled transform, so apply reverse scaling to argument
+\pgfmathparse{1/\pgfmathresult}%
+\pgf@process{\pgfpointscale{\pgfmathresult}{\pgfpointlineattime{0.5}{#1}{#2}}}%
+\pgf@xb=\pgf@x \pgf@yb=\pgf@y
+\pgfpointdiff{\pgfpoint{\pgf@xa}{\pgf@ya}}{\pgfpoint{\pgf@xb}{\pgf@yb}}%
+\pgftransformshift{\pgfpoint{\pgf@x}{\pgf@y}}%
+}
+
+% utility functions -- not currently used
+
+\def\pgfnodedelete#1{%
+\expandafter\global\expandafter\let\csname pgf@sh@ns@#1\endcsname\relax
+\expandafter\global\expandafter\let\csname pgf@sh@np@#1\endcsname\relax
+\expandafter\global\expandafter\let\csname pgf@sh@nt@#1\endcsname\relax
+\expandafter\global\expandafter\let\csname pgf@sh@pi@#1\endcsname\relax
+\expandafter\global\expandafter\let\csname pgf@sh@ma@#1\endcsname\relax
+}
+
+\def\pgfnodeifexists#1#2#3{%
+\expandafter\ifx\csname pgf@sh@ns@#1\endcsname\relax#3\else#2\fi
+}
+
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/pgftree.sty
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/pgftree.sty	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,6 @@
+\RequirePackage{pgf}
+\RequirePackage{pgffor}
+\RequirePackage{pgfsubpic}
+
+\input{pgftree.tex}
+\endinput
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/pgftree.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/pgftree.tex	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,188 @@
+%    pgftree.tex
+%    Version 1.1, 25 Dec 2009
+
+%    Copyright 2009 by David Chiang
+
+%    This program is free software; you can redistribute it and/or modify
+%    it under the terms of the GNU General Public License as published by
+%    the Free Software Foundation; either version 2 of the License, or
+%    (at your option) any later version.
+
+%    This program is distributed in the hope that it will be useful,
+%    but WITHOUT ANY WARRANTY; without even the implied warranty of
+%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+%    GNU General Public License for more details.
+
+%    You should have received a copy of the GNU General Public License along
+%    with this program; if not, write to the Free Software Foundation, Inc.,
+%    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+% New in version 1.1:
+% - major restructuring to not do arbitrary nesting of subpicture environments
+% - sideways trees
+
+% To do:
+% - trees with all leaves at same level
+% - if \nodename does not exist as desired, wrap inside a rectangle node
+% - don't use pgfsubpic internals
+
+\newdimen\levelsep \levelsep=30pt
+\newdimen\subtreesep \subtreesep=2pt
+
+\def\leveldirection{down}
+\def\siblingdirection{right}
+
+% definitions of growing directions
+\def\pgftree@levelshift{\csname pgftree@levelshift@\leveldirection\endcsname}
+\def\pgftree@parentanchor{\csname pgftree@parentanchor@\leveldirection\endcsname}
+\def\pgftree@childanchor{\csname pgftree@childanchor@\leveldirection\endcsname}
+% these assume that the current subpicture is the child
+\def\pgftree@presiblingshift{\csname pgftree@presiblingshift@\siblingdirection\endcsname}
+\def\pgftree@postsiblingshift{\csname pgftree@postsiblingshift@\siblingdirection\endcsname}
+
+\def\pgftree@levelshift@down{\pgfpoint{0}{-\levelsep}}
+\def\pgftree@parentanchor@down{south}
+\def\pgftree@childanchor@down{north}
+
+\def\pgftree@levelshift@up{\pgfpoint{0}{\levelsep}}
+\def\pgftree@parentanchor@up{north}
+\def\pgftree@childanchor@up{south}
+
+\def\pgftree@levelshift@right{\pgfpoint{\levelsep}{0}}
+\def\pgftree@parentanchor@right{east}
+\def\pgftree@childanchor@right{west}
+
+\def\pgftree@levelshift@left{\pgfpoint{-\levelsep}{0}}
+\def\pgftree@parentanchor@left{west}
+\def\pgftree@childanchor@left{east}
+
+\def\pgftree@presiblingshift@right{\pgf@process{\pgf@x-\pgf@subpicminx \advance\pgf@x\subtreesep \pgf@y 0pt}}
+\def\pgftree@postsiblingshift@right{\pgf@process{\pgf@x\pgf@subpicmaxx \pgf@y 0pt}}
+
+\def\pgftree@presiblingshift@left{\pgf@process{\pgf@x-\pgf@subpicmaxx \advance\pgf@x-\subtreesep \pgf@y 0pt}}
+\def\pgftree@postsiblingshift@left{\pgf@process{\pgf@x\pgf@subpicminx \pgf@y 0pt}}
+
+\def\pgftree@presiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicminy \advance\pgf@y\subtreesep}}
+\def\pgftree@postsiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicmaxy}}
+
+\def\pgftree@presiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicmaxy \advance\pgf@y-\subtreesep}}
+\def\pgftree@postsiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicminy}}
+
+% for convenience if you are using \pgftree directly
+\def\drawnode#1{\pgfnode{rectangle}{base}{#1}{\nodename}{\pgfusepath{discard}}}
+\def\drawedge{%
+\pgfpathmoveto{\pgfpointanchor{\parentnodename}{\pgftree@parentanchor}}%
+\pgfpathlineto{\pgfpointanchor{\nodename}{\pgftree@childanchor}}%
+\pgfusepath{stroke}}
+
+% local variables that we need to assign to inside a \pgfforeach
+\newdimen\pgftree@childx
+\newdimen\pgftree@savechildx
+\newdimen\pgftree@childy
+\newdimen\pgftree@savechildy
+\newcount\pgftree@childi
+\newcount\pgftree@savechildi
+
+%%% \pgftree{subtree}
+
+\def\pgftree#1{%
+\def\nodename{r}%
+#1%
+\pgfplacesubpicture
+}
+
+%%% \pgfsubtree{root}{subtrees}
+% The first argument draws the root node using PGF/TikZ commands.
+% The node must be named \nodename.
+
+% The second argument is an even-length sequence of tokens.
+% Token 2n-1 in the sequence draws the nth edge. It should draw an edge from \parentnodename to \nodename.
+% Token 2n in the sequence draws the nth subtree. Its root must be named \nodename.
+
+\pgfnewsubpicture{children}
+\newdimen\pgftree@lastchildx
+\newdimen\pgftree@lastchildy
+
+\def\pgfsubtree#1#2{%
+\let\parentnodename\nodename
+\pgftree@savechildx=\pgftree@childx
+\pgftree@savechildy=\pgftree@childy
+\pgftree@savechildi=\pgftree@childi
+% Build subpicture with all the children and their subtrees
+{\pgftree@childx=0pt%
+\pgftree@childy=0pt%
+\pgftree@childi=0%
+\process@children #2}%
+\begin{pgfsubpicture}%
+% Create node
+#1%
+\ifnum\pgftree@childi>0%
+% Place children
+% move down \levelsep
+{\pgftransformshift{\pgftree@levelshift}%
+% center so that parent is midway between origins of first and last children
+\pgftransformshift{\pgfpointscale{-0.5}{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}}%
+\pgfplacesubpicture}%
+% Draw the edges
+{\pgftree@childi=0%
+\process@edges #2}%
+\fi
+\end{pgfsubpicture}%
+\global\pgftree@childi=\pgftree@savechildi
+\global\pgftree@childx=\pgftree@savechildx
+\global\pgftree@childy=\pgftree@savechildy
+}
+
+\def\process@children{%
+\pgfutil@ifnextchar\egroup
+{% No more children, step back to origin of last child
+\global\pgftree@childx\pgftree@lastchildx
+\global\pgftree@childy\pgftree@lastchildy
+\global\pgftree@childi\pgftree@childi
+\ifnum\pgftree@childi>0%
+\pgfrestoresubpicture{children}% pass children back to caller
+\fi
+}%
+{\@process@children}%
+}
+\def\@process@children#1#2{% #1 is the edge, #2 is the child
+% Build the current child
+{\edef\nodename{\parentnodename-\the\pgftree@childi}%
+#2}%
+\begin{pgfsubpicture}%
+% Place current child
+\ifnum\pgftree@childi>0% the first child is always at 0
+\pgftree@presiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y
+\fi
+{\pgftransformshift{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}%
+\pgfplacesubpicture}%
+\global\pgftree@lastchildx\pgftree@childx
+\global\pgftree@lastchildy\pgftree@childy
+\pgftree@postsiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y
+% Save the augmented row of children back into "children"
+\end{pgfsubpicture}
+\ifnum\pgftree@childi>0%
+\pgfmergesubpicture{children}
+\else
+\pgfsavesubpicture{children}%
+\fi
+\advance\pgftree@childi by 1%
+\process@children
+}
+
+\def\process@edges{%
+\pgfutil@ifnextchar\egroup
+{}%
+{\@process@edges}%
+}
+\def\@process@edges#1#2{%
+\edef\nodename{\parentnodename-\the\pgftree@childi}%
+#1%
+\advance\pgftree@childi by 1%
+\process@edges
+}
+
+\def\subtreeof#1{%
+% the subpicture which contains a node also contains exactly its subtree
+\csname pgf@sh@pi@#1\endcsname
+}
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/sol03.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/sol03.tex	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,117 @@
+\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
+\usepackage{graphicx}
+%\usepackage[latin1]{inputenc}
+\usepackage{amsmath, amsthm, amssymb}
+\usepackage{typearea}
+\usepackage{algorithm}
+\usepackage{algorithmic}
+\usepackage{fullpage}
+\usepackage{mathtools}
+\usepackage[all]{xy}
+\usepackage{tikz}
+\usepackage{tikz-qtree}
+\usetikzlibrary{decorations.pathmorphing} % noisy shapes
+\usetikzlibrary{fit}					% fitting shapes to coordinates
+\usetikzlibrary{backgrounds}	% drawin
+\usetikzlibrary{shapes,snakes}
+\addtolength{\voffset}{-20pt}
+\title{CSP Exercise 03 Solution}
+\author{Eugen Sawin}
+\renewcommand{\familydefault}{\sfdefault}
+\newcommand{\E}{\mathcal{E}}
+\newcommand{\R}{\mathcal{R}}
+
+%\include{pythonlisting}
+
+\pagestyle{empty}
+\begin{document}
+\maketitle
+
+\section*{Exercise 3.1}
+The minimal network is $N_0 = \langle (v_1,v_2,v_3),(\{2,3\},\{1,2,3,4\},\{1,3,4\}),\{<_{(v_1,v_2)},<_{(v_1,v_3)},=_{(v_2,v_3)}\} \rangle$.
+
+\section*{Exercise 3.2}
+(a) The network for the puzzle is \emph{(we do not name the variables consecutively to keep a clear connection to the original puzzle fields)}
+\begin{align*}
+N = \langle (v_1,v_2,v_3,v_8),(\{ATOLL\},\{TOLL,HEAT\},\{EAT\},\{TOLL,HEAT\}),\{R_{v_1,v_2,v_8},R_{v_2,v_3},R_{v_3,v_8}\} \rangle
+\end{align*}
+with
+\begin{align*}
+R_{v_1,v_2,v_8} &= \{(ATOLL,HEAT,TOLL)\}\\
+R_{v_2,v_3} &= \{(HEAT,EAT)\}\\
+R_{v_3,v_8} &= \{(EAT,TOLL)\}
+\end{align*}
+(b) See figure 1.
+\begin{figure}[h]
+\centering
+\tikzstyle{var}=[circle,
+  draw=black!100,
+  fill=black!0]
+\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
+  \matrix[row sep=0.2cm,column sep=0.5cm] {    
+    & \node(v1)[var]{$v_1$}; & &\\
+    \node(v2)[var]{$v_2$}; & \node(v3)[var]{$v_3$}; & \node(v8)[var]{$v_8$};\\
+  };
+  \path[-]
+  (v1) edge (v2)
+  (v1) edge (v8)
+  (v2) edge (v3)
+  (v3) edge (v8)
+  ;      
+\end{tikzpicture}
+\caption{(3.2b) primal constraint graph of $N$}
+\end{figure}\\
+(c) See figure 2.
+\begin{figure}[h]
+\centering
+\tikzstyle{var}=[ellipse,
+  draw=black!100,
+  fill=black!0]
+\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
+  \matrix[row sep=0.2cm,column sep=0.5cm] {    
+    & \node(v1v2v8)[var]{$v_1,v_2,v_8$};\\
+    \node(v2v3)[var]{$v_2,v_3$}; & &\node(v3v8)[var]{$v_3,v_8$};\\
+  };
+  \path[-]
+  (v1v2v8) edge node[auto=right]{$v_2$} (v2v3)
+  (v1v2v8) edge node[auto=left]{$v_8$} (v3v8)
+  (v2v3) edge node[auto=left]{$v_3$} (v3v8)
+  ;      
+\end{tikzpicture}
+\caption{(3.2c) dual constraint graph of $N$}
+\end{figure}
+
+\section*{Exercise 2.2}
+We define the following undirected graph $G = \langle W, E \rangle$ with $\{w_i,w_j\} \in E$ iff $w_i$ and $w_j$ dislike each other. Additionally we define two sets $B_1 = B_2 = \{\}$ for the buildings and an auxiliary set $F = \{\}$ for remembering \emph{expanded} nodes.
+\begin{enumerate}
+  \item For all $w_i \in W$ with $w_i \notin \bigcup E$ add $w_i$ to $B_1$ and $F$, i.e. $B_1 = B_1 \cup \{w_i\}$ and $F = F \cup \{w_i\}$. This way we assign all workers, who are liked by everyone to building $B_1$.
+  \item If $F = W$ terminate, we have found a solution.\\
+  Otherwise select any $w_i \notin F$ and add it to $B_1$ and $F$, i.e. $B_1 = B_1 \cup \{w_i\}$ and $F = F \cup \{w_i\}$.\\
+  Add all its disliked neighbours to $B_2$, i.e. $B_2 = B_2 \cup \{w_j \mid \{w_i,w_j\} \in E\}$.\\
+  If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.
+  \item If there a $w_i \notin F$ with $w_i \in B_1 \cup B_2$ select it, otherwise continue with $2.$\\
+  Add all its disliked neighbours to the other building, i.e. $w_i \in B_1 \implies B_2 = B_2 \cup \{w_j \mid (w_i,w_j) \in E\}$, $w_i \in B_2 \implies B_1 = B_1 \cup \{w_j \mid (w_i,w_j) \in E\}$ and $F = F \cup \{w_i\}$.\\
+  If $B_1 \cap B_2 \neq \emptyset$ terminate, there was a conflict and therefore no possible solution.\\
+  Otherwise continue with $3.$
+\end{enumerate}
+This is essentially a random walk through the graph with some book keeping. Assumming that set containment can be tested in $\mathcal{O}(1)$ and set intersection in $\mathcal{O}(n)$ we have an asymptotic complexity of $\mathcal{O}(|W| \cdot |E|)$ (this includes the optimisation, that the intersection test is only done once when $F = W$ holds).
+
+\section*{Exercise 2.3}
+(a) $VertexCover \in NP$ because by guessing the vertex set $V'$, we can iterate over all $\{v_1,v_2\} \in E$ and check if $v_1 \in V'$ or $v_2 \in V'$ holds in polynomial time.\\
+We show $Clique \le_P VertexCover$. Given an undirected graph $G = \langle V,E \rangle$ and $k \in N$ we build a graph $G_2 = \langle V_2, E_2 \rangle$ so that there is a clique $V' \subseteq V$ with $|V'| \geq k$ iff there is a vertex cover $V_2' \subseteq V_2$ with $|V_2'| \leq k_2$ given following construction:
+\begin{itemize}
+  \item $V_2 = V$
+  \item $E_2 = \{\{v_i,v_j\} \mid \{v_i,v_j\} \notin E\}$
+  \item $k_2 = |V| - k$
+\end{itemize}
+If there is a vertex cover $V_2'$ of size $\leq k_2$, i.e. $\forall{e \in E}: \exists{v \in V_2'}: v \in e$ then it follows that there must be a clique of at least size $|V|-k_2$ in the complementary graph and vice versa, because for each disconnected vertex pair in one graph, there is a connected pair in the other.\\
+The construction takes linear time, hence it follows that $VertexCover \in NP$-$complete$. \qed\\\\
+(b) $Dominating Set \in NP$ because by guessing the vertex set $V'$, we can iterate over all $v \in V$ and check if $v \in V'$ or $\exists{v' \in V}: \{v,v'\} \in E$ holds in polynomial time.\\
+We show $Vertex Cover \le_P DominatingSet$. Given an undirected graph $G = \langle V, E \rangle$ and $k \in N$ we build a graph $G_2 = \langle V_2, E_2 \rangle$ so that there is a vertex cover $V' \subseteq V$ with $|V'| \leq k$ iff there is a dominating set $V_2' \subseteq V_2$ with $|V_2| \leq k$ given following construction:
+\begin{itemize}
+  \item $V_2 = V \cup \{v_e \mid e \in E\}$
+  \item $E_2 = E \cup \{\{v,v_e\} \mid v,v_e \in V_2$ and $e \in E\}$
+\end{itemize}
+By introducing the additional nodes for all vertices in $G$, we make sure that the dominating set $V_2'$, by covering all vertices in $G_2$, implicitely covers all edges in $G$. The other direction follows analogously, if a vertex cover $V'$ covers all edges in $G$ it follows that the same set covers all vertices in $G_2$.\\
+The construction takes linear time, hence it follows that $DominatingSet \in NP$-$complete$. \qed
+\end{document}
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/tikz-qtree-compat.sty
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/tikz-qtree-compat.sty	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,72 @@
+%    tikz-qtree-compat.tex
+%    Version 1.1, 25 Dec 2009
+
+\RequirePackage{tikz-qtree}
+
+\let\orig@Tree\Tree
+\def\Tree{\automath \qtreeprimes@internal \orig@Tree}
+
+\def\qsetw#1{\message{\noexpand\qsetw is not supported, sorry!}}
+\def\faketreewidth#1{\message{\noexpand\faketreewidth is not supported, sorry!}}
+\def\qbalance{\message{\noexpand\qbalance is not supported, sorry!}}
+\def\qframesubtree{\message{\noexpand\qframesubtree is not supported, sorry!}}
+
+% Implement \qroof as a fancy leaf node
+\newtoks\@qrooflabel
+
+\def\qroof#1.{%
+\begin{tikzpicture}[baseline]
+{\pgftransformshift{\pgftree@levelshift}%
+\node(qroofbot){#1};}
+\@qroof
+}
+\def\@qroof{\@ifnextchar\egroup{%
+% since we are putting the qroof inside a node, we already have an inner sep
+% so for the purposes of defining our bounding box, we must eliminate inner sep
+\begin{pgfsubpicture}
+\node [inner sep=0pt] {\the\@qrooflabel};% 
+\end{pgfsubpicture}
+\pgfpathrectanglecorners{\pgfpoint{\the\pgf@subpicminx}{\the\pgf@subpicminy}}{\pgfpoint{\the\pgf@subpicmaxx}{\the\pgf@subpicmaxy}}%
+\pgfusepath{use as bounding box}%
+\node (qrooftop) {\the\@qrooflabel};
+\draw \roof@edge{qrooftop}{qroofbot};%
+\end{tikzpicture}}
+{\@@qroof}}
+\def\@@qroof#1{\expandafter\@qrooflabel\expandafter{\the\@qrooflabel #1}\@qroof}
+
+%%% This is lifted straight from qtree.sty
+
+% and another odd convenience:
+%
+% Make _, ^ go into math mode automatically in the scope of \automath
+%
+{ % Temporarily change catcodes 
+\catcode`\_=\active
+\catcode`\^=\active
+
+  \global\def\automath{%
+    \catcode`\_=\active
+    \catcode`\^=\active
+    \def_##1{\@ifnextchar^{\automath@two_{##1}}{\ensuremath{\sb{##1}}}}%
+    \def^##1{\@ifnextchar_{\automath@two^{##1}}{\ensuremath{\sp{##1}}}}}
+}
+\def\automath@two#1#2#3#4{\ensuremath{#1{#2}\relax #3{#4}}}
+% Restore default catcodes for ^, _
+\def\noautomath{\catcode`\_=8 \catcode`\^=7 }
+
+
+% Let \0, \1, \2 produce ^0, $'$, $''$
+% The \rlap results in better centering of the label (ignoring the
+%  superscript)
+\def\qtreeprimes@internal{%
+  \def\0{\ifmmode ^0\else \rlap{$^0$}\fi}%
+  \def\1{\ifmmode '\else \rlap{$'$}\fi}%
+  \def\2{\ifmmode ''\else \rlap{$''$}\fi}%
+}
+
+% Same commands, but without the \rlap feature
+\def\qtreeprimes{%
+  \def\0{\ensuremath{^0}}%
+  \def\1{\ensuremath{'}}%
+  \def\2{\ensuremath{''}}}
+
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/tikz-qtree-manual.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/tikz-qtree-manual.tex	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,392 @@
+\documentclass{article}
+
+\usepackage{xltxtra,fontspec}
+
+\iffalse
+\setmainfont[Mapping=tex-text]{DejaVu Serif}
+\setmonofont[Scale=0.95]{DejaVu Sans Mono}
+\newfontfamily\verbfont[Scale=0.8]{DejaVu Sans Mono}
+\newfontfamily\ar[Script=Arabic]{DejaVu Sans}
+\newfontfamily\ja{VL Gothic}
+\newfontfamily\javerbfont[Scale=0.85,LetterSpace=5.0]{VL Gothic}
+\fi
+
+\iftrue
+\setmainfont[Mapping=tex-text]{DejaVu Serif}
+\setmonofont[Scale=0.95]{DejaVu Sans Mono}
+\newfontfamily\verbfont[Scale=0.8]{DejaVu Sans Mono}
+\newfontfamily\ar[Script=Arabic]{DejaVu Sans}
+\newfontfamily\ja{Hiragino Maru Gothic Pro}
+\newfontfamily\javerbfont[Scale=0.85,LetterSpace=5.0]{Hiragino Maru Gothic Pro}
+\fi
+
+\usepackage{tikz}
+\usepackage{tikz-qtree}
+
+\usepackage{fullpage}
+
+\usepackage{fancyvrb,fvrb-ex}
+\fvset{gobble=0,xleftmargin=0.5in,xrightmargin=2.75in,formatcom=\verbfont}
+\VerbatimFootnotes
+
+\newcommand\tikztree{\texttt{tikz-qtree}}
+
+\tikzset{>=latex}
+
+\title{\tikztree: better trees with TikZ}
+\author{David Chiang}
+\date{Version 1.11 (Christmas 2010)}
+
+\begin{document}
+
+\maketitle
+
+The \tikztree{} package provides a macro for drawing trees with
+TikZ\footnote{\texttt{http://sourceforge.net/projects/pgf/}} using the
+easy syntax of Alexis Dimitriadis'
+Qtree\footnote{\texttt{http://www.ling.upenn.edu/advice/latex/qtree/}}. It
+improves on TikZ's standard tree-drawing facility by laying out tree
+nodes without collisions; it improves on Qtree by adding lots of
+features from TikZ; and it improves on \verb|pst-qtree| in being
+usable with pdf\TeX{} and
+\XeTeX{}.\footnote{Although \XeTeX{} works with \verb|pst-qtree| using the \verb|xetex-pstricks| package. For typesetting very large trees or a large number of trees, this may be the better option.}
+
+\section{Basics}
+
+To load the package in \LaTeX{}:
+\begin{Verbatim}
+\usepackage{tikz}
+\usepackage{tikz-qtree}
+\end{Verbatim}
+%
+The simplest usage is identical to Qtree:
+\begin{center}
+\begin{SideBySideExample}
+\Tree [.S [.NP [.Det the ] [.N cat ] ] 
+          [.VP [.V sat ] 
+               [.PP [.P on ] 
+                    [.NP [.Det the ] [.N mat ] ] ] ] ]
+\end{SideBySideExample}
+\end{center}
+Subtrees are delimited by square brackets. A subtree's root label is
+joined by a dot (\verb|.|) to its opening bracket.\footnote{You can
+also write the label after the closing bracket instead of the opening
+bracket, or both, or neither. Please see the Qtree documentation for
+details.} As in Qtree, spaces are required after every (internal or
+leaf) node label. 
+
+\verb|\Tree| works inside or outside a
+\verb|tikzpicture| environment, but many of the features described 
+below require the explicit \verb|tikzpicture| environment.
+
+\goodbreak
+
+\paragraph{Options} Some options for standard TikZ trees work for \verb|\Tree| as
+well:
+\begin{itemize}
+\item \verb|level distance|: vertical distance between the anchors of a parent and its children
+\item \verb|sibling distance|: horizontal distance between the boundaries of sister subtrees (not the anchors of their roots, as in standard TikZ trees). Note that TikZ nodes already have some horizontal space around them (\verb|inner xsep|, by default \verb|0.3333em|), so even \verb|sibling distance=0pt| leaves some room.
+\end{itemize}
+These are set either by writing
+\verb|\tikzset{|\textit{option}\verb|=|\textit{value}\verb|}| or by
+writing \verb|[|\textit{option}\verb|=|\textit{value}\verb|]| after a
+\verb|\begin{tikzpicture}| or \verb|\begin{scope}|.\footnote{Allowing
+options after \verb|\Tree| would have made sense, but there would be
+no way to disambiguate the two uses of square brackets.} For example:
+
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\tikzset{level distance=72pt}
+\Tree [.NP [.Adj tall ] [.N tree ] ]
+\end{tikzpicture}
+%
+\begin{tikzpicture}[sibling distance=72pt]
+\Tree [.NP [.Adj fat ] [.N tree ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+
+The \verb|grow=|\textit{direction}\/ and \verb|grow'=|\textit{direction}\/ options control the orientation of trees just as for standard TikZ trees. However, \textit{direction}\/ must be one of \verb|up|, \verb|down|, \verb|left|, or \verb|right|. The difference between \verb|grow| and \verb|grow'| is that \verb|grow| places children counterclockwise with respect to their parent and \verb|grow'| places them clockwise:
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}[grow'=down]
+\Tree [.NP [.Adj reverse ] [.N tree ] ]
+\end{tikzpicture}
+%
+\begin{tikzpicture}[grow'=up]
+\Tree [.NP [.Adj upside-down ] [.N tree ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\vspace{3ex}
+\begin{SideBySideExample}
+\begin{tikzpicture}[grow=left]
+\tikzset{level distance=60pt,sibling distance=18pt}
+\tikzset{execute at begin node=\strut}
+\Tree [.NP [.Adj sideways ] [.N tree ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+Note that in sideways trees, \verb|level distance| is horizontal and \verb|sibling distance| is vertical. Sideways trees do take a little extra adjusting to look right, since the defaults are geared towards vertically growing trees. The meaning of the option \verb|execute at begin node=\strut| is, before typesetting the label of every node, insert the command \verb|\strut|, which is an invisible box that maximizes the height and depth of the node.
+
+\paragraph{Styles} TikZ lets you define \emph{styles}\/ which encapsulate multiple options:
+\begin{Verbatim}
+\tikzset{small/.style={level distance=20pt,sibling distance=0pt}}
+\end{Verbatim}
+Then the option \verb|small| causes the options in its definition to be used:
+\begin{center}
+\tikzset{small/.style={level distance=20pt,sibling distance=0pt}}
+\begin{SideBySideExample}
+\begin{tikzpicture}[small]
+\Tree [.NP [.Adj small ] [.N tree ] ]
+\end{tikzpicture}
+%
+\begin{tikzpicture}
+\Tree [.NP [.Adj normal ] [.N tree ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+The following TikZ styles are automatically applied inside trees,
+providing a hook for you to change the appearance of particular kinds
+of tree parts:
+\begin{itemize}
+\item \verb|every tree node| to every (internal and leaf) node (default: \verb|anchor=base|)
+\item \verb|every internal node| to every internal node
+\item \verb|every leaf node| to every leaf node
+\item \verb|edge from parent| to every edge (default: \verb|draw|)
+\end{itemize}
+
+The options for nodes and edges are all handled by TikZ and are
+described in detail in the TikZ documentation. For example, if you
+have a font named \verb|\ar| and want to set all the leaf labels in
+this font:
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\tikzset{grow'=down}
+\tikzset{every leaf node/.style={font=\ar}}
+\Tree [.S [.NP القط ] 
+          [.VP [.V وجلس ] 
+               [.PP [.P على ] [.NP حصيرة ] ] ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+
+You can make the nodes in a sideways tree line up on their left edge using \verb|anchor=base west|:
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\tikzset{grow'=right,level distance=32pt}
+\tikzset{execute at begin node=\strut}
+\tikzset{every tree node/.style={anchor=base west}}
+\Tree [.S [.NP [.Det the ] [.N cat ] ] 
+          [.VP [.V sat ] 
+               [.PP [.P on ] 
+                    [.NP [.Det the ] [.N mat ] ] ] ] ]
+\end{tikzpicture}                    
+\end{SideBySideExample}
+\end{center}
+
+In Qtree, it was allowed to use a line break (\verb|\\|) inside a node. TikZ nodes by default don't allow this, but the \verb|align| option (in PGF/TikZ version 2.1 or later) enables it as a side effect:\footnote{Thanks to Alan Munn for figuring this out. Prior to PGF/TikZ version 2.1, the fix was to use the options \verb|text width=2em,text centered|.}
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\tikzset{every tree node/.style={align=center,anchor=north}}
+\Tree [.S [.NP Det\\the N\\cat ]
+          [.VP V\\sat
+               [.PP P\\on
+                    [.NP Det\\the N\\mat ] ] ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+
+You can also define a style for all the edges in a tree. For example, if you want the edges to be a little darker:
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\tikzset{edge from parent/.style={draw,thick}}
+\Tree [.S [.NP [.Det the ] [.N cat ] ] 
+          [.VP [.V sat ] 
+               [.PP [.P on ] 
+                    [.NP [.Det the ] [.N mat ] ] ] ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+The \verb|draw| option is necessary, as by default they will not be
+drawn. As a more complex example, edges have an
+\verb|edge from parent path| option which lets you change the shape of
+the edge. Its value is a TikZ path expressed in terms of
+\verb|\tikzparentnode|, the parent node, and \verb|\tikzchildnode|,
+the child node.
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\tikzset{edge from parent/.style=
+  {draw,
+   edge from parent path={(\tikzparentnode.south) 
+                          -- +(0,-8pt) 
+                          -| (\tikzchildnode)}}} 
+\Tree [.S [.NP [.Det the ] [.N cat ] ] 
+          [.VP [.V sat ] 
+               [.PP [.P on ] 
+                    [.NP [.Det the ] [.N mat ] ] ] ] ]
+\end{tikzpicture}                    
+\end{SideBySideExample}
+\end{center}
+
+\clearpage
+
+\section{Embedding TikZ nodes}
+
+Inside a \verb|\Tree|, in place of a node label, you can use a TikZ
+\verb|\node| command.\footnote{\verb|\Tree| specifically watches out
+for the token \verb|\node|; do not use \verb|\path node| or other
+equivalents.}
+\begin{quote}
+\verb|\node [|\textit{options}\verb|] (|\textit{name}\verb|) {|\textit{label}\verb|};|
+\end{quote}
+Don't forget the terminating semicolon. The
+\verb|[|\textit{options}\verb|]|, which are optional, let you change
+the appearance of the node; for example, the \verb|draw| option draws
+a border around the node. The \verb|(|\textit{name}\verb|)|, which is
+also optional, can be used for drawing lines/arrows to/from the node.
+\begin{center}
+\begin{Example}
+\begin{tikzpicture}
+\Tree [.CP [.NP \node(wh){what}; ] 
+           [.C$'$ [.I did ] 
+                  [.\node[draw]{IP}; 
+                    [.NP [.Det the ] [.N cat ] ]
+                    [.VP [.V sit ] 
+                         [.PP [.P on ] 
+                              [.\node[draw]{NP}; 
+                                [.NP [.Det a ] [.N book ] ] 
+                                [.PP [.P about ] [.NP \node(t){$t$}; ] ] ] ] ] ] ] ]
+\draw[semithick,->] (t)..controls +(south west:5) and +(south:5) .. (wh);
+\end{tikzpicture}
+\end{Example}
+\end{center}
+
+You can also refer to the whole subtree rooted at the node named \textit{name}\/ using \verb|\subtreeof{|\textit{name}\verb|}|:
+\begin{center}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\Tree [.S [.NP [.Det the ] [.N cat ] ] 
+          [.\node(site){VP}; [.V sat ] ] ]
+\begin{scope}[shift={(1in,0.5in)}]
+\Tree [.\node(root){VP}; VP$^\ast$
+                         [.PP [.P on ] 
+                              [.NP [.Det the ] [.N mat ] ] ] ]
+
+\end{scope}
+
+\draw[->](\subtreeof{root}.140) .. 
+  controls +(west:1) and +(east:1) .. (site);
+
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+
+\noindent Another example for machine translation people:
+\begin{center}
+\fvset{formatcom=\javerbfont}
+\begin{SideBySideExample}
+\begin{tikzpicture}
+\Tree [.S [.NP [.Det \node(e1){the}; ] 
+               [.N \node(e2){cat}; ] ] 
+          [.VP [.V \node(e3){sat}; ] 
+               [.PP [.P \node(e4){on}; ] 
+                    [.NP [.Det \node(e5){the}; ] 
+                         [.N \node(e6){mat}; ] ] ] ] ]
+
+\begin{scope}[yshift=-5in,grow'=up]
+\tikzset{every leaf node/.style={font=\ja}}
+\Tree [.S [.NP \node(j1){猫が}; ] 
+          [.VP [.PP [.NP [.NP \node(j2){マット}; ] 
+                         [.Part \node(j3){の}; ]
+                         [.NP \node(j4){上}; ] ] 
+                    [.P \node(j5){に}; ] ] 
+               [.V \node(j6){土}; ] ] ]
+\end{scope}
+
+\begin{scope}[dashed]
+\draw (e1)--(j1);
+\draw (e2)--(j1);
+\draw (e3)..controls +(south:5) and +(north:4)..(j6);
+\draw (e4)--(j4);
+\draw (e4)--(j5);
+\draw (e5)--(j2);
+\draw (e6)--(j2);
+\end{scope}
+
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+
+\section{Explicit edges}
+
+The edge from a parent to a child node is normally automatically drawn
+for you, but you can do it yourself with an \verb|\edge| command
+\emph{before}\/ the corresponding child node. It is similar to the
+TikZ \verb|edge from parent| command.\footnote{Except that a TikZ
+\texttt{edge from parent} comes after the child node. I thought it was
+more logical to put it before.}
+\begin{quote}
+\verb|\edge [|\textit{options}\verb|];|
+\end{quote}
+Again, don't forget the semicolon. The
+\verb|[|\textit{options}\verb|]|, which are optional, let you change
+the appearance of the edge. You can also add an edge label:
+\begin{quote}
+\verb|\edge [|\textit{options}\verb|] node [|\textit{options}\verb|] {|\textit{label}\verb|};|
+\end{quote}
+Typically one will use the \verb|auto| option for edge labels, which
+places the label to the side of the edge.
+\begin{center}
+\begin{SideBySideExample}[xrightmargin=1.25in]
+\newcommand{\initial}[1]{\ensuremath{\alpha_{\textrm{\scriptsize #1}}}}
+\newcommand{\auxiliary}[1]{\ensuremath{\beta_{\textrm{\scriptsize #1}}}}
+
+\begin{tikzpicture}[level distance=36pt,sibling distance=12pt]
+\Tree [.\initial{sat} 
+        \edge node[auto=right]{1}; \initial{cat} 
+        \edge[dashed] node[auto=left]{2}; 
+        [.\auxiliary{on} 
+          \edge node[auto=left]{2}; \initial{mat} ] ]
+\end{tikzpicture}
+\end{SideBySideExample}
+\end{center}
+The fact that \verb|auto=left| draws a label on the right and
+\verb|auto=right| draws a label on the left makes sense if you think
+about the tree growing from the root to the leaves.
+
+There is a predefined style that draws a ``roof'' over a node, like Qtree's \verb|\qroof|:
+\begin{center}
+\begin{Example}
+\begin{tikzpicture}[level distance=36pt]
+\Tree [.S [.NP [.N this ] ] 
+          [.VP [.V is ] 
+               [.NP \edge[roof]; {a noun phrase 
+                                  the complexity of which 
+                                  is too great for me to parse} ] ] ]
+\end{tikzpicture}
+\end{Example}
+\end{center}
+
+\section{Qtree compatibility}
+
+For basic trees, \tikztree{} can be used as a drop-in replacement for Qtree, but most of Qtree's advanced features are either not accessed in the same way in \tikztree{} or not implemented at all. There is a package \verb|tikz-qtree-compat| which can be loaded to improve compatibility. Supported so far are:
+\begin{itemize}
+\item Superscripts and subscripts outside of math mode, and \verb|\automath|
+\item The \verb|\0|, \verb|\1|, and \verb|\2| commands, and \verb|\qtreeprimes|
+\item The \verb|\qroof| command
+\end{itemize}
+For unsupported commands, warning messages are printed, but at least your file should compile.
+
+\section*{Acknowledgements}
+This was all Dan Gildea's idea. Thanks to Alan Munn for his very helpful suggestions.
+
+\section*{Contact}
+Please send suggestions to \verb|chiang@isi.edu|.
+
+\end{document}
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/tikz-qtree.sty
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/tikz-qtree.sty	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,4 @@
+\RequirePackage{tikz}
+\RequirePackage{pgftree}
+\input{tikz-qtree.tex}
+\endinput
diff -r 07d59c14c712 -r b5c5ecd64f6a exercises/solutions/tikz-qtree.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/solutions/tikz-qtree.tex	Fri May 18 22:37:44 2012 +0200
@@ -0,0 +1,181 @@
+%    tikz-qtree.tex
+%    Version 1.11, 25 Dec 2010
+
+%    Copyright (C) 2002, 2009 by David Chiang
+
+%    This program is free software; you can redistribute it and/or modify
+%    it under the terms of the GNU General Public License as published by
+%    the Free Software Foundation; either version 2 of the License, or
+%    (at your option) any later version.
+
+%    This program is distributed in the hope that it will be useful,
+%    but WITHOUT ANY WARRANTY; without even the implied warranty of
+%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+%    GNU General Public License for more details.
+
+%    You should have received a copy of the GNU General Public License along
+%    with this program; if not, write to the Free Software Foundation, Inc.,
+%    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+% New in version 1.11:
+% - make options compatible with standard tikz trees
+
+% New in version 1.1:
+
+% - sideways trees
+
+%% These macros facilitate building up an object recursively before
+%% putting it into the input stream.
+
+\newtoks\@result
+\def\@call#1#2{\let\@cont=#2\bgroup\@result={}#1}
+\def\@return{\global\@result=\@result\egroup\@cont}
+
+\def\@ifequal#1#2{\edef\testa{#1}\edef\testb{#2}\ifx\testa\testb}
+
+%% scan a tree: this just scans a subtree and then puts it onto the
+%% input stream
+
+\def\Tree{\@call\@subtree\@Tree}
+\def\@Tree{%
+%\showthe\@result %debug
+\ifpgfpicture % is there a test for tikzpicture?
+\pgftree{\the\@result}%
+\else
+\tikzpicture[baseline]\pgftree{\the\@result}\endtikzpicture
+\fi
+}
+
+%% scan a subtree
+\newtoks\child@list
+\newtoks\root@node
+
+\def\@subtree[{%
+\root@node={}%
+\pgfutil@ifnextchar.{\@call\@interior\@@subtree}{\@@@subtree}}
+\def\@@subtree{%
+\root@node=\@result
+\@@@subtree
+}
+\def\@@@subtree{%
+\@call\@children\@@@@subtree
+}
+\def\@@@@subtree]{%
+\child@list=\@result
+\pgfutil@ifnextchar.{\@call\@interior\@@@@@subtree}{\@@@@@@subtree}}
+\def\@@@@@subtree{%
+%%% Check for mismatch.
+\@ifequal{\the\root@node}{\pgfutil@empty}%
+  \root@node=\@result
+\fi
+\@ifequal{\the\root@node}{\the\@result}\else
+  \message{Warning: mismatched labels, \the\root@node{} and \the\@result.}%
+\fi
+\@@@@@@subtree
+}
+\def\@@@@@@subtree{%
+\@ifequal{\the\root@node}{\pgfutil@empty}%
+\edef\act{\noexpand\@result={\noexpand\pgfsubtree{\noexpand\path coordinate (\noexpand\nodename);}{\the\child@list}}}%
+\else
+\edef\act{\noexpand\@result={\noexpand\pgfsubtree{\the\root@node}{\the\child@list}}}%
+\fi
+\act
+\@return}
+
+%% scan a sequence of subtrees or leaves
+
+\newif\ifscanned@edge
+
+\def\@children{%
+\scanned@edgefalse
+\child@list{}%
+\@@children}
+\def\@@children{%
+\pgfutil@ifnextchar]{\@result\child@list\@return}{% end of children
+\pgfutil@ifnextchar\edge{% explicit edge
+\ifscanned@edge
+\message{Warning: more than one edge given for a single child}\let\next\@@children % ignore
+\else
+\scanned@edgetrue\let\next\@@@children
+\fi
+\@call\@edge\next}{%
+% else, a real node is next
+\ifscanned@edge\else % no explicit edge, supply default
+\expandafter\child@list\expandafter{\the\child@list{\edge@adapter{}}}%
+\fi
+\scanned@edgefalse
+\pgfutil@ifnextchar[{\@call\@subtree\@@@children}% subtree
+{\@call\@leaf\@@@children}% leaf
+}}}
+\def\@@@children{%
+% wrap child inside curly braces
+\expandafter\@result\expandafter{\expandafter{\the\@result}}%
+\edef\act{\noexpand\child@list{\the\child@list \the\@result}}\act
+\@@children
+}
+
+\def\@interior.{\@result{\node[alias=\nodename][every tree node,every internal node]}\@label}
+
+\def\@leaf{\@call\@label\@@leaf}
+\def\@@leaf{\edef\act{\noexpand\@result{\noexpand\pgfsubtree{\noexpand\node[alias=\noexpand\nodename][every tree node,every leaf node]\the\@result}{}}}\act\@return}
+
+\def\@edge\edge #1;{%
+\@result{\edge@adapter{#1}}%
+\@return}
+\def\edge@adapter#1{%
+\let\tikzparentnode\parentnodename
+\let\tikzchildnode\nodename
+\path edge from parent #1;%
+}
+
+% a label is either text or PGF/TikZ code starting with \node
+\def\@label{\pgfutil@ifnextchar\node{\@litlabel}{\@@label}}
+\def\@@label#1 {%
+\expandafter\@result\expandafter{\the\@result{#1};}%
+\@return}
+
+% try to copy \node command into \@result without stripping braces
+\def\@litlabel\node{\@@litlabel}
+\def\@@litlabel{\pgfutil@ifnextchar\bgroup{\@@@litlabel}{\@@@@litlabel}}
+\def\@@@litlabel#1{\expandafter\@result\expandafter{\the\@result {#1}}\@@litlabel}
+\def\@@@@litlabel#1;{\expandafter\@result\expandafter{\the\@result #1;}\@return}
+
+% predefined edges
+
+\def\tree@edge#1#2{(#1.\pgftree@parentanchor) -- (#2.\pgftree@childanchor)}
+
+\def\roof@edge#1#2{\csname roof@edge@\leveldirection\endcsname{#1}{#2}}
+\def\roof@edge@down#1#2{(#1.south) -- (#2.north west) -- (#2.north east) -- cycle}
+\def\roof@edge@up#1#2{(#1.north) -- (#2.south west) -- (#2.south east) -- cycle}
+\def\roof@edge@left#1#2{(#1.west) -- (#2.north east) -- (#2.south east) -- cycle}
+\def\roof@edge@right#1#2{(#1.east) -- (#2.north west) -- (#2.south west) -- cycle}
+
+%%% Options
+\pgfkeysgetvalue{/tikz/level distance/.@cmd}{\orig@leveldistance}
+\tikzoption{level distance}{\pgfmathsetlength\levelsep{#1}\orig@leveldistance#1\pgfeov}
+\pgfkeysgetvalue{/tikz/sibling distance/.@cmd}{\orig@siblingdistance}
+\tikzoption{sibling distance}{\pgfmathsetlength\subtreesep{#1}\orig@siblingdistance#1\pgfeov} % different semantics
+
+% I don't really like this scheme
+\pgfkeysgetvalue{/tikz/grow/.@cmd}{\orig@grow}
+\tikzoption{grow}{\csname grow@#1\endcsname\orig@grow#1\pgfeov}
+\pgfkeysgetvalue{/tikz/grow'/.@cmd}{\orig@growprime}
+\tikzoption{grow'}{\csname growprime@#1\endcsname\orig@growprime#1\pgfeov}
+\def\grow@up{\def\leveldirection{up}\def\siblingdirection{left}}
+\def\grow@down{\def\leveldirection{down}\def\siblingdirection{right}}
+\def\growprime@up{\def\leveldirection{up}\def\siblingdirection{right}}
+\def\growprime@down{\def\leveldirection{down}\def\siblingdirection{left}}
+\def\grow@left{\def\leveldirection{left}\def\siblingdirection{down}}
+\def\grow@right{\def\leveldirection{right}\def\siblingdirection{up}}
+\def\growprime@left{\def\leveldirection{left}\def\siblingdirection{up}}
+\def\growprime@right{\def\leveldirection{right}\def\siblingdirection{down}}
+
+% defaults appropriate for linguistic trees
+\tikzset{every tree node/.style={anchor=base}}
+\tikzset{every leaf node/.style={}}
+\tikzset{every internal node/.style={}}
+\def\tikz@edge@to@parent@path{\tree@edge{\tikzparentnode}{\tikzchildnode}}
+
+% predefined roof style
+\tikzset{roof/.style={edge from parent path=\roof@edge{\tikzparentnode}{\tikzchildnode}}}
+