---

email: ceh@cs.ucf.edu 

---

Structure: TR 1330-1445 (1:30PM-2:45PM); COMM-114; 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:15PM-4:30PM
GTA: Syed Zain Masood, HEC-234
Office Hours: MW 3:15PM-4:30PM

Required Reading: Notes
Recommended Reading:
Arora & Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Sipser, Introduction to the Theory of Computation 2nd Ed., Course Technologies, 2005
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.
Hopcroft, Motwani&Ullman, Intro to Automata Theory, Languages and Computation 2nd Ed., Addison-Wesley, 2001
Davis, Sigal and Weyuker, Computability, Complexity and Languages 2nd Ed., Academic Press (Morgan Kaufmann), 1994.

Web Pages:
Base URL: http://www.eecs.ucf.edu/courses/cot6410/spr2012
Notes URL: http://www.eecs.ucf.edu/courses/cot6410/spr2012/Notes/COT6410NotesSpring2012.pdf

Assignments: Around 6 to 10; Paper + Presentation

Exams: midterm and a final.

Exam Dates (Tentative): Exam#1 – Tuesday, February 28; Spring Break – March 5-10; Withdraw Deadline – Tuesday, March 20; Final – Tues., April 24, 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 compuation
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/19 (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

Assignment #2

Closure properties of Recursive, RE and non-RE sets

Due: 1/31 (Key)

1. Models of computation
• Turing machines
• Register machines
• Factor replacement systems (FRS)
• Petri Nets
• RM simulated by Ordered FRS
2. Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)
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
2. Encodings
3. Equivalence of models
4. TMs to Register Machines
5. RM to Factor Replacement Systems
6. Factor Replacement to Recursive Functions

   Assignment #3

   a. Prove that the primitive recursive functions are clsed under multual recursion. Mutual recusrion is defined by:
       Assume g1, g2, h1 and h2 are know to be primitive recursive. Define
       f1(x,0) = g1(x); f1(x,y+1) = h1(f2(x,y)); f2(x,0) = g2(x); f2(x,y+1) = h2(f1(x,y))
   b. Redo the construction that shows a universal recursive function associated with FRS, but use the pairing
       function, not the factor encoding
   

   Due: 2/14 (Key)
   

1. Gory deatils on FRS to REC
   
2. Universal machines
3. Recursive Functions to TMs
   
4. Consequences of equivalence
5. Review Undecidability (Halting Problem, shown by diagonalization)
6. Notation matching (mine versus Davis's)
7. RE sets and semidecidability
8. Enumeration Theorem
9. The set K = { n | n is in the n-th re set } is re, non-recursive
10. Alternative characterizations of re sets
11. Parameter Theorem (aka Sm,n Thearem)
12. Quantification and re sets

1. Quantification and non-re sets
2. Diagonalization revisited (set of algorithms, Ko or Lu, is non-re)
3. Reduction
4. Classic sets Ko (Lu), NON-EMPTY (Lne), EMPTY (Le)
5. Reducibility and degrees (many-one, one-one, Turing)
6. Complete re set (K and Ko as examples)
7. Rice's Theorem

1. "Picture" proofs for Rice's Theorem
   
2. Constant Time and Mortal Machines
3. END OF MATERIAL FOR Midterm
4. Sample Midterm
5. Introduction to rewriting systems (Thue, Post)
6. Post Canonical Forms
7. Review and go over sample questions
8. Sample Midterm Key

1. Midterm (Tuesday)
2. Semi-Thue systems
3. Word problems
4. Simulating Turing Machine by Semi-Thue System
5. Simulating by Thue Systems
6. Grammars and re sets
7. Unsolvable problems related to context-free grammars/languages
8. Post Correspondence Problem

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

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

    Assignment #4 

        1. Present a decision procedure for the word problem for Semi-Thue Systems over one-letter alpahabets.
        2. Present a decision procedure for the Post Correspondence Problem over one-letter alpahabets.

    Assignment #5 

        Proposed team presentations (preferably 3 members per team)
            Topic, abstract, team members, resources (papers, texts, people)
       Details and Suggestions

1. Optional Midterm2 on 3/19
2. Note: 3/20 is the Withdraw Deadline
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
17. Optional Midterm2 Key

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
9.     using dynamic programming with changed parameters, n*W versus 2^n
10. Reduction techniques
11. Reduction of 3SAT to k-Vertex Cover

1. Note that you must send me your presentations at least 2 days before you present)
   
2. 3-SAT to 3-Coloring
3. Isomophism of k-Coloring with k-Register Aloocation of live variables
4. Scheduling problems introduced 
5. Scheduling on multiprocessor systems
6. Scheduling problems (fixed number of processors, minimize final finishing time)
   
7. N processors, M tasks, no constraints
8. Partition and scheduling problems
9. Greedy heuristics
10. 2 processor scheduling -- greedy first fit, greedy best fit,  sorted, optimalGreedy versus optimal (N/(N+1))
11. Scheduling anomalies, level strategy for UET trees, level strategy for UET dags
    
12. Precedences (lists, delays, preemption)
13. Anomalies (reducing preceeedence, increasing processors, reducing times)
14. Unit Execution Time: Trees, forest, anti forests
15. UET: DAGs and m=2
16. co-NP
17. P = co-P ; P contained in intersection of NP and co-NP
18. NP-Hard
19. QSAT as an example of NP-Hard, possibly not NP
20. More NP-Complete poroblems (fun ones)
    

1. Presentations 20 minutes + 5
2. 4/10 Philip Shibly, Jose Sanchez
3. 4/10 Frank Plochan, Andrew Yee, Deli Zhang
4. 4/10 Jeff Cashion, Chris Zorn
   
5. 4/12 Greg Morse, Charles Synyder
6. 4/12 Jun Ding, Ying Wang
7. Clean-up (NP-Easy, NP-Equivalent, FP, FNP)
8. Sample Final exam Questions
   

Week#14:(4/17, 4/19)

1. 4/17 Sarah Buchanan, Juliet Norton
2. 4/17 Rahmatollah Beheshti, Haroon Idrees, Ashkan Paya
   
3. 4/17 Vera Kasakova, Anthony Wehrer
4. Sample papers in Projects/Samples/
   
5. All papers related to presentations are due by 11:59 on 4/23.
   
6. 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.
   
7. Your papers must include one or two questions you would ask of your audience
8. Sample Final Exam Key
9. Review for Final Exam