Discrete II: Theory of Computation
Fall 2016
 

U.C.F.

Charles E. Hughes
Department of Computer Science
University of Central Florida


email: charles.e.hughes@knights.ucf.edu 

Structure: TR 1630-1745 (4:30PM - 5:45PM), CB2-204; 29 class periods, each 75 minutes long.
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Instructor: Charles Hughes; Harris Engineering Center 247C; 823-2762
Office Hours: TR 1430-1545 (2:30PM - 3:45PM)
GTA: Sina Lotfian; Harris Engineering Center 234, Desk 1; slotfian@knights.ucf.edu
Office Hours: W 1000-1200 (10:00AM - 12:00PM); F 1600-1800 (4:00PM - 6:00PM)
Image of Sina so you recognize him
Text: Sipser, Introduction to the Theory of Computation 2nd/3rd Ed., Cengage Learning, 2005/2013+Notes
Secondary References: Hopcroft, Motwani and Ullman, Introduction to Automata Theory, Languages and Computation 3rd Ed., Prentice Hall, 2006.
Prerequisites: COT 3100; COP3503

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot4210/Fall2016
Notes URL: http://www.cs.ucf.edu/courses/cot4210/Fall2016/Notes/COT4210Notes.pdf

Quizzes and Assignments: 10 or so.

Exams: 2 midterms and a final.

Material: I will draw heavily from Chapters 0-7 of Sipser. Some material will also come from Hopcroft et al.. You are responsible for material discussed in notes and in in-class discussions. Not all of this is addressed in either of these texts. I highly recommend attending class, interacting with me and listening very carefully when I say a topic is important to me; hint, hint about exam questions ;-)

Important Dates: Exam#1 -- Tentatively September 29; Withdraw Deadline -- October 31; Exam#2 -- Tentatively November 3; Final -- Thursday, December 8, 1600-1850 (4:00PM-6:50PM)

Evaluation (Tentative):
Mid Terms -- 100 points each
Final Exam -- 175 points
Quizzes and Assignments -- 75 points
Bonus -- 50 points added to your best exam
Total Available: 500
Grading will be A ≥ 90%,A- ≥ 88%,B+ ≥ 85%,B ≥ 80%, B- ≥78%,C+ ≥ 75%,C ≥ 70%,C- ≥ 60%,D ≥ 50%,F < 50%


Weeks#1: (8/23, 8/25) -- Notes pp. 2-66 (Chapters 0 and 1 of Sipser); Syllabus
  1. Ground rules
  2. Sets, sequences, relations and functions (review)
  3. Ordinals, cardinals and infinities
  4. Graphs
  5. Languages
  6. Set/Language recognizers and generators
  7. Introduction to computability: historical and motivation perspective
  8. Basic notions of automata theory, formal languages, computability and complexity
  9. Brief introduction to Chomsky Hierarchy (sets context for much of course)
  10. Proof techniques
  11. Some history of the genesis of the theory of computation (Hilbert, Godel, Turing, Post, Kleene)
  12. Complexity theory: basic goals; big question is P=NP?
  13. Discussions about non-determinism versus determinism
  14. Formal definition of a Determinitic Finite (State) Automaton (DFA)
    A = (Finite State Set, Finite Input Alphabet, Transition Function, Start State, Final States), 
      where transtion function maps (Current State, Current Input Symbol) to Next State
    Can represent Transition Function by State Transition Table or State Transtion Diagram (preferred)
  15. Determinitic Finite (State) Automaton (DFA): what and why?
    Sequential circuits; pattern matchers; lexical analyzers; simple game/simulation behaviors
    Formal definition and examples
    State transition diagrams versus state transition tables
  16. Some hand-written notes for this week.

Assignment #1

See page 13 of Notes

Due: Midnight Friday, 8/26 (Key)

Assignment #2

See page 44 of Notes
Due: Thursday, 9/1 at 4:30PM (Key)

Week#2: (8/30, 9/1) -- Notes pp. 67-100 (Chapter 1 of Sipser)
  1. DFA closure (complement, union, intersection, difference, exclusive or)
  2. Non-determinism (NFA)
    Closure under concatenation, Kleene *
    Formal definition and examples
  3. The epsilon (lambda) closure of a set of states
  4. Equivalence of DFAs and NFAs (subset of all states construction)
  5. Regular Expressions (closure of primitive sets under union, concatenation and star)
  6. Every language defined by a Regular Expression is accepted by an NFA
  7. Generalized NFA (GNFA) -- Definition
  8. Every language accepted by a DFA is defined by a Regular Expression (ripping states out)
  9. Alternate approach through Rij(k) construction
  10. Languages defined by Regular Equations (not in text) and NFAs without lambda transitions
  11. Some hand-written notes for this week.

Assignment #3

See page 83 of Notes

