---

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

---

Structure: TR 1330-1445 (1:30PM-2:45PM); CB1-120; 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

Instructor: Charles Hughes; Harris Engineering Center 247C; 823-2762
Office Hours: TR 3:00PM-4:15PM
GTA: Antoniya Petkova; Harris Engineering Center 354; apetkova@knights.ucf.edu
Office Hours: MW 3:00PM-4:15PM

Required Reading: Notes

Recommended Reading:

• Garey&Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1979.
• Papadimitriou & Lewis, Elements of the Theory of Computation, Prentice-Hall, 1997.
• Davis, Sigal&Weyuker, Computability, Complexity and Languages 2nd Ed., Acad. Press (Morgan Kaufmann), 1994.
  
• 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/~odedg/cc-drafts.html
• Arora&Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  Draft available at http://www.cs.princeton.edu/theory/complexity/
• 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/~odedg/bc-drafts.html
• Sipser, Introduction to the Theory of Computation 3rd Ed., Cengage Learning, 2013.

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot6410/spr2014
Notes URL: http://www.cs.ucf.edu/courses/cot6410/spr2014/Notes/COT6410NotesSpring2014.pdf

Assignments: Around 6 to 10; Paper + Presentation

Exams: midterm and a final.

Exam Dates (Tentative): Exam#1 – Tuesday, February 25; Spring Break – March 3-8; Withdraw Deadline – Tuesday, March 18; Final – Tues., April 29, 1:00PM–3:50PM

Evaluation (Tentative):

1. Mid Term – 125 points; Final Exam – 175 points (balance between weights will be adjusted in your favor)
2. Assignments – 100 points; Paper and Presentation – 75 points
3. Extra -- 25 points used to increase weight of exams or assignments, 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 may 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. Basic notions of computability and complexity
8. Existence of unsolvable problems (counting and diagonalization)
   

Assignment #1

Review of some closure properties of formal languages

Due: 1/16 (Key)

1. Solved, solvable, unsolved, unsolvable, re, non-re
2. Hilbert's Tenth
3. Undecidable problems made a bit more concrete
   
4. Lots about problems and their complexity
5. Halting Problem (HALT) is RE, not decidable
6. Set of algorithms (TOT) is no-RE
   
7. Halting Problem seen as fun
   
8. Models of computation
• Turing machines
• Register machines
• Factor replacement systems (FRS)
• Orifinally 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 compuation 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
  

Assignment #2

Closure properties of Recursive, RE and non-RE sets

Due: 1/28 (Key)

1. Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)
2. RM simulated by Ordered FRS
3. Primitive Recursive Functions (prf)
4. Initial functions
5. Closure under composition and recursion
6. Addition and multiplication examples
7. Sample functions and predicates
8. Closure under cases
9. Bounded minimization
10. Arithmetic fuctions that use bounded search
11. Pairing functions
12. Limitations of primitive recursive
    
13. mu-recursion and the partial recursive functions

1. Notions of instantaneous descriptions (again)
2. Encodings
3. Equivalence of models
4. TMs to Register Machines
5. RM to Factor Replacement Systems
6. Factor Replacement to Recursive Functions
7. Gory details on FRS to REC
   
8. Universal machines
9. Recursive Functions to TMs
   
10. Consequences of equivalence
11. Review Undecidability (Halting Problem, shown by diagonalization)
12. RE sets and semidecidability
13. Enumeration Theorem
14. The set K = { n | n is in the n-th re set } is re, non-recursive
15. Alternative characterizations of re sets
16. Parameter Theorem (aka Sm,n Thearem)
17. Quantification and re sets
18. Quantification and non-re sets

Assignment #3

Closure of primitive recursive functions under triple recursion

