\documentclass[10pt]{article}

\usepackage{hevea}

\oddsidemargin 0cm
\textwidth 17cm

\begin{document}


\begin{center}
{\large\bf CS 3100 -- Models of Computation -- Fall 2011}  
\end{center}

\footnotesize

\ahref{http://www.eng.utah.edu/\home{cs3100}/grades2011.html}{\large\bf Grade Lookup}

\ahref{FAQ.txt}{\large\bf Frequently Asked Questions (FAQ) and their answers}

\section{Reference Materials}
% {\bf Required Textbook:} ``Introducing the Theory of Computation,'' by Wayne Goddard, Jones and Bartlett, 2008

The course is based on my lecture notes.
%
You will also find an excellent set of notes courtesy of Dr. Konrad Slind 
at \ahrefurl{http://www.eng.utah.edu/\home{cs3100}/KonradNotes.pdf} that gives
crystal-clear explanations of many theoretical concepts.

\section{General Course Info}
\begin{footnotesize}
%
\begin{itemize}
\item {\bf Email Subscription:}
 Please send your
 name and preferred email address to 
 {\tt teach-cs3100@eng.utah.edu}.
\item {\bf Class Website:} \ahrefurl{http://www.eng.utah.edu/\home{cs3100}}
\item {\bf Class Room:} WEB L 101
\item {\bf Lecture Hours:}   TH 10:45 to 12:05
\item {\bf Instructor:}  {\bf Ganesh Gopalakrishnan}
\item {\bf Instructor Email:} teach-cs3100@list.eng.utah.edu
\item {\bf Instructor Office Hours:} Mon : 11:00am to 12:15pm 
                                     and Tue : 12:30pm to 2:00pm
\item {\bf Instructor Office Location:} 3428 MEB
\item {\bf TA Emails:} teach-cs3100@list.eng.utah.edu
\item {\LARGE\bf TA Office Location:} 3419 MEB
\item {\bf TA Office Hours:} 
  \begin{itemize}
  \item {\sl TA1:}
    \begin{itemize}
    \item Peng Lee (``Peter''), \verb|peterlee@cs.utah.edu|
    \item Office Hours: Mon 9:30-10:45 and Wed 9:30-11:00
    \end{itemize}
  \item {\sl TA2:}
    \begin{itemize}
    \item Akram Daruki (``Samira''), \verb|akram.daruki@utah.edu|
    \item Office Hours: 9:15-10:30 on Thu and 2:15-3:45 on Fri (beginning 9/9/11)
    \end{itemize}
  \end{itemize}


\end{itemize}
%
\end{footnotesize}




%\ahref{faq/faq.html}{(faq URL)} -- \ahref{faq/faq.pdf}{(faq.pdf)} 


\section{HANDOUTS AND WEEKLY SCHEDULE}
\label{sec:weekly-schedule}

\begin{itemize}

\item Week1
  \begin{itemize}
	\item 8/23   L1: Introduction to the course
-- \ahref{lectures/l1/notes1.pdf}{notes1[.pdf]} 
\ahref{lectures/l1/notes1.tex}{[.tex]} 
-- \ahref{lectures/l1/asg1.pdf}{asg1[.pdf]}
\ahref{lectures/l1/asg1.tex}{[.tex]}
-- \ahref{lectures/l1/asg1soln.pdf}{asg1soln[.pdf]}
\ahref{lectures/l1/asg1soln.tex}{[.tex]}
-- \ahref{lectures/l1/l1slides.pdf}{l1slides[.pdf]}
\ahref{lectures/l1/l1slides.tex}{[.tex]}
-- \ahref{lectures/l1/TerminalSessionL1.txt}{TerminalSessionL1.txt}

        \item 8/25    L2: Functional Programming in Python + {\bf Strings, Languages}
-- \ahref{lectures/l2/notes2.pdf}{notes2[.pdf]} 
\ahref{lectures/l2/notes2.tex}{[.tex]} 
-- \ahref{lectures/l2/l2slides.pdf}{l2slides[.pdf]}
\ahref{lectures/l2/l2slides.tex}{[.tex]}
  \end{itemize}

	
\item Week2
   \begin{itemize}
 	\item 8/30   L3: Language, DFAs
-- \ahref{lectures/l3/asg2.pdf}{asg2[.pdf]}
\ahref{lectures/l3/asg2.tex}{[.tex]}
-- \ahref{lectures/l3/asg2soln.pdf}{asg2soln[.pdf]}
\ahref{lectures/l3/asg2soln.tex}{[.tex]}
-- \ahref{lectures/l3/notes3.pdf}{notes3[.pdf]} 
\ahref{lectures/l3/notes3.tex}{[.tex]} 
-- \ahref{lectures/l3/network-flow-regexp-article.pdf}{network-flow-regexp-article.pdf}
-- \ahref{lectures/l3/TerminalSessionL3.txt}{TerminalSessionL3.txt}

 	\item 9/1    L4: More DFAs
        \end{itemize}    

\item Week3
   \begin{itemize}
 	\item 9/6   L5: More DFA
-- \ahref{lectures/l6/asg3.pdf}{asg3[.pdf]}
\ahref{lectures/l6/asg3.tex}{[.tex]}
-- \ahref{lectures/l6/asg3soln.pdf}{asg3soln[.pdf]}
\ahref{lectures/l6/asg3soln.tex}{[.tex]}
-- \ahref{lectures/l5/notes5.pdf}{notes5[.pdf]} 
\ahref{lectures/l5/notes5.tex}{[.tex]} 

 	\item 9/8    L6: More DFA, and basics of NFA and Regular Expressions.
   \end{itemize}    


\item Week4
   \begin{itemize}
 	\item 9/13   L7: Notes on NFA
-- \ahref{lectures/l7/notes7.pdf}{notes7[.pdf]}
\ahref{lectures/l7/notes7.tex}{[.tex]}

 	\item 9/8    L8\ahref{lectures/l12/asg6soln.pdf}{:} Assignment 4 posted
-- \ahref{lectures/l8/asg4.pdf}{asg4[.pdf]}
\ahref{lectures/l8/asg4.tex}{[.tex]}
-- \ahref{lectures/l8/asg4soln.pdf}{asg4soln[.pdf]}
\ahref{lectures/l8/asg4soln.tex}{[.tex]}
   \end{itemize}    


\item Week5
   \begin{itemize}
 	\item 9/20   L9: Kleene-star of NFA
-- \ahref{lectures/l9/notes9.pdf}{notes9[.pdf]}
\ahref{lectures/l9/notes9.tex}{[.tex]}

 	\item 9/22   L10:  Assignment 5 posted
-- \ahref{lectures/l10/asg5.pdf}{asg5[.pdf]}
\ahref{lectures/l10/asg5.tex}{[.tex]}
-- \ahref{lectures/l10/asg5soln.pdf}{asg5soln[.pdf]}
\ahref{lectures/l10/asg5soln.tex}{[.tex]} 
   \end{itemize}

\item Week6
   \begin{itemize}
 	\item 9/27   L11:
Arrears from previous lecture notes (union, intersection, etc.).
          {\bf Also see notes now.}
-- \ahref{lectures/l11/notes11merged.pdf}{notes11[.pdf]}

 	\item 9/29   L12:
Assignment 6 posted. 
-- \ahref{lectures/l12/asg6.pdf}{asg6[.pdf]}
\ahref{lectures/l12/asg6.tex}{[.tex]}
   \end{itemize}

\item Week7
   \begin{itemize}
 	\item 10/4  L13: 
          Discussed sample problems
-- \ahref{lectures/l13/notes13.pdf}{notes13[.pdf]}
-- \ahref{lectures/l13/notes13.tex}{[.tex]}

 	\item 10/6   L14: Midterm-1, in class. 
      \ahref{lectures/l14/midterm1soln.pdf}{SOLUTIONS}.
          

        \item \ahref{lectures/l14/asg7.pdf}{[{\bf asg7.pdf}]} \ahref{lectures/l14/asg7.tex}{[{\bf .tex}]}
        \item \ahref{lectures/l14/ply-3.4}{ply-3.4 directory. You'll find
  calc.py in this tree under examples}
   \end{itemize}    

\item  \ahref{lectures/l15/asg7-L.tar.gz}{{\bf asg7-L.tar.gz}}

\item Week8

   \begin{itemize}
 	\item 10/18  L15: 
          \begin{itemize}
          \item Pumping Lemma for regular languages.
          \item Practice problems
          \item Begin reading: 
            \begin{itemize}
            \item Material on the Pumping Lemma
            \ahref{lectures/l15/notes15a.pdf}{[notes15a.pdf]}
            \item Material on Context-Free Languages
              and Context-Free Grammars. 
              \ahref{lectures/l15/notes15.pdf}{[notes15.pdf]}
            \end{itemize}
 	\item   pyc.tar.gz:
          \ahref{lectures/l15/pyc.tar.gz}{pyc.tar.gz}
 	\item    pyc-mac.tar.gz: \ahref{lectures/l15/pyc-mac.tar.gz}{pyc-mac.tar.gz}
          \end{itemize}

 	\item 10/20: L16: \ahref{lectures/l16/asg8.pdf}{[{\bf MORE NOTES + asg8.pdf}]} 
           \ahref{lectures/l16/asg8.tex}{[{\bf .tex}]} covering
           the Pumping Lemma.
           \begin{itemize}
           \item Notes on the Pumping Lemma (excerpts from my book)
             are \ahref{lectures/l16/plchapter.pdf}{HERE}.
           \end{itemize}
         \item  \ahref{lectures/l16/asg8soln.pdf}{[{\bf asg8soln.pdf}]} 
           \ahref{lectures/l16/asg8soln.tex}{[{\bf .tex}]}.
   \end{itemize}    

\item Week9
   \begin{itemize}
 	\item 10/25  L17: Refer back to notes15.pdf. I've kept many illustrations of concepts online.
          Here are the files:
          \begin{itemize}
          \item \ahref{lectures/l17/lexerex.py}{Example of Lexer - lexerex.py}
          \item \ahref{lectures/l17/calc.py}{Example of an integer calculator - calc.py}
          \item \ahref{lectures/l17/fcalc.py}{Changed integer calculator to deal with floats (now broken too; can't do ints!!) - fcalc.py}
          \item \ahref{lectures/l17/brokencalc.py}{Broke the precedence/associativity - brokencalc.py}
          \item \ahref{lectures/l17/fix1brokencalc.py}{Fixing using Yacc specification of associativity/precedece - fix1brokencalc.py}
          \item \ahref{lectures/l17/fix2brokencalc.py}{Fixing by layering the grammar - fix2brokencalc.py}
          \end{itemize}
 	\item 10/27  L18: Introduce PDAs.
          \begin{itemize}
          \item \ahref{lectures/l18/pda-notes.pdf}{Notes on Push-down Automata}
          \item \ahref{lectures/l18/notes18.pdf}{Lecture notes 18 [.pdf]}\ahref{lectures/l18/notes18.tex}{[.tex]}
            \item Some JFLAP files kept for your convenience:
            \begin{itemize}
            \item \ahref{lectures/l18/aEQbORbEQcCFG.jff}{aEQbORbEQcCFG.jff: the CFG for the language aEQbORbEQc}
            \item \ahref{lectures/l18/aEQbORbEQcWRong.jff}{aEQbORbEQcWRong.jff: Incorrect PDA for this language}
            \item \ahref{lectures/l18/aEQbORbEQcFixed.jff}{aEQbORbEQcFixed.jff: Corrected PDA for this language}

            \item \ahref{lectures/l18/CFG2PDAONaEQbORbEQc.jff}{CFG2PDAONaEQbORbEQc.jff: Converting the CFG of this language to a PDA}
            \end{itemize}
          \end{itemize}
   \end{itemize}    

\item Week10
   \begin{itemize}
 	\item 11/1  L19: {\bf Asg-7 is due.}
            \begin{itemize}
            \item \ahref{lectures/l19/notes19.pdf}{notes19.pdf}
            \end{itemize}
          
 	\item 11/3  L20: Assignment on PDAs, CFGs, and conversions. Project proposal. Quiz.
            \begin{itemize}
            \item \ahref{lectures/l20/asg9.pdf}{asg9.pdf}
            \item \ahref{lectures/l20/asg9soln.pdf}{\bf asg9soln.pdf}
            \item \ahref{lectures/l20/project-proposal.pdf}{project-proposal.pdf}
            \end{itemize}
   \end{itemize}    

\item Week11
   \begin{itemize}
 	\item 11/8  L21: DTMs, NDTMs
          \begin{itemize}
            \item \ahref{lectures/l21/notes21.pdf}{notes21.pdf}
            \item \ahref{lectures/l21/pcpnotes.pdf}{pcpnotes.pdf}
            \item \ahref{lectures/l21/w_pound_w.TM.jff}{DTM in JFLAP format for w\_pound\_w}
            \item \ahref{lectures/l21/ww_ndtm.TM.jff}{NDTM in JFLAP format for ww\_ndtm}
            \item \ahref{lectures/l21/ling_zhao_ualberta_PCP_solver.tar.gz}{Ling Zhao's PCP Solver from Univ of Alberta, 2003}
            \item \ahref{lectures/l21/bdd-notes-ganesh-cs3100.pdf}{Notes on BDDs, including solving Lewis Carroll's Puzzles}
          \end{itemize}

 	\item 11/10 L22: 
          \begin{itemize}
          \item \ahref{lectures/l22/notes22.pdf}{notes22.pdf}
          \item \ahref{lectures/l22/practice-mt2.pdf}{practice-mt2.pdf}
          \end{itemize}
   \end{itemize}    

\item Week12
   \begin{itemize}
 	\item 11/15 L23: Review for the second midterm.
 	\item 11/17 L24: Second Midterm Exam solutions are 
          \ahref{lectures/l24/midterm2-soln.pdf}{HERE}
   \end{itemize}    

\item Week13
   \begin{itemize}
 	\item 11/22 L25: 
          \begin{itemize}
          \item \ahref{lectures/l25/notes25.pdf}{notes25.pdf}
          \item \ahref{lectures/l25/asg10.pdf}{asg10.pdf}
          \item \ahref{lectures/l25/asg10soln.pdf}{\bf asg10soln.pdf}
          \end{itemize}
 	\item 11/24 No Class - Thanksgiving.
   \end{itemize}    

\item Week14
   \begin{itemize}
 	\item 11/29 L26:
          \begin{itemize}
          \item \ahref{lectures/l26/notes26.pdf}{notes26.pdf}
          \item \ahref{lectures/l26/tylers.tar.gz}{Tyler's BDD Package in Python (tgz)}
          \item \ahref{lectures/l26/DFA-to-predict-epileptic-seizures.pdf}{DFA to predict epileptic seizures.pdf} 
          \end{itemize}

 	\item 12/1  L27:
          \begin{itemize}
          \item \ahref{lectures/l27/asg11.pdf}{asg11.pdf}
          \item \ahref{lectures/l27/asg11soln.pdf}{\bf asg11soln.pdf}
          \item \ahref{lectures/l27/notes27.pdf}{notes27.pdf}
          \item \ahref{lectures/l27/bddchapter.pdf}{bddchapter.pdf}
          \item \ahref{lectures/l21/bdd-notes-ganesh-cs3100.pdf}{Notes on BDDs, including solving Lewis Carroll's Puzzles}
          \end{itemize}

   \end{itemize}    

\item Week15
   \begin{itemize}
 	\item 12/6 L28: Refer to the BDD notes posted under L27.

 	\item 12/8 L29: 
          \begin{itemize}
          \item \ahref{lectures/l29/practice-finals.pdf}{practice-finals.pdf}
          \item \ahref{lectures/l29/FINALS-key.pdf}{The final exam with answer-sketches.}
          \end{itemize}
   \end{itemize}    


 	
% \item Week3
%   \begin{itemize}
% 	\item 9/7     L5: Ch4, NFAs, NFA to DFA conversion
% -- \ahref{notes5/notes5.pdf}{notes5.pdf} 
% -- \ahref{notes5/notes5.tex}{notes5.tex} 
% -- \ahref{notes5/Ch4Slides.pdf}{Ch4Slides.pdf} 
% 
% 	\item 9/9     L6: Ch4, More exercises, in particular notes5.pdf in detail.
%           I'll also work out a problem similar to Asg3.
% -- \ahref{asg3/asg3.pdf}{asg3.pdf}
% -- \ahref{asg3/asg3soln.pdf}{asg3's Solution .pdf}
%         \end{itemize}
% 	
% \item Week4
%   \begin{itemize}
% 	\item 9/14    L7: Discussion of why $\{a^n b^n \}$ is not regular.
%           Show it using distinguishable strings. Also discuss it using the
%           Pumping Lemma. 
% %-- \ahref{asg1/asg1.pdf}{asg1.pdf} 
% %- \ahref{notes1/notes1.pdf}{notes1.pdf} 
% -- \ahref{notes7/Ch5Slides.pdf}{Ch5Slides.pdf} 
% 
% 	\item 9/16    L8: Discuss Asg3  -- TA(s). The TA will demonstrate JFLAP and its
%           features in detail to help you do Asg3.
% 
% -- \ahref{notes8/midterm1-practice.pdf}{Midterm-1 Practice} 
% -- \ahref{notes8/midterm1-practice-slides.pptx}{Midterm-1 Practice Slides (PPTX)} 
% -- \ahref{notes8/midterm1-practice-slides.pdf}{Midterm-1 Practice Slides (PDF)} 
% 
%         \end{itemize}
% 	
% \item Week5
%   \begin{itemize}
% 	\item 9/21    L9:  Slack, review for midterm exam \#1 
% 	\item 9/23    L10: MIDTERM EXAM \#1
% -- \ahref{notes10/midterm1-solution.pdf}{mt1soln}
%           
%         \end{itemize}
% 	
% \item Week6
%   \begin{itemize}
% 	\item 9/28    L11: Application of FA,
%           Ch 6, Context-free Grammars
% -- \ahref{asg4/asg4.pdf}{asg4.pdf}
% -- \ahref{asg4/asg4soln.pdf}{asg4's Solution .pdf}
% -- \ahref{notes11/notes11.pdf}{Notes for L11}
% 
% 	\item 9/30    L12: Ch 6, Context-free Grammars
%          
% 
%         \end{itemize}
% 	
% \item Week7
%   \begin{itemize}
% 	\item 10/5    L13: Ch 7, Push-down automata
% -- \ahref{asg5/asg5.pdf}{asg5.pdf}
% -- \ahref{asg5/asg5soln.pdf}{asg5soln.pdf}
% 
% 	\item 10/7    L14: Ch 8, Grammars and equivalence
% -- \ahref{cs3100Excerpts.pdf}{Ganesh's book}
% -- \ahref{KonradNotes.pdf}{DrSlindNotes}
% -- \ahref{asg5/JFLAPFiles/}{JFLAP examples illustrated in class}
%         \end{itemize}
% 	
% \item Week8
%   \begin{itemize}
% 	\item 10/19   L15: 
% -- \ahref{notes15/notes15.pdf}{notes15.pdf}
% -- \ahref{asg6/asg6.pdf}{asg6.pdf}
% -- \ahref{asg6/asg6soln.pdf}{asg6soln.pdf}
% -- \ahref{asg6/asg6lex.l}{asg6lex.l}
% -- \ahref{asg6/asg6yacc-buggy.y}{asg6yacc-buggy.y}
% -- \ahref{asg6/fullcalc.y}{fullcalc.y}
%           \begin{itemize}
%           \item Ch 8: Review PDA to CFG on a simple example
%           \item Ganesh's book: Ch 13.3:
%             CFG Ambiguity shown on if-then-else and ``equal a's and b's.''
%           \item Ganesh's book: Ch 13.4.2:
%             CFL simplification
%           \item Ganesh's book: Ch 13.6:
%             Reversal, left and right linearity
%             \begin{itemize}
%             \item Linearity
%             \item CFLs being closed under reversal
%             \end{itemize}
%           \item 
%             \ahref{http://dinosaur.compilertools.net/yacc/index.html}
%             {Simple usage of Lex and Yacc to build a calculator}
%           \end{itemize}
% 
% 
% 	\item 10/21   L16: 
%           \begin{itemize}
%           \item \ahref{http://dinosaur.compilertools.net/yacc/index.html}
%             {Lex/Yacc continued}
%           \item Ch 9: Conversion to the Chomsky Normal Form
%           \item Ch 9: Pumping Lemma for CFLs
%           \item TMs for your experimentation
%             \begin{itemize}
%               \item \ahref{notes16/w_pound_w.TM.jff}{A deterministic TM for w\#w, in JFLAP} --
%                 \ahref{notes16/w_pound_w.TM.pdf}{in PDF}
%               \item \ahref{notes16/ww_ndtm.TM.jff}{A non-deterministic TM for ww, in JFLAP} --
%                 \ahref{notes16/ww_ndtm.TM.pdf}{in PDF}
%             \end{itemize}
%           \item \ahref{notes16/computability.pdf}{Slides on Computability [.pdf]} --  \ahref{notes16/computability.ppt}{[.ppt]}
%           \end{itemize}
% 
%         \end{itemize}
% 	
% \item Week9
%   \begin{itemize}
% 	\item 10/26   L17 (from Chapter 12)
%         \item {\bf Midterm-2 will include portions since Midterm-1 up to and including material
%             in Assignment 7. All facts mentioned in various lectures are also included.}
%         \item \ahref{asg7/asg7.pdf}{asg7.pdf}
%         \item \ahref{asg7/asg7soln.pdf}{\large\bf asg7soln.pdf}
%         \item \ahref{notes17/notes17.pdf}{notes17.pdf}
%           \begin{itemize}
%           \item Pumping Lemma for CFLs (review)
%           \item PDA to CFG conversion (review)
%           \item TM construction (review)
%           \item Encoding a TM as a string
%           \item Encoding a TM and an input as a string
%           \item Encoding a CFG as a string
%           \item The language of a TM (a TM can partially read its input!)
%           \end{itemize}
% 
% 	\item 10/28   L18 (from Chapter 13)
%           \begin{itemize}
%           \item {\em Do ask me questions on Asg7}
%           \item Recursively Enumerable Sets 
%           \item Recursive Sets 
%           \item The ability to enumerate and recognize 
%             various languages pertaining to REs, CFGs, and TMs
%           \item A printer TM
%           \item Equivalence of a printer and a regular TM
%           \end{itemize}
%         \end{itemize}
% 	
% \item Week10
%   \begin{itemize}
% 	\item 11/2    L19 
%           \begin{itemize}
% \item 13.1 - RE and recursive, Printer TM == RE (top of page 133)
% \item 13.2 - Encoding notation, 13.3 Theorem about some languages being recursive  (bottom of page 133), Proof at bottom of page 134 (also why Total\_cfg is not RE
% \item 13.4 - decidability of computational strings
% \item 13.5 - other models, plus foray into Section 8.2
% \item Page 141 - librarian paradox
% \item 14.1 - S\_tm not being RE
% \item 14.2 - countable sets (use of Schroder-Bernstein theorem)
% \item Example 14.1 on Diagonalization
% \item Page 146 - P(N) is not countable
% \item Page 147 - Reals are not countable
% \item Top of page 148 - S\_tm is not RE
% \item 14.4 - A\_tm is RE
% \item Page 149 - A\_tm is not recursive - two proofs
% \item Reductions (from Chapter 15)
% \item Rice's Theorem
%           \end{itemize}
% 
% 	\item 11/4    L20 
%           \begin{itemize}
%           \item Continue the above discussion
%           \item \ahref{notes20/notes20.pdf}{\Large notes20.pdf}
%           \end{itemize}
%         \end{itemize}
% 	
% \item Week11
%   \begin{itemize}
% 	\item 11/9    L21: Lecture on compiler front-ends by my RAs.
%        {\bf   Also Asg7 due.}
% 	\item 11/11   L22: Review for Midterm Exam \#2; \ahref{asg7/asg7soln.pdf}{Discuss Asg7's solution}
%         \item \ahref{notes22/midterm2-preparation.pdf}{\large\bf midterm2-preparation.pdf}
%         \end{itemize}
% 	
% \item Week12
%   \begin{itemize}
% 	\item 11/16   L23:  MIDTERM EXAM \#2 : Invigilation by TA(s)
% 	\item 11/18   
%           \begin{itemize}
%           \item \ahref{notes24/MT2soln.pdf}{Midterm-2 Solution}
%           \item L24:  Chapter 15 (Reductions), 
%             17 (Time Complexity, class NP), and
%               19 (NP-completeness)
%           \item \ahref{notes24/notes24.pdf}{notes24.pdf}
%           \item \ahref{asg8/asg8.pdf}{Asg8 on Basics of Reduction, NP-completeness}
%           \item \ahref{notes24/npc-chapter.pdf}{npc-chapter.pdf}
%           \end{itemize}
%         \end{itemize}
% 
% \item Week13
%   \begin{itemize}
% 	\item 11/23   L25: 
%           \begin{itemize}
%           \item Discuss Asg8. 
%           \item Continue with Chapter 15 (Reductions), 17 (Time Complexity, class NP), and     19 (NP-completeness)
%           \item \ahref{notes25/CS3100-11-23-10.pdf}{Lecture25.pdf} and
%          \ahref{notes25/CS3100-11-23-10.pptx}{Lecture25.pptx}
%           \end{itemize}
% 	\item 11/25   No class (Thanksgiving break)
%         \end{itemize}
% 	
% \item Week14
%   \begin{itemize}
% 	\item 11/30   L26: 
%           \begin{itemize}
%           \item Boolean Reasoning with BDDs
%           \item \ahref{notes26/mock-finals.pdf}{mock-finals.pdf}
%           \item \ahref{notes26/mock-finals-solution.pdf}{\bf Solution to mock-finals.pdf}
% 
%           \item \ahref{notes26/final-notes-cs3100-f10.pdf}{final-notes-cs3100-f10.pdf}
%           \item \ahref{notes26/minDFA-Diagonalization-BDDs.pdf}{minDFA-Diagonalization-BDDs.pdf}
%           \item \ahref{asg9/asg9.pdf}{Asg9 on BDDs and the use of DDCal handed out}
%           \item \ahref{asg9/asg9soln.pdf}{\bf Solution to Asg 9}
%           \end{itemize}
% 
% 	\item 12/2    L27: 
%           \begin{itemize}
%           \item \ahref{asg8/asg8soln.pdf}{Asg8 due; discuss its solution}
%           \item Discuss Asg9, more BDDs
%           \end{itemize}
% 
%         \end{itemize}
% 	
% \item Week15
%   \begin{itemize}
% 	\item 12/7    L29: 
%           \begin{itemize}
%           \item \ahref{asg9/asg9soln.pdf}{Asg9 due; discuss its solution}
%           \end{itemize}
% 
% 	\item 12/9    L30 (Last lecture): Course Review
%         \item \ahref{checklist-finals.html}{checklist-finals[.html]}
%           -- \ahref{checklist-finals.pdf}{[.pdf]}
% 
%         \end{itemize}
% 	
 \item	12/10   Classes end
	
\item	12/16   FINAL EXAM - 10:30 to 12:30 in class

\end{itemize}





%\section{Update history}
%
%\begin{itemize}
%
%\item None
%
%\end{itemize}








% \section{JFLAP Info}
% \label{sec:jflap}
% 
% 
% JFLAP is a free tool for experimenting with FA's. Download at:
% 
% \ahrefurl{http://www.cs.duke.edu/csed/jflap/}
% 
% To run the jar file on linux from a shell type: java -jar JFLAP.jar
% 
% JFLAP is also available on CADE in {\tt /home/cs3100/jflap/bin/jflap}. To
% use it put the directory {\tt /home/cs3100/jflap/bin} in your path
% 
% (see 
% 
% \verb|http://www.cade.utah.edu/index.php?module=faq&FAQ_op=view&FAQ_id=21|
% 
%  for info on how to do that).
% 
% Alternately, type ~cs3100/jflap/bin/jflap. To be able to use JFLAP on CADE
% remotely connect with 'ssh -Y' (don't use the -X flag, it won't work
% well). Even so, it will be slow due to network delays. Your best bet
% is to be at the CADE lab or download your own JFLAP copy.
% 
% Other ways to connect remotely:
% 
% \verb|http://www.cade.utah.edu/index.php?module=faq&FAQ_op=viewFAQs&FAQ_cat=12|.
% 
% Let us know if you have any questions about JFLAP.




%\section{Learning Goals}
%
%This class is about the fundamental capabilities and ultimate limitations
%of computing devices (as described on Page 1 of our textbook by Goddard).
%%
%It is designed to give you an appreciation for what computing devices can
%and cannot do.
%%
%For a computer science student, 
%knowing these absolute limits is as important as knowing the velocity of
%light or the lowest possible temperature is for a Physics student.
%
%
%Making a light source brighter does not alter the fundamental limit
%of the speed of light any more than
%providing more memory or providing more CPUs alters the power of a 
%computer.
%%
%That said, there are distinct classes of computational devices
%that differ only in terms of their discipline of memory access.
%%
%We shall study the following amazing facts in this course:
%\begin{itemize}
%\item A computational device built using a finite-state control mechanism and
%  two stacks (or finite-state control plus an infinite tape) models
%  all ``real-world computers.'' It is called a {\sl Turing machine.}
%
%\item Providing more stacks (than two) does not serve any useful purpose in terms
%  of increasing the computational power!
%
%\item A computational device built a using finite-state control mechanism and
%  one stack is strictly less powerful. It is called a {\sl Pushdown automaton (PDA).}
%
%\item A computational device built solely in terms of a finite-state control
%  mechanism (``zero stacks'') is the most primitive form of a ``computer.''
%  It is called a {\sl Finite Automaton (FA)}.
%
%\end{itemize}
%
%We will be studying the types of tasks that these varieties of computers can carry out and what they cannot.
%
%\subsection{A real-world Turing machine}
%
%Lest you think that these machines are figments of one's imagination,
%a Turing machine can really be built! See \\
%  \ahrefurl{http://www.parallax.com/tabid/854/Default.aspx}. \\
%  Of course, you may prefer to use a real laptop or desktop machine
%  instead of this computer---although they are strictly equal in power!
%Unfortunately,
%we will not be constructing such computers in this class (!). 
%%
%Rather we will take a 
%standard computer (equivalent to a Turing machine) and program it
%to follow the rules of finite-state or pushdown computers.
%
%\subsection{Computability and complexity}
%
%After appreciating the main characteristics of the three basic machine types,\footnotemark
%we will be focusing our attention
%on two ideas; namely, computability, and complexity.
%
%\footnotetext{Linear Bounded Automata are like TMs except they allow only the input to be
%``stomped over''---that is, overwritten. The rest of the tape is read-only. TMs can read/write
%anywhere. LBA are between PDAs and TMs in power.}
%
%
%\begin{description}
%\item[Computability:] What can Turing machines solve and
%  what can they not solve?
%
%\item[Complexity:] How do we formally understand
%  the class of ``solvable but hard'' problems called NP-hard and
%  NP-complete problems? What do these problems tell about the
%  design of algorithms for many important real-world problems?
%\end{description}
%
%While we won't study the topic of complexity a whole lot, the similarity of approaches to
%formalizing
%computability and complexity would serve as another affirmation that there is something
%fundamentally elegant about Turing machines.
%
%\subsection{How should you approach the subject?}
%
%In order to understand these ideas concretely, we must 
%use the tools of Discrete Mathematics that you have studied
%in CS 2100 (or an equivalent class).
%%
%We must learn to patiently construct mathematical proofs, and
%learn how to avoid flawed arguments---all reinforced by our assignments
%and exams (more on them later). 
%%
%This will be of primary emphasis throughout this course.
%%
%Of course, we shall employ liberal doses of real-world examples
%and light-hearted analogies whenever possible.
%
%
%It is quite easy to get discouraged by the ``pain of having to
%learn math.''
%%
%My advice is this:
%\begin{itemize}
%\item {\em Begin working on your homeworks early!} If you put off asking questions
%  till the penultimate day, you will have a very unpleasant experience
%  solving the assigned problems. Questions asked early will make it to our FAQ list also (see below).
%  
%\item {\em Please check our FAQ list often!} Our FAQ list will evolve rapidly in
%  response to your early questions. We will try to freeze the FAQ list during the days leading
%  up to the deadline.
%
%\item {\em Check email, and ask questions in class and during the TA hours!} Please take advantage of our
%  office hours. Please also check email frequently. You may wish to keep a separate folder for
%  all CS 3100 related emails (or else you will end up complaining about apparent email volume).
%
%\item {\em We are really keen on helping you!} So please do ask questions in class or during office hours!
%
%\item That said, we have very busy professional lives besides CS 3100. So consultations outside of class 
%  or office hours will be through email, but that too depending on how much time we have to process email
%  and how much our hands can type in a day ({\em i.e.}, early questions will tend to receive more attention).
%
%
%\end{itemize}
%
 



\section{Assignments, Exams, Grading}


This class will have two midterm exams and a final exam---all closed book.
%
The weightages are: 
%
\begin{itemize}
\item PARTICIPATION: 5\% (mainly through roll-call - sheet to circulate each day - but also
  through extra-ordinary creativity and/or class participation)
\item Assignments: 45\% (all assignments weighed equally).
  {\bf Two of your lowest assignment scores (after normalizing all assignments) will be dropped.}
\item  MIDTERM EXAM \#1 and MIDTERM EXAM \#2: 30\% (15 \% each)
\item FINAL EXAM: 20\%
  \begin{itemize}
  \item 10\% is for a final group project
  \item 10\% is for an in-class final exam (will examine your own project)
  \end{itemize}
\end{itemize}

The midterms will emphasize portions covered since the previous
midterm (or the beginning of the course, in case of the first midterm).
%
The final exam will emphasize portions covered after the second midterm.
%
{\em The final exam will also include higher level questions
covering the whole course.}

\subsection*{HANDIN Info}

To hand-in assignments electronically use the 'handin' utility
available in the CADE lab. Type:

{\tt handin cs3100 asg1 <files>}

\noindent where {\tt <files>} are the files to be submitted. {\tt handin cs3100}
will list the assignments available for hand-in.

\noindent {\tt WebHandin} can also be used: See
\ahrefurl{https://webhandin.eng.utah.edu/}


\subsection*{EXAM AND BREAK SCHEDULES}

The exams and breaks are as follows:


\begin{description}
  \item[Midterm Exam \#1:] {\bf 10/6 During class time} -- subject to change with sufficient
    notice
  \item[TGIFB (Thank God It's Fall Break):] {\bf Monday 10/10 - Saturday 10/15}
  \item[Midterm Exam \#2:] {\bf 11/17 During class time} -- subject to change with sufficient
    notice
  \item[Final Exam:] 12/16 in class 
    10:30 to 12:30, as per schedule posted at \\ \ahrefurl{http://www.sa.utah.edu/regist/calendar/finals/finExamSch.htm}
\end{description}


\subsection*{GRADE CALCULATION}

After determining your individual scores, we will divide the class scores into groups
based on percentage scores.
Here is how the final grades will be assigned:
 90th percent and above : A;
 83-89 : A-;
 78-82 : B+;
 75-77 : B;
 72-74 : B-;
 68-71 : C+;
 65-67 : C;
 62-64 : C-;
 58-61 : D+;
 55-57 : D;
 52-54 : D-; and
 Below 52 : E.



% Assignments will be posted pretty much every week on Tuesdays (with exceptions that will be
% announced).
% %
% You will see the assignment on the class webpage by Tuesday midnight (sometimes earlier).
% %

\subsection*{ASSIGNMENTS AND LATE POLICY}

We will not be handing out hardcopy assignments or course notes; they'll all be posted.
%
{\em All assignments will be due through handin by midnight of the due date.}

\begin{itemize}
\item Normal submission: No penalty. For assignment {\tt asg5}, the submissions must go into
  the handin directory {\bf asg5}, and similarly for all other assignment numbers. 
\item Up to one day late : 20\% off. {\bf Files must be submitted in asg5L1}, taking {\tt asg5} as an example.
\item Less than four days late : 40\% off. {\bf Files must be submitted in asg5L4}, taking {\tt asg5} as an example.
\item More than four days late : most of the points off.
  {\bf Files must be submitted in asg5L5}, taking {\tt asg5} as an example.
  {\em We won't be grading these, except at the end of the semester when your grade happens
    to be borderline, and these submissions may justify pushing you up.}
\end{itemize}

The TAs will be assigning you a pass-code using which you can look up your grades.
They will be sending you a website URL at which the grades will be available for lookup.

\subsection*{ASSIGNMENTS AND ORIGINAL SUBMISSIONS}

High level discussions are OK but please do not offer detailed help
(unless you seek our permission).
%
Non-original solutions constitute cheating; if it occurs, we will follow
University of Utah policies pertaining to academic dishonesty.


\section{Students with Disabilities}

Reasonable accommodation will gladly be provided to the known disabilities of students in the class.
Please let the instructor know the situation as soon as possible.
If you wish to qualify for exemptions under the Americans with Disabilities Act (ADA), you should also
notify the Center for Disabled Students Services, 160 Union Building. 


\end{document}

%--

          \item Solve puzzles using BDDs and DDCalc of Colorado
            (based on VIS; author: Somenzi et al.)