Due: 9/8 by 4:30PM (Key)

 


Week#3: (9/6, 9/8) -- Notes pp. 95-124 (Chapter 1 of Sipser); Samples
  1. Right model for closure of Regular Languages under Intersection, Complement, and Reversal
  2. Closure of Regular Languages under Substitution, Homomorphism, and Quotient
  3. Meta approach to closure based on Substitution and Intersection
  4. Closure of Regular Languages under Prefix, Postfix, Substring, Min and Max
  5. Reachable states from some given state
  6. Reaching states to some given state
  7. Minimizing the states of a DFA (indistinguishable vs distinguishable states)
  8. Minimization example using notion of distinguishable states
  9. Classic non-regular languages {0n1n | n is greater than or equal to 0}
  10. Pumping Lemma for Regular Languages
  11. Proofs that certain languages are not regular using Pumping Lemma
  12. Right-invariant equivalence relationships and Myhill-Nerode Theorem
  13. Existence of minimal state machine for any Regular Language
  14. Proofs that certain languages are not regular using Myhill-Nerode Theorem
  15. Some handwritten notes for this week

Assignment #4 

See page 114-115 of Notes

Due: 9/15 by 4:30PM (Key)


Week#4: (9/13, 9/15) -- Notes pp. 125-142 (Chapter 1 of Sipser); Samples
  1. Additional minimization example using notion of distinguishable states
  2. More proofs that certain languages are not regular using Pumping Lemma and Myhill-Nerode
  3. Transducers (automata with output); Mealy and Moore Models
  4. Post, Thue rewriting systems
  5. Basic notion of grammars and languages generated by grammars
  6. Chomsky hierarchy (Type 3 through Type 0 grammars and languages)
  7. Notions of derivation and the language generated by a grammar
  8. Regular (right linear, Type 3) grammars
  9. Every language generated by a regular grammar is regular
  10. Every regular language is generated by a type 3 grammar
  11. Some handwritten notes for this week

Assignment #5

See page 136 of Notes

Due: 9/22 by 4:30PM (Key)


