\documentclass[12pt]{article}
\begin{document}
\centerline{\bf Untimed Midterm. Morally Due Feb 28, 9:00AM}
\newcommand{\implies}{\Rightarrow}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\NCU}{{\rm NCU}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}
\centerline{\bf WARNING: THIS MIDTERM IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}
\begin{enumerate}
\item
(10 points)
In this problem $L_n$ is the linear order on $n$ points.
In this problem you may assume that,
{\it for all $n$ there is a $k$ such that DUP wins the DUP-SPOILER game with
$L= L_n$ and $L'= \N + \N^*$. (In class we agreed that $k$ was roughly $\log n$.
For this problem it does not matter what $k$ is.)}
(Recall that $\N^*$ is $\N$ backwards $\ldots, 4,3,2,1,0$.
\begin{enumerate}
\item
Give a strategy for Duplicator to win the DUP-SPOILER game with
$L= \N$
$L'= \N+\Z$
Any value of $k$
\item
Give a strategy for Duplicator to win the DUP-SPOILER game with
$L= \Z$
$L'= \Z+\Z$
Any value of $k$.
(You may use the last part in this part.)
\end{enumerate}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(20 points)
In this problem you will write a program that, given $n,m$, outputs a formula on
$n$ variables that has {\it exactly} $m$ satisfying assignments. That is an informal
description which I formalize soon.
You will be outputting boolean formulas in DNF form. We illustrate the format we want with an
examples.
If your formula is
$$(x_1 \wedge x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_7)$$
you output
$$(1,2,n3)(n1,10).$$
The {\it length} of a formula is the sum of the following (and we give
examples from the above formula).
The number of parenthesis: 4.
The number of commas: 3.
The number of $n$'s: 2.
The number of occurences of numbers: 5. This is 1,2,3,1,10. Note that we don't count the 10 as
two characters.
The length of the above formula is $4+3+2+5=14$.
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\begin{enumerate}
\item
(0 points but you need it for the next part)
Write a program that will, on input $n,m$ output one of the following:
\begin{itemize}
\item
If $m=0$ then output the formula $x \vee \neg x$. (Note that this has 0 satisfying assignments.)
\item
If $m\ge 2^n+1$ then output THERE IS NO SUCH FORMULA. (Note that there really is no such formula.)
\item
If $1\le m\le 2^n$ then output a DNF formula on $n$ variables that has exactly $m$ satisfiying assignments.
(There may be many, just output one of them.) Also output the formulas length.
\end{itemize}
\item
(5 points)
Run your program on (2,2), (3,3), (4,4), $\ldots$ (10,10) and plot the graph of $n$ vs. the length
of what you get on input $(n,n)$. Hand in your data and the graph.
\item
(0 points)
Speculate what the function $n$ goes to length of the formula for $(n,n)$ roughly is.
\item
(15 points) Email Emily your code. She will run it on many values so make sure that it is correct.
\end{enumerate}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(20 points)
Let $n\in\N$. $\NCU(n)$ is the least number such that $n$ can be written as the sum
of $\NCU(n)$ cubes. Clearly $\NCU(n)\le n$ since
$$n= 1^3 + \cdots + 1^3.$$
\noindent
It is known that $\NCU(n)\le 9$.
In this problem you will write one programs that will,
given $n\in\N$, find a bound on $\NCU(n)$.
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\begin{enumerate}
\item
(0 points but you need to do this for the next part.)
Write a program that will, given $n$, find, for all $1\le i\le n$, a number $A[i]$
such that $i$ can be written as the sum of $A[i]$ cubes.
\begin{itemize}
\item
$A[0]\leftarrow 0$ (0 can be written as the sum of 0 cubes).
\item
$A[1]\leftarrow 1$ (1 can be written as the sum of 1 cube).
\item
For $i\leftarrow 2$ to $n$
$$A[i]\leftarrow 1+ \min\{A[i-j^3] \colon i-j^3\ge 0\}$$
(We are speculating that if we used $j^3$ there is $i-j^3$ left.)
\end{itemize}
\item
(4 points- 1 points each)
Run the program on $n=1,2,\ldots, 1000$.
\begin{enumerate}
\item
How many required 9 cubes? List them all. (23 should be one of them.)
\item
How many required 9 cubes? List all that are $\le 100$. (50 should be one of them.)
\item
Write 50 as the sum of 8 cubes.
\item
Prove that 50 cannot be written as the sum of 7 cubes.
(You may use that 23 cannot be written as the sum of 8 cubes.)
\end{enumerate}
\item
(16 points) Email your code to Emily. She will run it on many numbers so
make sure it is correct
\end{enumerate}
\end{enumerate}
\end{document}