---

email: charles.hughes@ucf.edu

---

Structure: TR 1330-1445 (1:30PM-2:45PM); HEC-103; 28 class periods, each 75 minutes long.
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Instructor: Charles Hughes; Harris Engineering Center 247C
Office Hours: TR 3:15PM-4:30PM
GTA:  Harish Raviprakash; harishr@knights.ucf.edu; HEC-308
Office Hours: MW 1:30PM-3:00PM

Required Reading: Notes (PowerPoint Version)

Recommended Reading:

• Cooper, Computability Theory 2nd Ed., Chapman-Hall/CRC Mathematics Series, 2003.
  
• Garey&Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1979.
• Davis, Sigal&Weyuker, Computability, Complexity and Languages 2nd Ed., Acad. Press (Morgan Kaufmann), 1994.
  
• Papadimitriou & Lewis, Elements of the Theory of Computation, Prentice-Hall, 1997.
• Bernard Moret, The Theory of Computation, Addison-Wesley, 1998.
  
• Hopcroft, Motwani&Ullman, Intro to Automata Theory, Languages and Computation 3rd Ed., Prentice-Hall, 2006.
• Oded Goldreich, Computational Complexity: A Conceptual Approach, Cambridge University Press, 2008.
  Draft available at http://www.wisdom.weizmann.ac.il/~/oded/cc-drafts.html
• Oded Goldreich, P, NP, and NP-Completeness: The Basics of Complexity Theory, Cambridge University Press, 2010.
  Draft available at http://www.wisdom.weizmann.ac.il/~/oded/bc-drafts.html
• Arora&Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  Draft available at http://www.cs.princeton.edu/theory/complexity/
• Sipser, Introduction to the Theory of Computation 3rd Ed., Cengage Learning, 2013.

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot6410/Spring2019
Notes URL: http://www.cs.ucf.edu/courses/cot6410/Spring2019/Notes/COT6410NotesSpring2019.pdf
http://www.cs.ucf.edu/courses/cot6410/Spring2019/Notes/COT6410NotesSpring2019.pptx

Assignments: Around 6 to 10; Paper + Presentation

Exams: midterm and a final.

Exam Dates (Tentative): Exam#1 – Thursday, March 7; Spring Break – March 11-16; Withdraw Deadline – Wednesday, March 20; Study Day – Tuesday, April 23; Final – Tues., April 30, 1:00PM–3:50PM

Evaluation (Tentative):

1. Mid Term – 125 points; Final Exam – 200 points (balance between weights will be adjusted in your favor)
2. Assignments – 75 points; Paper and Presentation – 75 points
3. Extra -- 25 points used to increase weight of best exam,  or maybe presentation, always to your benefit
4. Total Available: 500
5. Grading will be  A >= 90%, B+ >= 85%, B >= 80%, C+ >= 75%, C >= 70%, D >= 50%, F < 50%; minus grades might be used.
   

.

1. Ground rules
2. Decision problems
3. Solving vs checking
4. Procedures vs algorithms
5. Introduction to theory of computation
6. Terminology, goals and some historical perspective
7. Review of automata (finite, pushdown, linear bounded, Turing machines)
8. Review of formal languages (regular, context free, context sensitive, phrase structured)
9. Review material created by Prof. Jim Rogers, Earlam College
10. Review material from Prof. Workman, UCF
11. COT4210 material from Prof. Matt Gerber, UCF
12. COT4210 material by me on Automata Theory and Formal Languages
    