1. Alternative characterizations of re sets
2. Parameter Theorem (aka Sm,n Thearem)
3. Quantification and re sets
4. Quantification and non-re sets
5. Diagonalization revisited (set of algorithms, Ko or Lu, is non-re)
6. Reduction
7. Classic sets Ko (Lu), NON-EMPTY (Lne), EMPTY (Le)
8. Reducibility and degrees (many-one, one-one, Turing)
9. Complete re set (K and Ko as examples)

Assignment #4

Quantification approximations of Complexity


Due: 2/13 (Key)

1. Rice's Theorem
2. "Picture" proofs for Rice's Theorem
   
3. Constant Time and Mortal Machines
4. END OF MATERIAL FOR Midterm

    Assignment #5


Rice's Theorem and Reduction


    Due: 2/20 (Key)

1. Sample Midterm
2. Introduction to rewriting systems (Thue, Post)
3. Semi-Thue systems
4. Word problems
5. Simulating Turing Machine by Semi-Thue System
6. Simulating by Thue Systems
7. Post Canonical Forms
8. Review and go over sample questions
9. Sample Midterm Key
10. Key for Samples from Notes
    

1. HELP SESSION on Monday, February 24, from 3:30 to 5:30 in HEC-101
   
2. Midterm (Tuesday)
3. Post Correspondence Problem
4. Grammars and re sets
5. Unsolvable problems related to context-free grammars/languages
6. Ambiguity of CFGs
7. Non-Emptiness of CFL Intersections

       Assignment #6 
   

           Post Correspondence Problem over one-letter alphabets
   

       Due: 3/13 (Key)
   

Week#9: (3/11, 3/13) -- Notes pp. 264-297; 298-314 (optional); 315-335

1. Key to Midterm
2. Context-Sensitive Grammars and Unsolvability Results
3. Valid (CSL) and Invalid Traces (CFL)
4. Intersection and Quotients of CFLs
5. Details on Valid (CSL) and Invalid Traces (CFL)
6. Intersection of CFLs revisited
7. Quotients of CFLs revisited
8. Type 0 grammars and Traces
9. L = all string over an alphabet
10. L=L^2 for L a CFL
11. Revisit Set Real-Time (Constant-Time)
12. Real-Time and Mortal Machines
13. Finite Power Problem for CFLs

1. Note: 3/18 is the Withdraw Deadline
2. Propositional Calculus (axiomatic versus truth table based)
   
3. Fast Review of Order Analysis
4. Basics of Complexity Theory
5. Decision vs Optimization Problems (achieving a goal vs achieving min cost)
6. Polynomial == Easy; Exponential == Hard
7. Polynomial reducibility
8. Verifiers versus solvers
9. P as solvable in deterministic polynomial time
10. NP as solvable in non-deterministic polynomial time
11. NP as verifiable in deterministic polynomial time
12. Concepts of NP-Complete and NP-Hard
13. Canonical NP-Complete problem: SAT (Satisfiability)
14. Some NP problems that do not appear to be in P: SubsetSum, Hamiltonian Path, k-Clique
15. Million dollar question: P = NP ?
16. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
    

    Presentation Stage #1
    

            Turn in a list of team members (3 preferred but 2 or 4 okay with permission)
    
            Turn in a citation to paper(s) being proposed as basis for paper and Fast Forward
    
             Paper being read should have length equivalent to 8 or more single spaced, two-column journal pages
                Must be at least 12 pages if four members in group (2 6-page papers works as well)
    
             Your paper that summarizes and highlights must be at least 5 pages, double-spaced, single column
                Must be at least 7 pages if four members in group
    
             Sample Topics
    

        Due: 3/25
    

