\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\input{macros-course}


\newif\ifspaceout
\spaceouttrue
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
   \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}


\ifshowsolutions
{
\begin{center}
{\large \bf
Exam 1 Solutions}

October 24, 2000
\end{center}
\else
\begin{center}
{\large \bf
6.042 Exam 1}

October 18, 2000\\
Grading Standards
\end{center}

\fi

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Predicates and Quantifiers}

\begin{problemparts}

\problempart {\bf (5 points)}  $P(4) \wedge R(1,4)$ 

\problempart {\bf (5 points)}  $\exists n \forall m S(n, m)$

\problempart {\bf (5 points)} $\forall n \forall m T(n, m)
\leftrightarrow \neg R(n, m) \wedge \neg R(m, n)$

\problempart {\bf (5 points)} $\forall n Q(n) \leftrightarrow [\forall
m R(0, m) \wedge R(m, n) \wedge S(m, n) \rightarrow T(m, 1)]$

\problempart {\bf (5 points)} $\forall n P(n) \rightarrow [\exists m
R(0, m) \wedge R(1, m) \wedge R(m,n) \wedge S(m,n)]$

\problempart {\bf (5 points)} Yes, using parts (a), (c), (d), and (e).

\bigskip

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Parts (a) through (e):\+\\
-4 points for using the symbols $=$, $|$, $<$, $>$, $\leq$, or $\geq$\\
-3 points for mistranslating but in a way that still defines the same
true property \\
\>(ie, they define part (d) in terms of $\neg T$ instead of $R$)\\
-2 points for a correct translation but with one letter accidentally
misplaced\\\> (ie, an $S$ instead of an $R$)\\
-2 points for the incorrect order (ie, $R(x,1)$ instead of $R(1,x)$).\\
-1 point for forgetting the $\forall$ in parts (c), (d), or (e).\\
-2 points for other quantifier errors.\\
-1 point for each implication direction mistake (ie, using a
 $\leftarrow$ instead of a $\rightarrow$\\ 
\>or a $\rightarrow$ instead of a $\leftrightarrow$)\\
-1 point for leaving out the $R(0,x)$ in parts (d) or (e).\\
\< Part (f):\\
-4 points if they say no, but with a general fact that would be useful.\\
-2 points if they say no, with a general fact that would be useful, but in
fact the way\\\> they translated the other parts, they need it.\\
-2 points for saying yes but forgetting to list part (a) as required.\\
-1 point for saying yes and including part (b) or not including parts\\\> (c),
 (d), or (e): (-1 point per mistake).
\end{tabbing}

\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf{Relations}
\begin{problemparts}

\problempart {\bf (5 points)}  Antisymmetric, Transitive

\problempart {\bf (5 points)}  Partial Order, Total Order

\problempart {\bf (5 points)}  None of These

\problempart {\bf (5 points)}  None of These

\problempart {\bf (5 points)}  Equivalence Relation

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\+\\
 -1 points for each property they circle that should not be circled.\\
 -4 points for not circling the property that should be circled, if there's
only one.\\
 -2 points for not circling a property that should be circled, if there are
two.\\
 -5 points if they didn't circle anything.\\
 -5 points if they circled ``none of these'' and something else.
\end{tabbing}


\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{15} \textbf{Directed Graphs}

\begin{problemparts}

\problempart{\bf (5 points)} The claim is true.

In a tournament graph on 4 nodes, every node will have an odd number
of edges, so the degree of every node is odd.  By the theorem from 
class, it won't have an Euler circuit.

\problempart{\bf (5 points)} The claim is false.

An example is the graph on five nodes $a, b, c, d, e$ where there are
edges are $(a,b),\, (b,c),\, (c,d),$ $(d,e),\, (e,a),\, (a,c),\,(c,e),\,
(e,b),\, (b,d),\,(d,a).$  The edges in this order give an Euler circuit.

\problempart{\bf (5 points)} The claim is false.

The complete graph on 225 nodes has an Euler circuit, since every node
has degree 224, which is even.  Since an Euler circuit contains every
edge, all we have to do to construct a 225-node tournament graph with
an Euler circuit is take the Euler circuit on $K_{225}$ and choose a
direction, then include every edge in our 225-node tournament graph in
the direction it appears in the Euler circuit.  This will be a
tournament graph, since every two nodes are connected and every edge
is directed.

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\+\\
-5 if they don't answer yes/no or true/false, or if they answer wrong.\\
-4 if they answer correctly but give no justification.\\
-3 if they answer correctly but give incorrect justification.\\
-2 if they answer correctly but give incomplete justification.\\
-1 if they answer correctly and give a graph for justification but
 they give no\\
\> explaination that it works: They could show the Euler circuit, or
they could say\\
\> that all nodes have equal in degree and out degree.  Just a graph
is insufficient.\\
-1 if they answer correctly but miss a minor point in their justification.\\
\end{tabbing}



