---

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

---

Structure: TR 1800-1915 (6:00PM-7:15PM); 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 1530-1645 (3:30PM-4:45PM)

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.
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.
Sipser, Introduction to the Theory of Computation 2nd Ed., Course Technologies, 2005

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot6410/fall2010
Notes URL: http://www.cs.ucf.edu/courses/cot4210/fall2010/Notes/COT6410NotesFall2010.pdf 

Assignments: Around 6 to 8; Paper + Presentation

Exams: midterm and a final.

Exam Dates (Tentative): Exam#1 – Tuesday, October 5 (tentative); Withdraw Deadline – Friday, October 15; Veterans Day – Thursday, November 11; Thanksgiving – Thursday, November 25; Final – Tues., Dec. 7, 4:00PM–6:50PM

Evaluation (Tentative):

1. Mid Term – 100 points ; Final Exam – 150 points
2. Assignments – Up to 100 points; Paper and Presentation – 50 points
3. Total Available: About 400
4. Grading will be  A >= 90%, B+ >= 85%, B >= 80%, C+ >= 75%, C >= 70%, D >= 50%, F < 50%

.

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 #0

Send me an e-mail with subject COT6410 containing
(1)where and when you took Discrete Structures II or its equivalent.

(2) your area(s) of strong research interests.

There is no actual credit for this, but it establishes the lines of communication.

Due: 8/27 by midnight

1. Solved, solvable, unsolved, unsolvable, re, non-re
2. Hilbert's Tenth
3. Lots about problems and their complexity
4. Models of computation
• Turing machines
• Register machines
• Factor replacement systems (FRS)
• Petri Nets
• RM simulated by Ordered FRS
• FRS equivalent to Petri Nets (ordered and unordered)

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

Assignment #1

Show that prfs are closed under Fibonacci induction. Fibonacci induction means that at each induction step, y+1, after calculating the two base values is computed using the y-th and (y-1)st values. The formal hypothesis is:

Assume g1, g2 and h are already known to be prf, then so is f, where

f(x,0) = g1(x); f(x,1) = g2(x)
f(x,y+1) = h(f(x,y),f(x,y-1))

Hint: The pairing function is useful here.

Due: September 16 (at start of class)

1. More equivalences
2. Final steps of equivalence
3. Universal machines
4. Consequences of equivalence
5. Undecidability (Halting Problem, shown by diagonalization)
6. Notation matching (mine versus book'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
13. Diagonalization revisited (set of algorithms, Ko or Lu, is non-re)
14. Quantification and non-re sets
15. Reduction
16. Classic sets Ko (Lu), NON-EMPTY (Lne), EMPTY (Le)
17. Reducibility and degrees (many-one, one-one, Turing)

    Assignment #2

    1. For the sets in a) and b), write a set description that involves the use of a minimum sequence of alternating quantifiers in front of a totally computable predicate (typically formed from STP and/or VALUE). Choosing from among (REC) recursive, (RE) re non-recursive, (Co-RE) co-re, non-recursive, (HU) non-re/non-co-re, categorize each of the sets based on the quantified predicate you just wrote. No proofs are required.  The following is a sample answer:
    Sample.)    S = { f | f(x) diverges for all x }
          Co-RE since f is in S   iff   for all <x,t> [ ~STP( x, f, t )]
    a.)  A = { f |  domain(f) is infinite }
    b.)  B = { f | f(x) > x for at least one value x }
    c.)  C = { <f,x> | f(x) > x whenever f(x) converges }

    2. Consider the set of indices SemiConstant = { f | |range(f)| = 1  }. Use reduction from Halting Problem to show that SemiConstant is undecidable (not recursive).
    

    Due: 9/23

1. Complete re set (K and Ko as examples)
2. Lr = { x | dom[x] is recursive }
3. Lnr = { x | dom[x] is not recursive }
4. Rice's Theorem
5. "Picture" proofs
6. 
   

Assignment #3

1. Show that K <=m SemiConstant = { f | |range(f)| = 1  }. To do this, define a total recursive function g, such that index f is in K iff g(f) is in SemiConstant. Be sure to address both cases (f in & f not in).
2. What, if anything, does Rice’s Theorem have to say about the following? In each case explain by either showing that all of Rice’s conditions are met or convincingly that at least one is not met.
a.) SemiConstant = { f | |range(f)| = 1  }
b.) BOUNDED = { f | there is a g such that for all x [ if f(x) converges then g(x) > f(x) ] }


Due: 9/30

1. Real-Time and Mortal Machines
2. END OF MATERIAL FOR EXAM#1
3. Introduction to rewriting systems (Thue, Post)
4. Post Canonical Forms
5. Semi-Thue systems
6. Word problems
7. Simulating Turing Machine by Semi-Thue System
8. Simulating by Thue Systems
9. Grammars and re sets
   