Financial Aid (Assignment#1)

Survey at Webcourses

Due: Friday, January 11 at 5:00 PM

1. Continue Automata/Formal Languages Review
2. MyHill-Neroda as proof of min DFA uniqueness
3. Myhill-Nerodaa s a tool to show languages are not regular.
   
4. The chosen language is
   L = { aⁿ b^m | n is not equal to m}.
   This can be shown easily in an indirect manner by showing its complement is not regular, A direct approach is using right invariant equivalence classes as it is not amenable to the Pumping Lemma.
5. Review of reduced CFGs
6. Chomsky Normal Form (CNF)
   
7. The use of CNF in the Cocke-Kasami-Younger O(N³) parsing of CFLs generated by CNFs.

1. Pumping Lemma for CFLs
   
2. Show L = { ww | w is in {a,b}⁺ } is not a CFL
3. CSG for L
   
4. CFG for the complement of L
   { xy | |x| = |y| but x is not the same as y }
   can be first viewed as
   {x1 a x2 y1 b y2 | |x1|=|x2|, |y1|=|y2|} Union
     {x1 b x2 y1 a y2 | |x1|=|x2|, |y1|=|y2|}.
   But this can also be seen as
   {x1 a y1 x2 b y2 | |x1|=|x2|, |y1|=|y2|}.Union
     {x1 b y1 x2 a y2 | |x1|=|x2|, |y1|=|y2|}.
   The above is easy to show as a CFL. We then union this with odd length and we have L1 complement.
   
5. Basic notions of computability and complexity
6. Existence of unsolvable problems (counting and diagonalization)
7. Solved, solvable (decidable, recursive), unsolved, unsolvable, re, non-re
8. Hilbert's Tenth
9. Undecidable problems made a bit more concrete
10. Lots about problems and their complexity
11. Halting Problem (HALT) is re, not decidable
12. Set of algorithms (TOT) is non-re
13. Halting Problem seen as fun
14. Some consequences of non-re nature of algorithms
15. Turing Machines
    

Assignment #2

Posted on Webcourses

1. Insights from intro computability material
   
2. Models of computation
• Turing machines
  
• Register machines
• Factor replacement systems (FRS)
• Originally introduced by John Conway, "Unpredictable Iterations," Proceedings of the 1972 Number Theory Conference (1972), pp. 49-52
• Google Fractran for more information on Conway's fractional computation systems
  Weisstein, Eric W. "FRACTRAN." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/FRACTRAN.html
• The 3x+1 problem http://arxiv.org/pdf/math/0309224.pdf
3. Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)
4. RM simulated by Ordered FRS
5. Primitive Recursive Functions (prf)
6. Initial functions
7. Closure under composition and recursion
8. Primitive recursive functions SNAP, TERM, STP and VALUE
9. Primitive Recursive Function in detail
10. Addition and multiplication examples
11. Sample functions and predicates
12. Closure under cases
13. Bounded minimization
14. Arithmetic fuctions that use bounded search
15. Pairing functions
16. Limitations of primitive recursive
17. mu-recursion and the partial recursive functions
18. Notions of instantaneous descriptions
19. Encodings
20. Equivalence of models
21. TMs to Register Machines
22. RM to Factor Replacement Systems

1. Factor Replacement to Recursive Functions
2. Gory details on FRS to REC
3. Universal machines
4. Recursive Functions to TMs
5. Consequences of equivalence
6. Review Undecidability (Halting Problem, shown by diagonalization)
7. RE sets and semidecidability
8. The set of all re sets W₀, W₁, W₂, ...
9. Enumeration Theorem
10. The set K = { n | n is in the n-th re set } = { n | n is in W_n } is re, non-recursive
11. The set K₀ = HALT = { <n,x> | x is in the n-th re set }
12. Alternative characterizations of re sets
13. Parameter Theorem (aka Sm,n Thearem)
14. Quantification and re sets
15. Quantification and Co-re sets
16. Diagonalization revisited (set of algorithms is non-re and K₀ (Lu) = HALT is non-rec)
17. Reduction
18. Classic sets Ko (Lu), NON-EMPTY (Lne), EMPTY (Le)
19. Reduction from Ko that shows undecidability of K, HasZero, IsNonEmpty
20. Complete re set (K and K₀ as examples)
21. Note: To be re-complete a set must be re

Assignment #3

Posted in Webcourses

Due: 2/14 (Key)

1. Reduction from Ko that shows undecidability of K, HasIndentity, TOTAL, IsZero, IsEmpty, IsIdentity
2. Equivalence of certain re sets (K, HasZero, IsNonEmpty, HasIndentity) to Ko
3. Equivalence of centain non-re sets (IsZero, IsEmpty, IsIdentity) to TOTAL
4. Quantification of Non-re, Non-Co-re sets
   
5. Reducibility and degrees (many-one, one-one, Turing)
6. Hierarchy or RE equivalence class (m-1 and 1-1 degrees)
7. Rice's Theorem
8. "Picture" proofs for Rice's Theorem
9. Constant Time and Mortal Machines
10. Practice Probelms (I will provide solutions next week)
    
11. Introduction to rewriting systems (Thue, Post)
12. Semi-Thue systems
13. Word problems

    Assignment #4


Posted in Webcourses
Sample with key


    Due: 2/26 (Key)

1. Simulating Turing Machine by Semi-Thue System
2. Simulating by Thue Systems
3. Post Canonical Forms
4. Post Correspondence Problem
5. Grammars and re sets
6. Unsolvable problems related to context-free grammars/languages
7. Ambiguity of CFGs
8. Non-Emptiness of CFL Intersections
9. Context-Sensitive Grammars and Unsolvability Results
10. Valid (CSL) and Invalid Traces (CFL)
11. Intersection and Quotients of CFLs
12. Details on Valid (CSL) and Invalid Traces (CFL)
13. Intersection of CFLs revisited
14. Quotients of CFLs revisited
15. Type 0 grammars and Traces
16. L =  S*  for L a Regular or CFL
17. L=L^2 for L a CFL
18. Finite Convergence
19. Finite Power Problem for CFLs