\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{8} \textbf{Structured Reasoning}

4.1.1:  Existential Generalization, from 4.1.

4.1.2:  Addition, from 4.1.1.

4.3:  Proof by cases from 3, 4.1.2, and 4.2.2.

5:  Universal Generalization, from 1 and 4.

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Each of the blanks is worth 2 points.\+\\
-1 if they get the reason wrong \\
-1 if they don't list the right statements the deduction relies on.\\
\>  On step 5, DO take off a point if they only miss the ``1''.  It's
necessary that \\
\>  the $x_0$ be arbitrary to perform a UG.\\
\>  On step 4.1.2, don't take off a point if they say ``Law of Domination''
instead of \\
\> addition.  If they say something general like ``rules of predicate logic,''
this is okay,\\
\> but if they list an incorrect rule, it's not.
\end{tabbing}




\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{32} \textbf{Proof Comprehension}

For this question, if they explain what's wrong with a proof but never
say it's invalid, that's fine as long as their explanation makes it
clear they think it's invalid.  If they seem wishy-washy about it,
give no credit for saying it's valid or invalid correctly: only give
partial credit on the explanation.

If they say a proof is valid and explain why they think so this can be
used as partial credit.  

\begin{problemparts}

\problempart {\bf (8 points)} This proof, obviously, is invalid.  The
theorem assumes $P$ and proves TRUE; this is a fallacious argument,
since $P$ could be false yet $P \rightarrow $TRUE could still be true.

\begin{tabbing}
XXX\=\kill
Validity/Invalidity:\\
\>4 points for saying it is invalid.\\
Explanation:\\
\>4 points for calling this the fallacy of affirming the conclusion\\
\>4 points for calling this the converse fallacy\\
\>4 points for saying something like ``Proving $P \rightarrow $TRUE doesn't
prove $P$.''\\
\>3 points for saying that differentiating can't be reversed.\\
\>0 points for anything else, especially if they claim we divided by 0.
\end{tabbing}

\problempart {\bf (8 points)} The proof is invalid.  Induction generalizes
over the natural numbers, not over the rationals.

\begin{tabbing}
XXX\=XXX\=\kill
Validity/Invalidity:\\
\>4 points for saying it is invalid.\\
Explanation:\\
\>4 points for talking about induction not applying to the rationals.\\
\>2 points for having this idea but being inept about expressing it.\\
\>-1 point for getting the right reason but giving other ``reasons'' which
are\\
\>\>incorrect (for each other reason).
\end{tabbing}

\nextproblem

\problempart {\bf (8 points)} This proof is valid.  If they say it is
invalid they may get *some* partial credit...

\begin{tabbing}
XXX\=XXX\=\kill
Validity/Invalidity:\\
\>8 points for saying it is valid.\\
Explanation:\\
\>2 points for saying it is invalid and mentioning minor points the theorem leaves out, such as:\\
\>\> - Proving the weight of a spanning tree is an integer\\
\>\> - Proving the well-ordering property of the natural numbers\\
\>2 points for any other reasonable nitpick.\\
\>0 points for saying it can't be valid because it's not formal.
\end{tabbing}


\problempart {\bf (8 points)} This proof is invalid.  It would be
valid if the assumption that the set $S$ is finite was not omitted.
As it is, there is no contradiction, since $k$ is not necessarily 
a number.

\begin{tabbing}
XXX\=XXX\=\kill
Validity/Invalidity:\\
\>4 points for saying it is invalid.\\
Explanation:\\
\>4 points for saying anything to the effect of: we need to assume
that $S$ is finite.\\
\>4 points for arguing there is no contradiction since $k$ is not
necessarily a number.\\
\>2 points for arguing they didn't prove $k$ was prime.\\
Other:\\
\>6 points if they say it is valid and that the assumption that $S$ is
finite is implicit. \\
\>4 points if they say it is valid and that it's just like the proof
we gave in lecture.
\end{tabbing}

\end{problemparts}

\nextproblem
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{30} \textbf{Hamiltonian Circuits}
\begin{problemparts}

\problempart {\bf (4 points)} A 4 by 4 grid graph looks like it has 9
cells, not 16.  The labeled points should be the middle two on the top
row [$(1,3)$ and $(2,3)$] and the point below the further of these to
the right [(2,2)].

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\+\\
-3 points for drawing a 5 by 5 grid graph but labeling the points
correctly\\  \>(in a 5 by 5 graph, these points would be internal).\\
-4 points for drawing a 5 by 5 grid graph and labeling the points on
the outside.\\
-1 point if they label points as if the bottom left were $(1,1)$ instead
of $(0,0)$.\\
-1 point if they don't orient the graph in the standard way.  The bottom
left should\\
\> be $(0,0)$ and the points should be on the top.  If they are
oriented \\
\> consistenly but not in this manner, apply this penalty.\\
-1 point for each vertex they label incorrectly.\\
-1 point if they label any of the vertices ambiguously enough that you 
really can't\\
\> tell if they got the label right.
\end{tabbing}