1. SAT is polynomial reducible to (<=_P) 3SAT
2. 3SAT as a second NP-Complete problem
3. 3SAT <=_P SubsetSum
4. SubsetSum <=_P Partition
5. Partition equivalence to SubsetSum
6. Knapsack (relation to SubsetSum), Bin Packing
7. Bin packing (fixed capacity, minimize number of bins)
8. Pseudo polynomial-time solution for Knapsack using dynamic programming with changed parameters, n*W versus 2^n

   Assignment #7
   

           Consider the boolean CNF expression E = (a+b+c+d)(~a)(~b+d)(a+b+~d)
   
            1. Recast E in 3-CNF form (that is, with each term being a disjunct of three items)
            2. Present the table that represents a conversion of E's satisfiability to an instance of SubsetSum
            3. Explicitly write down the numbers that comprise this instance of SubsetSum
            4. Show a solution to this SubsetSum instance that encodes a solution to E's satisfiability
            5. Recast the SubsetSum instance you have as an instance of Partition
            6. Show an explicit solution to this instance of Partition -- that's easy given (3)
            7. Recast the 3-CNF form of E as an instance of k-Vertex Covering and present a solution to the latter
            8. Recast the 3-CNF form of E as an instance of the k-Coloring problem and present a solution to the latter
   

       Due: 4/8 (Key)
   

1. Reduction techniques
2. Reduction of 3SAT to k-Vertex Cover
3. 3-SAT to 3-Coloring
4. Isomophism of k-Coloring with k-Register Aloocation of live variables
5. Traveling Salesman
   
6. Scheduling problems introduced 
7. Scheduling on multiprocessor systems
8. Scheduling problems (fixed number of processors, minimize final finishing time)
   
9. N processors, M tasks, no constraints
10. Partition and scheduling problems
11. Greedy heuristics
12. 2 processor scheduling -- greedy first fit, greedy best fit,  sorted, optimalGreedy versus optimal (N/(N+1))
13. Scheduling anomalies, level strategy for UET trees, level strategy for UET dags
    
14. Precedences (lists, delays, preemption)
15. Anomalies (reducing precedence, increasing processors, reducing times)
16. Unit Execution Time: Trees, forest, anti forests
17. UET: DAGs and m=2

        Assignment #8
    

            See pages 520 to 521 in Notes
    

        Due: 4/10 (Key)

1. Hamiltonian Path
2. Travelling Salesman
3. Integer Linear Programming
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. Clean-up (PSPACE, FP, FNP, TFNP, NP-Easy, NP-Equivalent)
11. NP contained in PSPACE
12. FP is functional equivalent to P; R(x,y) in FP if can provide value y for input x via deterministic polynomial time algorithm
13. FNP is functional equivalent to NP; R(x,y) in FNP if can verify any pair (x,y) via deterministic polynomial time algorithm
14. 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)
  
15. Factoring is in TFNP, but is it in FP?
    
• If TFNP in FP then TFNP = FP,
16. P = (NP intersect Co-NP) is interesting analogue to intersection of RE and co-RE but may not hold here
    
17. 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)
18. NP-Easy -- these are problems that are polynomial when using an NP oracle
19. 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
  
20. More NP-Complete poroblems (fun ones)
21. All papers related to fast-forward presentations are due by 11:59 on 4/25.
22. I prefer just electronic versions of word or pdf files. If a pdf, I would also like the files used to create it in a zip or rar.
23. Your papers must include one or two questions you would ask of your audience
24. Final Exam Topics
    
25. Sample Final Exam Questions (E1, E2)
    
26. Review for Final Exam(s)
27. Sample Final Exam Keys (E1, E2)
    

Week#14: (4/14 (Review), 4/15 (Exam 2A), 4/17 (Exam 2B))

1. Review (Monday) from 3:00 to 5:00 in HEC-111
   
2. Exam # 2A (Tuesday):
   
• Computability material (required of all)
  
3. Exam # 2B (Thursday)
• Complexity material (required of all)
  

1. Optional Exam # 1 Booster (Tuesday) in ENG1-224 at normal class time -- 1:30 to 2:45:
   
• Computability material  from first exam
• Used to (hopefully) improve on Exam # 1 performance
• Will not count against you but please don't take if you had a strong Exam # 1