1. Summary of Grammar Results
   
2. Revisit Set Real-Time (Constant-Time)
3. Real-Time and Mortal Machines
4. Finite Power Problem for CFLs
5. Closure properties for re and recursive sets
   
6. Propositional Calculus
7. Axiomatizable Fragments
8. Unsolvability for Membership in Fragments of Diadic Partial Implicational Propositional Calculus
9. Review session and sample exams
10. Exam Topics
    
11. Sample exam1; Sample exam1 key
    
12. Sample exam2; Sample exam2 key
13. Sample exam3; Sample exam3 key
14. Key to Samples from Notes
15. Yet Other Examples (Focused on Formal Languages and Automata Theory)
16. Yet Other Examples key (Focused on Formal Languages and Automata Theory)
17. Midterm Legal Cheat Sheet
    

Week#9: (3/5, 3/7) -- Notes pp. 516-633; Midterm Help Session 10-noon on Wednesday, 3/6 in HEC-101A; Midterm on Thursday, 3/7

1. Basics of Complexity Theory
2. Decision vs Optimization Problems (achieving a goal vs achieving min cost)
3. Polynomial == Easy; Exponential == Hard
4. Polynomial reducibility
5. Verifiers versus solvers
6. P as solvable in deterministic polynomial time
7. NP as solvable in non-deterministic polynomial time
8. NP as verifiable in deterministic polynomial time
9. Concepts of NP-Complete and NP-Hard
10. Canonical NP-Complete problem: SAT (Satisfiability)
11. Some NP problems that do not appear to be in P: SubsetSum, Hamiltonian Path, k-Clique
12. Million dollar question: P = NP ?
13. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
14. SAT is polynomial reducible to (<=_P) 3SAT
15. 3SAT as a second NP-Complete problem
16. Integer Linear Programming
    
17. Midterm (Thursday)

 Presentation Stage #1

                Turn in a list of team members (3 preferred)
                Turn in a citation to paper(s) being proposed as basis for paper and Presentation
                 Your paper that summarizes and highlights must be at least 6 pages,
                 double-spaced, single column


                 Sample Topics (see SampleTopics Folder)

  Assignment #5

        See Notes, Page 680

Week#10: SPRING BREAK

1. Note: 3/20 is the Withdraw Deadline
2. 3SAT <=_P SubsetSum
3. SubsetSum <=_P Partition
4. Partition equivalence to SubsetSum
5. Discussion of group presentations
6. Reduction of 3SAT to k-Vertex Cover
7. 3-SAT to 3-Coloring
8. Isomophism of k-Coloring with k-Register Aloocation of live variables
9. Scheduling problems introduced 
10. Scheduling on multiprocessor systems
11. Scheduling problems (fixed number of processors, minimize final finishing time)
12. N processors, M tasks, no constraints
13. Partition and scheduling problems
14. Greedy heuristics
15. 2 processor scheduling -- greedy based in list, sorted long to short, sorted short to long, optimal. Tradeoffs.
    
16. Scheduling anomalies, level strategy for UET trees, level strategy for UET dags
17. Precedences (lists, delays, preemption)
18. Anomalies (reducing precedence, increasing processors, reducing times)
19. Unit Execution Time: Trees, forest, anti forests
20. UET: DAGs and m=2
21. Midterm Key
22. Sample Presentation (paper and abstract) from 2015
    This one was a group of two (smaller class size)
    The paper started with a 1998 thesis and brought us up to date (2015 pubs)
    
23. Sample presentation (paper only) from 2014
    This was also a group of two
    The paper started with a 2011 paper and worked backwards to those from which the 2011 result built
24. Both of the above were really well-done; for this Saturday evening, I just want
    Citation with pdf of paper that you will use to start your journey
    Brief abstract of your goals
    Team members
25. For Final paper and presenation I would like  that the conclusion include your own take on the importance of the results relative to your own research including potential extensions. I am okay if you pick a single challenging paper and dissect it so others can understand the results and techniques. I am also fine with a journay (actually preferred) of papers that either start with a classic and bring us up to today or start with today and help us understand today's results in terms of other prior research.

1. Hamiltonian Path
2. Travelling Salesman
3. Knapsack (relation to SubsetSum), Dynamic Programming Approach
4. Bin packing (fixed capacity, minimize number of bins)
5. Pseudo polynomial-time solution for Knapsack using dynamic programming with changed parameters, n*W versus 2^n
6. Reduction techniques
7. Tiling the plane and Bounded Tiling
8. Bounded PCP
   

           Assignment #6
   

                Posted in Webcourses
   

           Due: 4/4 (Key)

1. You must send me preferred day of presentation by 4/7 at 6:00PM.
   