\problempart {\bf (10 points)} 

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Use normal proof standards.  The following is the breakdown of important
points they must cover:\+\\
1 point: proving that 1 color would not suffice\\
6 points: providing a 2-coloring of the $m$ by $n$ grid graph\\
3 points: explaining why their 2-coloring is valid.\-\\
If they give a good picture that in your opinion makes it clear why
the 2-coloring\\ 
would work for any size grid graph, give them credit for explaining
correctly.\\
However, if they draw a picture without being clear about the pattern,
this is insufficient.\\
Also, if they don't draw a general $m$ by $n$ picture but rather give
an example,\\
some explanation is needed to back this up.
\end{tabbing}

\nextproblem

\problempart {\bf (16 points)} Give 0 points partial credit for ANY
argument that doesn't resemble induction. If they set up their
argument as an inductive one (ie, base case and inductive step) but in
their inductive step they don't call on the inductive assumption but
just prove $P(n+1)$ directly, give them 6 points off: this is actually
induction but it's not a proof in the spirit of induction (if someone
does this, just use normal proof standards for the grading instead of
what is listed below).

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Use normal proof standards.  The following is the breakdown of important
points they must cover:\+\\
2 points for setting up their proposition correctly (even if they're
not explicit about this).\\
4 points for the base case: they should give a *little* explanation,
not just draw a graph\\
\> (though a directed version of the 2x2 grid graph would suffice.)\\
2 points for breaking down the $2(n+1)$ by $2(n+1)$ grid graph into
a\\
\> $2n$ by $2n$ grid graph plus some remaining area.\\
6 points for giving a Hamiltonian circuit based on the circuit in the
$2n$ by $2n$ graph. \\
2 points for correctly dealing with any issues about the {\em
direction}\\
\> to follow the smaller circuit in.
\end{tabbing}

\nextproblem

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{40} \textbf{State Machines and Invariants}
\begin{problemparts}

\problempart {\bf (10 points)}  

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
The following is a breakdown of the points:\+\\
 4 points for the set of states.  States {\em must} include $m$, $i$,
and $List$.\\
 2 points for the start state.\\
 4 points for the transitions.  Take off 1 point if they never mention
about what\\\> happens if $m=1$.
\end{tabbing}

\problempart {\bf (10 points)}  

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Use normal proof standards.  The following is a breakdown of the points:\+\\
3 points for giving a correct invariant and clearly stating it.\\
1 point for the base case.\\
2 points for correctly arguing each of the two types of transitions.\\
2 points for arguing that if $m=1$ the list is a factorization of $n$.
\end{tabbing}

\problempart {\bf (10 points)}  

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Use normal proof standards.  The following is a breakdown of the points:\+\\
3 points for giving a correct invariant and clearly stating it.\\
1 point for the base case.\\
2 points for correctly arguing each of the two types of transitions.\\
2 points for arguing that if $m=1$ the list is a factorization of $n$.
\end{tabbing}

This problem is a little more tricky.  They will probably need to give
a stronger invariant than that the list never contains any non-prime
numbers, because proving that $i$ is prime when we insert it requires
some more information.  If they deal with this point by arguing it
loosely in the case where $i$ is added to the list, and don't
strengthen their invariant, give them a maximum of 2 points on their
invariant and 1 point on that case (so the total penalty is 2 points).

\nextproblem

\problempart {\bf (10 points)} Prove that this algorithm always
terminates.  

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\\
Use normal proof standards.\\
If they use the termination theorem, take off:\+\\
1 point if their function isn't always $\geq 0$.\\
1 point if they never argue $m$ is always an integer (which will
probably\\
\> be necessary to prove their termination function is an integer\\
6 points if they never argue why their termination function is always
$\geq 0$,\\\> but they state it.\\
\end{tabbing}

\nextproblem


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%   PROBLEM 8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{20}  Bags and Stacks

\problempart{\bf (10 points)}

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\+\\
5 points for saying yes.\\
5 points for the abstraction relation.
\end{tabbing}

For this problem, it is okay for them to define the abstraction
relation loosely as long as they define the important part well (ie,
the part that associates the sequence to the multiset.


\problempart{\bf (10 points)} 

\begin{tabbing}
XXX\=XXX\=\kill
Grading:\+\\
5 points for saying no.\\
4 points for giving a sequence of inputs for a correct trace.\\
1 points for providing the outputs of the trace.
\end{tabbing}











\end{problems}

\end{document}