Week#5: (9/20, 9/22) --  9/23 (Help Session in ENG2-203), Notes pp. 143-168 (Chapters 1 and 2 of Sipser); Samples
  1. Every language generated by a regular grammar is regular (Formal prrof)
  2. Every regular set (language) is generated by a type 3 grammar (Formal proof)
  3. The right and left linear grammars generate equivalent classes of languages
  4. Can extend regular grammars to include strings rather than single characters
  5. Decidable Properties -- membership, emptiness, everything, finiteness, equivalence
  6. Grammars and closure properties (union, concatenation, Kleene *)
  7. Context free grammars and context free languages
  8. Sample grammars: {a^n b^n}; {w w(reversed)}; {w | #a(w) = #b(w)}
  9. Derivations (leftmost/rightmost)
  10. Parsing (parse trees; top down/bottom up)
  11. Notion of ambiguity (inherent versus due to a specific grammar)
  12. Definition of ambiguity -- some string leads to two or more
    1. Parse trees
    2. Leftmost derivations
    3. Rightmost derivations
  13. Parsing problems (left recursion bad for top-down; right recusion bad for bottom-up)
  14. DCFLs (unambiguous CFLs) versus DCFGs (unambiguous CFGs)
  15. LR(k) languages versus grammars; LL(k) languages versus grammars
    1. LR(1) languages = DCFLs; LR(k) grammars properly contained in DCFGs
    2. LL(k) languages properly contained in LL(k+1) languages
    3. LL(k) grammars properly contained in DCFGs
    4. In the limit as k goes to infinity LL(k) languages = DCFLs
  16. Some handwritten notes for this week
  17. Help Session in ENG2-203 on Friday, 9/23, September 23 from 4:30PM – 5:50PM
  18. Exam#1 Topics pp. 152-156 in Notes
  19. Sample Exam  -- Complete this for discussion on 9/27 (key)

Week#6: Notes pp. 152-156, 9/28 (Help Session in HEC-101C), 9/27 (Chapter 2 of Sipser, review), 9/29 (Midterm1) 
  1. Help Session in HEC-101C on Wednesday, 9/28, from 10:00AM to 12:00PM
  2. Exam#1 Topics pp. 152-156 in Notes
  3. Review and go over sample questions
  4. MidTerm 1  (Chapters 0, 1; Notes pp. 1-156; Assignments 1-5)


Week#7: (10/4, 10/6 -- Hurricane Matthew) -- Notes pp. 169-179; Chapter 2 of Sipser
  1. More top-down versus bottom-up
  2. Removing left or right recursion to accommodate top-down or bottom-up
  3. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
    1. Eliminate lambda rules and accommodate for nullable non-terminals
    2. Eliminate unit rules (chains of non-terminals)
    3. Eliminate non-productive non-terminals (no terminal string can be generated from them)
    4. Eliminate unreachable non-terminals (cannot get to them from S)
    5. To be continued after Matthew Mayhem
  4. Some handwritten notes for this week

Assignment #6

See page 187 of Notes

Due: 10/18 by 4:30PM (Key) Comments


Week#8: (10/11, 10/13) -- Notes pp. 172-215; Chapter 2 of Sipser
  1. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
    1. Eliminate lambda rules and accommodate for nullable non-terminals
    2. Eliminate unit rules (chains of non-terminals)
    3. Eliminate non-productive non-terminals (no terminal string can be generated from them)
    4. Eliminate unreachable non-terminals (cannot get to them from S)
    5. On rhs's of length >1, replace each terminal with symbol that derives it directly
    6. Recursively change rhs of length k, k>2, to two rules, one with rhs of length 2 and the other of length k-1
  2. Cocke-Kasami-Younger (CKY) polynomial time CFG parser
  3. Pumping Lemma for CFLs
  4. Constructive proof of Pumping Lemma for CFLs
  5. Some handwritten notes for this week
  6. More examples of CKY
  7. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
  8. Pushdown automata (PDA) non-determinstic vs deterministic
  9. Notion of instantaneous description (ID)
  10. Equivalence of a variety of PDA formalizations
    1. Bottom of stack marker versus none at start
    2. Ability to push none or one, versus many characters on stack
    3. Recognition by accepting state, by empty stack and by both
    4. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
  11. Shorthand notation for PDA
  12. Non-determinism in PDAs
  13. Examples PDAs
  14. Top down parsing of a CFL by PDA
  15. Bottom up parsing of CFL by PDA
  16. Using just pop and push operations in a PDA
  17. Converting PDA to CFG
  18. Some handwritten notes for this week
  19. Midterm Exam#1 Key


Week#9: (10/18, 10/120 -- Notes pp. 213-251; Chapter 2 of Sipser

  1. Greiback Normal Form (GNF) and linear parsing (with great guessing)
  2. Example to show PDA language is a CFL by two different methods
  3. Closure properties for CFLs (intersection with regular, substitution)
  4. Using substitution and intersection with regular to get many more,
    e.g., prefix, suffix , substring and quotient with regular
  5. Non-closure (intersection and complement)
    1. Intersection of {a^n b^n c^m} and {a^m b^n c^n}
    2. Complement
  6. Max and Min non-closure
  7. Complement of {ww | w is a string over Sigma* } is a CFL
  8. Solvable Decision Probelms about CFLs and CFGs
  9. Solvable Decision Problems for CFL, L
    1. Is w in L?
    2. Is L empty (non-empty)?
    3. Is L finite (infinite)?
  10. Context Sensitive Grammars (CSG) and Languages (CSL)
  11. Phrase Structured Grammars (CSG) and Languagess (re)
  12. Some handwritten notes for this week
  13. This ends the material for Exam#2
  14. Solved/Unsolved, Solvable/Unsolvable, Enumerable (semi-decidable)/Non-Enumerable
  15. Hilbert 10th
  16. Cantor and diagonalization -- countable versus uncountable
  17. Countability of machines/programs in any model of computation
  18. Counting argument that there are undecidable problems
  19. Halting Problem defined
  20. Notations for convergence and non-convergence
  21. Halting Problem -- undecidabibility using diagolization
  22. Turing Machines
  23. Some handwritten notes for this week

Assignment #7

See page 220 of Notes

Due: 10/27 by 4:30PM (Key)


Week#10: (10/25, 10/27) -- Notes pp. 252-310; Chapter 3 of Sipser;  10/28 Help Session in MSB 260) 4:00PM-6:00PM
  1. Variants of Turing Machines
  2. Turing Machines as enumerators/recognizers
  3. Review and go over topics and sample questions
  4. Register Machines
  5. Factor Replacement Systems (FRS) as simple models of computation
  6. The necessity of order with FRSs
  7. Some handwritten notes for this week
  8. Discussion of determinism versus non-determinism in models of computation
  9. Primitive (incomplete) and mu recursive (complete) functions
  10. Numbering machines
  11. Universal Machine
  12. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
  13. Diagonalization proof for Halting Problem
  14. Halt is semi-decidable
  15. Sample Exam#2
  16. Sample Exam#2 Key
  17. Exam#2 Topics pp. 224-225 in Notes
  18. Only Help Session is on 10/28 at 4:00PM-6:00PM in MSB 260
  19. Note: 10/31 is the Withdraw Deadline


Week#11: (11/1, 11/3) -- Notes pp. 311-319; 11/2 Help Session in Engr1-427 9:00-9:50; 11/3 (Midterm2)
  1. Help Session on Wednesday is from 9:00 to 9:50 in ENG1-427
  2. Handrwriien Notes for Tuesday
  3. MidTerm 2 on Thursday, 11/3


Week#12: (11/8, 11/10) -- Notes pp. 320-373; Chapters 4, 5 of Sipser 
  1. The set of algorithms is non-re
  2. Diagonalization proof for non-re nature of set of algorithms
  3. Enumeration Theorem
  4. Set TOTAL
  5. Reducibility as a technique to show undecidability
  6. Reducibility as a technique to show non-re-ness
  7. Using reducibility to show properties of Zero = { f | for all x f(x) =0 }
  8. Many-one reducibility and equivalence
  9. Notion of (many-one) re-complete sets (HALT is one such set)
  10. One-one reducibility and one-one degrees
  11. Turing reducibility and Turing degrees
  12. The sets K and K0 are equivalent and re-complete
  13. Rice's Theorem (weak and strong forms)
  14. Applying Rice's
  15. Handwritten Notes for Tuesday
  16. RE sets
  17. STP predicate (STP(f,x,t) iff f(x) converges in t steps or fewer)
  18. VALUE(f,x,t) = f(x) if STP(f,x,t), else 0
  19. Finally, proof that re and semi-decidable are same
  20. Proof that re and co-re iff recursive (decidable, solvable)
  21. Quantification as a tool to identify upper bound complexity
  22. Rewriting Systems -- Semi-Thue systems
  23. Undecidability of Semi-Thue word problem (ST(Word)
  24. Post Correspondence Problem (PCP)
  25. ST(Word) reduced to PCP shows PCP unsolvable
  26. Applications of PCP (Undecidability of Ambiguity of CFLs and Non-emptiness of Intersection of CFLs)
  27. Application of PCP to Undecidability of Non-emptiness of CSLs
  28. CSL emptiness
  29. Handwritten Notes for Thursday

Assignment #8

See page 339 of Notes

Due: 11/17 by 4:30PM (Key)

Assignment #9

See page 356 of Notes

Due: 11/29 by 4:30PM (Key)


Week#13:  (11/15, 11/17) --  Notes pp. 374-409 Chapters 5  and 6 of Sipser 
  1. Traces (computational histories)
  2. Quotients of CFLs
  3. Traces and Type 0 (PSG)
  4. ST(Word) reduced to re membership
  5. Lots of consequences of above
  6. Is L = Sigma*? Is L = L^2? undecidable for CFL
  7. Non-closure of L1/L2 (both CFLs)
  8. More Unsolvable Decision Problems for CFL, L
    1. Is L = L', where L' is some other CFL?
    2. Is L intersect L' empty (non-empty)
  9. Handwritten Notes for Tuesday
  10. Introduction to Complexity Theory
  11. Verifiers versus solvers
  12. NP as verifiable in deterministic polynomial time
  13. P as solvable in deterministic polynomial time
  14. NP as solvable in non-deterministic polynomial time
  15. Million dollar question: P = NP ?
  16. Some NP problems that do not appear to be in P: SubsetSum, Partition
  17. Concepts of NP-Complete and NP-Hard
  18. Canonical NP-Complete problem: SAT (Satisfiability)
  19. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
  20. 3SAT as a second NP-Complete problem
  21. 3SAT to SubsetSum reduction
  22. SubsetSum equivalence (within a polynomial factor) to Partition
  23. Midterm Exam#2 Key



Week#14: (11/22, Thanksgiving) --  Notes pp. 410-434; Chapters, 5 and 7 of Sipser (pp. 246-256 were informational only)

  1. Handwritten Notes on Sample Questions from Notes pp. 352-355
  2. 0-1 Integer Linear Programming
  3. Vertex Cover
  4. Independent Set
  5. K-Color
  6. Sample Final

    Assignment #10

    See page 434 of Notes
    Due: 12/1 by 4:30PM (Key)



Week#15:  (11/29, 12/1) --   Notes pp. 435-467; Chapter 7 of Sipser; Final Exam Review

  1. K-Color Continued
  2. Register Allocation
  3. Scheduling on multiprocessor systems
  4. Final Exam Topics (Notes pp. 462-467)
  5. Sample Final (Key)
  6. Final Exam Review
  7. Picture of Relations of REC, RE, Co-RE, NRNC, NR
  8. Following material will not be on exam and may not even be discussed (Notes pp. 468-496)
  9. Hamilton Circuit
  10. Travelling Salesman
  11. Tiling (undecidable in plane; NP-Complete in polynomial size limited plane)

Review Sessions: HEC-103; Monday, December 5; 1300 - 1500 (1:00PM - 3:00PM)

Final Exam; Thursday, December 8; 1600 - 1850 (4:00PM - 6:50PM)



© UCF Last Updated December 8, 2016