\documentclass[12pt]{article}

\usepackage{comment}
\begin{document}

\centerline{Homework 01, MORALLY Due Feb 10}
\newcommand{\implies}{\Rightarrow}

(The last question IS honors HW 01 and graded separatel but handed in
with this HW.) 


\begin{enumerate}

\item
(0 points)
When is the midterm (give date and time)?
If you cannot take the midterm on that day then tell 
Professor Gasarch by Feb 10. 

\bigskip

\newpage

\item
(40 points)
\begin{enumerate}
\item 
(20 points)
Give a Propositional Formula on four variables that has exactly
three satisfying assignments.
Give the satisfying assignments.


\bigskip

\item 
(20 points)
Give a Propositional Formula on four variables that has exactly
13 satisfying assignments.
ADVICE: You could do it in a messy way BUT there is an EASIER way.
Both are full credit, but try to find the easier way. 

\bigskip

\end{enumerate}

\newpage

\item
(30 points)
Recall that a {\it 2CNF} formula is of the form 

$$C_1 \wedge \cdots \wedge C_k$$

where each $C_i$ is an $\vee$ of two literals. 

Recall that  {\it 2SAT} is the following problem: Given a 2CNF formula, determine
if it is satisfiable. 

Recall that I said in class that 2SAT is in P.

\begin{enumerate}
\item
(0 points but you need to do this for Part 2)
Look on the web or ChatGPT or whatever you want for an ALGORITHM that
solves 2SAT in polynomial time.
\item
(30 points) Describe the algorithm in English so that someone who
can't read code can follow it. (You do not need to show that its in polynomial time.) 
\item
(0 points and just for your own benefit and part of a long term extra credit problem) 
Code up the 2SAT algorithm. 
This is used in every SAT algorithm. I may have an extra credit project in this course
where you code up a SAT solver. 
\end{enumerate}


\newpage

\item
(30 points)
Show that, for all $n\ge 1$, there exists a formula on $n$ variables that is satisfied by
exactly $n$ satisfying assignments. Give the satisfying assignments.
(This is NOT by induction. Just give
the Formula. You may use DOT DOT DOT (that is ``$\dots$") though it should be clear what you mean.)

\newpage
\item 
{\bf Honors HW 1} This is graded separately as Honors HW01.

THere are 3 people in a room.

Two are truth tellers.

One is normal (can tell the truth or lie).

They all know about each other. 

Show how by asking them YES-NO questions you can determine which one is the normal. 

\bigskip

\end{enumerate}
\end{document}