\documentclass{article}
\usepackage{hevea}
\thispagestyle{empty}

\begin{document}

\begin{center}
{\bf Checklist of all the things you've learned in CS 3100, Fall 2010}\\
Also a small Mapping Reduction proof at the end\\
Handed out 12/9/10
\end{center}

\noindent{\bf Final Exam:} The final exam will have 
closed-book multiple-choice short questions
on all these topics below, for 50 minutes. Then after a 5-minute
break, you'll be given a 60-minute long
open-book exam on all the bold-faced
topics plus the mapping reduction proof at the end (or small
variants of this mapping reduction).

\begin{list}{[\ ]}{\addtolength{\itemsep}{-1.05\itemsep}}
\item {\bf Designing simple FAs and Reg Exps}
\item Identify strings in a given Reg Exp
\item Basic notions about sets and strings (Powerset etc)
\item FA, Reg Exp conversions
\item DFA to Reg Exp conversion
\item {\bf DFA minimization} (studied much later)
\item FA operations (intersection, reversal, etc), and
  whether closure is guaranteed
\item Why some languages are not regular; Pumping lemma
\item {\bf Alternate characterization of
  regularity: Ultimate periodicity}
  and ``lasso shapes'' for minimal DFA (studied much later)
  over a singleton alphabet
\item Midterm examined the above, esp. exp growth of
  NFA/DFA conversion, etc. 
\item Flex experiments
\item PDA design using JFLAP; NPDA, DPDA
\item What JFLAP helps you do: freeze configurations,
  watch non-determinism evolve, Pumping Lemma tutor,
  conversions from DFA to RE, etc.
\item {\bf Designing simple CFGs}
\item CFG consistency, completeness, simplification
\item Pumping Lemma for CFLs
\item Why certain CFLs are not closed under complementation
\item Parsing using dynamic programming using
  the Chomsky normal form of a CFG (the table filling idea)
\item CFG to PDA and back
\item The Chomsky normal form; why it guarantees
  certain derivation lengths
\item General story of pumping: not an iff theorem
\item Yacc based design of calculator
\item Linearity of CFGs, and what it means
\item PDA and CFG operations (union, intersection, etc.) and
  whether closure is guaranteed
\item The LBA classification (briefly) and context
  sensitive languages
\item {\bf 
    Designing simple Turing machines (DTM, NDTM, multi-tape TM).}
\item Language classifications: RE, Recursive, etc. and what
  it means
\item Basic results: Universality of CFGs being undecidable;
  emptiness being decidable; status of grammar equivalence
  (decidable or not)
\item Printer TM and decider TM, conversions
\item Self referential statements, self-denying TMs   $S_{TM}$
  being undecidable
\item Favorite sets : $A_{TM}$ etc. and status of decidability
\item Diagonalization. Use in cardinality comparison
\item Notion of onto and into functions
\item {\bf Schr\"{o}der-Bernstein Theorem and its uses to compare
  cardinalities}
\item Cardinality based arguments to show there are non-RE languages
\item Proof of undecidability of the Halting problem. Two 
  approaches: diagonalization proof, and proof based on
  $S_{TM}$.
\item {\bf Time-complexity classes NP, P, NPC. What a 
    non-deterministic algorithm is.}
\item Mapping reductions: what they are.
\item Mapping reductions for showing undecidability
\item {\bf Mapping reductions for showing NP-completeness: the
  SAT to Clique reduction.}
\item {\bf BDDs for simple Boolean functions.}
\item BDDs as minimal DFA
\item BDDs used to express Logic
\item BDDs to synthesize circuits using multiplexors
\item How many Boolean functions over N inputs
\item How to use a 4-to-1 mux to implement all possible
  2-input Boolean functions
\item Variable ordering
\item What it means for a problem to be NP-complete
\item {\bf How Regular, DCFL, CFL, CSL, NPC, Decidable, 
    RE, non-RE are contained.}
\end{list}

\noindent{\bf Show that $EQ_{TM}$ is not RE}. 

\noindent{\bf Proof:} Build two 
machines $M_1$ which always rejects and $M_2$ which accepts any $x$
so long as $M$ accepts $w$. Then we have achieved 
$A_{TM}\leq_m \overline{EQ_{TM}}$. This means
$\overline{A_{TM}}\leq_m EQ_{TM}$. Thus, $EQ_{TM}$ can't be RE (else
we will have an enumerator for $\overline{A_{TM}}$. 

%\noindent {\bf Also try:}
%See what happens if you build $M_1$ to always accept? What
%mapping reduction do you get?


\end{document}