10. Review and go over sample questions
11. Sample Exam
12. Sample Exam Key
    

1. Exam #1 (Tuesday)
2. Unsolvable problems related to context-free grammars/languages
3. Post Correspondence Problem
4. Ambiguity of CFGs
5. Non-Emptiness of CFL Intersections
6. Context-Sensitive Grammars and Unsolvability Results

1. Valid (CSL) and Invalid Traces (CFL)
2. Intersection and Quotients of CFLs
3. Details on Valid (CSL) and Invalid Traces (CFL)
4. Intersection of CFLs revisited
5. Quotients of CFLs revisited
6. Type 0 grammars and Traces
7. L = all string over an alphabet
8. L=L^2 for L a CFL
9. Revisit Set Real-Time (Constant-Time)
10. Real-Time and Mortal Machines
11. Finite Power Problem for CFLs
12. Propositional Calculus
13. Note: 10/15 is the Withdraw Deadline

    Assignment #4 

        Prove that PCP is decidable over a one-letter alphabet. Do so by presenting a detailed algorithm that solves and one-letter instance of PCP.

Week#9: (10/19, 10/21) -- Notes

1. Basics of Complexity Theory
2. Verifiers versus solvers
3. NP as verifiable in deterministic polynomial time
4. P as solvable in deterministic polynomial time
5. NP as solvable in non-deterministic polynomial time
6. Million dollar question: P = NP ?
7. Some NP problems that do not appear to be in P: SubsetSum, Hamiltonian Path, k-Clique
8. Concepts of NP-Complete and NP-Hard
9. Canonical NP-Complete problem: SAT (Satisfiability)

1. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
2. 3SAT as a second NP-Complete problem
3. 3SAT to SubsetSum reduction
4. Partition equivalence to SubsetSum
5. Key to Exam#1
6. Prep for Exam#2

    Assignment #5 

        Assuming a 3SAT expression (a + ~b + c) (b + b + ~c),  show the reduction from 3SAT to Subset-Sum.

1. Exam#2 (Tuesday)
2. Reduction techniques
3. Isomophism of k-Coloring with k-Register Aloocation of live variables
   
4. Reduction of 3SAT to k-Vertex Cover
   
5. Scheduling on multiprocessor systems
6. N processors, M tasks, no constraints
7. 2 processor scheduling -- greedy first fit, greedy best fit,  sorted, optimal
8. Greedy versus optimal ((N+1)/N)
   
9. Precedences (lists, delays, preemption)
10. Anomalies (reducing preceeedence, increasing processors, reducing times)
11. Unit Execution Time: Trees, forest, anti forests
12. UET: DAGs and m=2
    

        See Pages 482/483 of Notes

1. Alliances and Secure Sets
   
2. Fixed Parameter Tractable (FTP)
3. Note that you must send me your presentations at least 2 days before you present)
   
4. Thursday, November 11, is a holiday
   

1. co-NP
2. P = co-P ; P contained in intersection of NP and co-NP
3. NP-Hard
4. QSAT as an example of NP-Hard, possibly not NP
5. Presentation (Losert)
   

Week#14:(11/23) -- Notes 

1. Presentations (Fontaine, Warner)
2. Thursday, November 25, is a holiday

Week#15:(11/30, 12/2) -- Notes 

1. Presentations (Miller, Riggs)
   
2. All papers related to presentations are due at 6:00PM on 12/2. 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.
   
3. Your papers must include one to two questions you would aks of your audience
4. Key to Exam#2
5. Sample Final Exam Questions
6. Several of Dr. Dutton's Final Questions 
• For graph coloring, for example, we showed in class that unless P = NP,  there is no polynomial time algorithm that can guarantee a solution that is within any fixed constant of the optimal. Use that problem, or one of your choosing, to prove that statement.
• What is the difference between proving a problem is NP-Hard and proving a problem is NP-Easy (or, equivalently, NP-Equivalent)? 
• The power of "reductions" is critical to the areas of Complexity and Computability. Especially: constructing them in the "right" direction. Consider the decision problem asking if there is a coloring of a graph with at most k colors, and the optimization version which asks what is the minimum coloring number of a graph. (You may choose your own favorite pair of problems if you choose). You can reduce in both directions. So, do that. Make sure you carefully explain for each direction just what it is that you are proving. 
• Draw a neatly labeled picture of the "world of NP," including its surroundings. Neatly label it and give a short (one or so) sentence describing what each is.
7. Discussion of function problems. Review for Final exam

Final Exam; Tuesday December 7; 4:00PM to 6:50PM in HEC118