• The days to choose from are 4/9, 4/11, 4/16, 4/18.
2. You must send me an abstract of your presentation by 6:00 PM, two days prior to your scheduled day (one to two paragraphs)
• The abstract must include title and team member names
• It is designed so everyone is mentally prepared for your presentation
  
3. All papers and final versions of presentation slides are due as pdf files by 11:59 on 4/26
   
• Your papers must include one or two questions you would ask of your audience
• I would also like the files (word, power point, tex, etc.) used to create these in a zip or rar
4. co-NP
5. P = co-P ; P contained in intersection of NP and co-NP
6. NP-Hard
7. QSAT as an example of NP-Hard, possibly not NP
8. NP-Hard problems are in general functional not necessarily decision problems
9. NP-Complete are decision problems as they are in NP
10. NP-Easy -- these are problems that are polynomial when using an NP oracle
11. NP-Equivalent is the class of NP-Easy and NP-Hard problems
• In essence this is functional equivalent of NP-Complete but also of co-NP Complete
  
• NP-Equivalent uses a Turing machine polynomial time reduction so just uses rather than accepts answers from oracle
12. Optimization versions of SubsetSum and of K-Color
    
13. Clean-up (PSPACE, NPSPACE, CO-PSPACE, PSPACE-COMPLETE)
    
14. EXPSPACE, EXPTIME, NEXPTIME
15. ATM (Alternating NDTM)
16. QSAT. Petri Nets, Presburger
    
17. FP is functional equivalent to P; R(x,y) in FP if can provide value y for input x via deterministic polynomial time algorithm
18. FNP is functional equivalent to NP; R(x,y) in FNP if can verify any pair (x,y) via deterministic polynomial time algorithm
19. TFNP is the subset of FNP where a solution always exists, i.e., there is a y for each x such that R(x,y).
• Task of a TFNP algorithm is to find a y, given x, such that R(x,y)
• Unlike FNP, the search for a y is always successful
  
• FNP properly contains TFNP contains FP (we don't know if proper)
  
20. Factoring is in TFNP, but is it in FP?
    
• If TFNP in FP then TFNP = FP
21. P = (NP intersect Co-NP) is interesting analogue to intersection of RE and co-RE but may not hold here
22. It appears that TFNP does not have any complete problems!!!
• The deal is that there is no known recursive enumeration of TFNP but there is of FNP
• This is similar to total versus partially recursive functions (analogies are everywhere)
23. Sample slides from prior years -- mostly anonymized so you don't bug the authors
    (GMCP, Multiple object tracking as ILP, Self Assembly, Theorem Proving
    

1. Validity of SubsetSum optimization reduction to SubsetSum Decision Problem Oracle
   
2. Final Exam Topics
   
3. Sample Final Exam (Key)
4. 4/11 Presentations (In order as below; Group letters are for my convenience)
   A (4/11)    Abusnaina:  How computational models can help unlock biological systems (Abstract)
   H (4/11)    Cunningham: Memcomputing: Leveraging memory and physics (Abstract)
   L (4/11)     Jamal: GMMCP for multiple object tracking (Abstract)
   M (4/11)    Lamar: Decidability of Shared Memory Safety (Abstract)
   O (4/11)    Shelopugin: Parameterized tractability of single machine scheduling with rejection (Abstract)
   

Week#15: (4/16, 4/18)

1. 4/16 Presentations (In order as below; Group letters are for my convenience)
   B (4/16)    Al Hasan: Neural Combinatorial Optimization with Reinforcement Learning (Abstract)
   C (4/16)    Al Ruabye: Minimum Weight Vertex Cover Problem (Abstract)
   F (4/16)     Chouhan:  LSTM to Transformer to Star-Transformer (Abstract)
   G (4/16)    Cimen: Bounded PCP (Abstract)
   N (4/16)    Li: The Raod from Simulated Annealing to GNNs (Abstract)
   
2. 4/18 Presentations (In order as below; Group letters are for my convenience)
   D (4/18)    Ardebili: Oracle Separation of BQP and PH (Abstract)
   E (4/18)    Belcher: Message Passing Neural Networks (Abstract)
   I  (4/18)    Duarte: Data-Driven Approximations to NP-Hard Problems (Abstract)
   J (4/18)     Fahmi: Multiple Sequence Alignment (Abstract)
   K (4/18)    Hu: Tackling Reinforcement Learning with Deep Neural Networks (Abstract)
   

   

Week#16:  (4/23 -- Review Day in HEC-103 From 1:30PM To 2:45PM)

1. Complete Review
   
2. Due on Friday, 4/26 by midnight
• Paper associated with presentation
• Presentation (pptx, pdf, or whatever)
• Note: pdf files should be accompanied by zip of source