Instructor:
Charles Hughes; Contact: charles.hughes@ucf.edu;
Use Subject COT6410 Office Hours: Tuesday
10:45AM-11:45AM; Thursday 12:15PM-1:30PM until week of February 22
Tuesday/Thursday 10:45-11:45AM from week of February 22 to end of
semester OH Zoom Link: https://tinyurl.com/y3ffvbm3
GTA: Daniel Daniel Gibney; Contact:
dangibney@knights.ucf.edu; Use Subject COT6410 Office Hours:MW
1:30PM-3:00PM OH Zoom Link:https://tinyurl.com/y2y2lmum
Required Reading: All class
notes linked from this site.
Recommended Reading:
Sipser, Introduction
to the Theory of Computation 3rd Ed., Cengage
Learning, 2013.
Hopcroft, Motwani&Ullman, Intro to Automata Theory, Languages and Computation 3rd
Ed., Prentice-Hall, 2006.
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.
Oded Goldreich, Computational
Complexity:
A Conceptual Approach, Cambridge University Press,
2008.
Oded Goldreich, P, NP, and
NP-Completeness: The Basics of Complexity Theory,
Cambridge University Press, 2010.
Arora&Barak, Computational
Complexity:
A Modern Approach, Cambridge University Press, 2009.
Assignments: 6 for sure and maybe a seventh; Paper + Video
Presentation with Slides
Exams: Midterm and Final.
Exam Dates (Tentative): Mid Term: Thursday,
March 11; Withdraw Deadline:Friday, March 26; Spring Break: April
11-18; Final: Thurs., April 29, 7:00AM-9:50AM
Evaluation (Tentative):
Mid Term: 125 points; Final Exam: 125 points (balance between
weights will be adjusted in your favor)
Assignments: 75 points;
Individual Paper Reviews and Presentations: 125 points
Extra -- 50 points used to increase weight of best exam,
always to your benefit
Total Available: 500
Grading will be A >= 90%, B+ >= 85%, B >= 80%,
C+ >= 75%, C >= 70%, D >= 50%, F < 50%; minus grades
might be used.
State minimization using O(| Q | 2) table.
Note alphabet is constant size.
Why is this just O(| Q | 2)
cost, rather than O(| Q | 3)
More closure properties
Reversal and regular equations
Substitution
Quotient using NFA
Quotient redone use meta technique based on substitution
and intersection with Regular Sets
Meta technique for Init (Prefix), Last, (Suffix) Mid
(Substring), Exterior, etc.
Closure under min and max and discussions of various
Reaching Algorithms (Depth-First Search)
Pumping Lemma for Regular Languages (Pigeon Hole Principle)
Adversarial Nature of use of PL to show a language is not
Regular
Myhill-Nerode Theorem
Right invariant equivalence
relations of finite index
Specific right invariant
equiv. relation, RL for language L
Myhill-Nerode as proof of min
DFA uniqueness
Myhill-Nerode as a tool to show
languages are not regular.
The chosen language is
L = { an bm | 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.
Finite State Machines
(Transducers): Mealy versus Moore Model
Decision Problems for Regular
Languages
Introduction to Grammars (Regular
and CFG mainly)
Regular Grammars and Regular
Languages
Rules of Form A →a;
A → aB; A →
Define Right Linear Grammars
Conversion of DFA to Equivalent
Right Linear Grammar
Conversion of Right Linear
Grammar to Equivalent NFA
Equivalence of Right and Left
Linear Grammars as Generators of Languages
Why We Cannot Mix Right and Left
Linear Grammars and stay in Regular Languages
Extended Right and Left Linear
grammars Using String of Terminals
Use of context free grammars in
parsing and notion of Ambiguity
Bottum-Up (Shift-Reduce and
conflicts)
Top-Down (Predictive and guessing
-- recursive descent)
Review of reduced CFGs
Remove Rules: Null, Unit,
Non-Productive, Unreachable (order of removal matters)
Chomsky Normal Form (CNF)
A -> a and A -> BC are only
allowed forms
The use of CNF in the
Cocke-Kasami-Younger O(N3) parsing of CFLs generated
by CNFs
Bottum-Up technique
Great Example of the value of
Dynamic Programming
Pumping Lemma for CFLs
Show L1 = { an bn
cn | n i> 0 } and {L2 = { ww | w is in {a,b}+
} are not CFLs
CSG for L
Non-closure of CFLs under
intersection and complement
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 strings and we have L1
complement.
Decision problems for CFLs:
is L(G) empty or finite/infinite are fine
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. https://mathworld.wolfram.com/FRACTRAN.html
Decision vs Optimization
Problems (achieving a goal vs achieving min cost)
Polynomial == Easy;
Exponential == Hard
Polynomial reducibility
Verifiers versus solvers
P as solvable in
deterministic polynomial time
NP as solvable in
non-deterministic polynomial time
NP as verifiable in
deterministic polynomial time
Concepts of NP-Complete and
NP-Hard
Canonical NP-Complete
problem: SAT (Satisfiability)
Some NP problems that do not
appear to be in P: Graph Coloring, Vertex Cover, SubsetSum
Million dollar question: P =
NP ?
Boolean expressions:
Tautologies, Satisfiability, Truth Tables
Axiomatic Systems for
propositional logic: Substitution and modus ponens versus
refutation/resolution
Unsolvability of deducibility
in fragments of propositional calculus
Construction that maps every
problem solvable in non-deterministic polynomial time on TM to
SAT
Week#11:(3/23, 3/25, (3/26
is Withdrawal Deadline)) -- Complexity Theory
SAT is polynomial reducible
to (<=P) 3SAT
3SAT as a second NP-Complete
problem
Integer Linear Programming
Note: 3/26 is the Withdraw
Deadline
3SAT <=P SubsetSum
SubsetSum <=P Partition
Partition equivalence to SubsetSum
Discussion of group
presentations
Reduction of 3SAT to k-Vertex
Cover
3-SAT to 3-Coloring
Isomophism of k-Coloring with
k-Register Allocation of live variables
Scheduling problems
introduced
Scheduling on multiprocessor
systems
Scheduling problems (fixed
number of processors, minimize final finishing time)
N processors, M tasks, no
constraints
Partition and scheduling
problems
Greedy heuristics
2-processor scheduling --
greedy based on list, sorted long to short, sorted short to
long, optimal. Tradeoffs.
You will each, individually, develop a paper and a
presentation, based on an existing research paper, just as
if you had to present to your peers and advisors. In
addition to presenting the results and the way in which
these were proven, you should comment on the paper's
importance, readability, and replicability, and even its
validity if you question that, just as if you were a journal
or conference reviewer. Your report must be a tutorial on
the topic of the paper so those with less time to delve into
the paper can get a strong sense of the results and the
context of those results. Specifying new open problems that
you see as interesting is also a goal, but may not be
attainable for some of these. The length of your paper is
6 to 12 pages double-spaced, 1" margins all around, using
either Times Roman or Calibri 11 point, or Arial 10-point.
The references are in addition to the narrative and appear
on separate pages that do not count against the 6 to 12-page
limit. Images may be used but if the total number of images
exceeds a page, then all past that one-page aggregate will
lead to a requirement for additional text. The presentation
slides must be designed to support your 8 to 10-minute
video. This means that there are likely 10 to 15 slides.
Towards the end of the
semester you give a presentation to a small group of other
studesnt and they to you. This will be done in a breakout Zoom
session where your presentation and any questions/answers are
captured. You may, if you wish, create the presentation in
advance and share a video, but you need to be there to
participate in the Q&A and to hear other students'
presentations. To do this, I assume you all have access to a
webcam and use Zoom or a similar tool that captures your
slides and you in one extended screen. Let me know if you lack
a webcam. Note that you will be asked to provide some brief
feedback to me on the papers of your fellow students taking
part in teh same breakout.
I have placed about 65 sample
papers out there at SampleTopics.
You may choose from any of these except for ones that have
already been taken. You may also choose your own separate from
these with permission from me. In general, the minimum page
length in IEEE 2-column format is 8 pages or 10 pages in
single column, single-spaced layout. The prefix CLAIMED_NAME
means NAME has already chosen that. Please send me an email to
assure you succeed in making your "claim."
Realize that many of these
suggested papers will be from arXiv and, while arXiv is a
fantastic source, it is not refereed so if you question the
validity of some result, that is actually a reasonable outcome
so long as you present their approach and your
counterarguments just as if you were a reviewer.
This folder
contains some examples (papers and presentations) from past
semesters.
Final Paper
and PowerPoint
Read above. Its weight is 125 points. The
split is nominally 75 for the paper and 50 for your
presentation
and feedback on other's presentations you
provide.
Due: 4/23
Assignment #5
See Webcourses
(Assignment # 5) for description Sample with Key
Knapsack (relation to SubsetSum), Dynamic Programming
Pseudo-polynomial Solution
Bin packing (fixed capacity, minimize number of bins)
Pseudo polynomial-time solution for Knapsack using dynamic
programming with changed parameters,
n*W versus 2^n but W = 2^log(W). This kind of problem is called
Weak NP Complete. I'll chat about that later.
Tiling the plane and Bounded Tiling
Bounded PCP
Co-NP
Reduction techniques
P = co-P ; P contained in intersection of NP and co-NP
NP-Hard
QSAT as an example of NP-Hard, possibly not NP
NP-Hard problems are in general functional not necessarily
decision problems
NP-Complete are decision problems as they are in NP
NP-Easy -- these are problems
that are polynomial when using an NP oracle
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
Optimization versions of SubsetSum and K-Color
Validity of SubsetSum
optimization reduction to SubsetSum Decision Problem Oracle
Assignment #6
See
Webcourses (Assignment # 6) for description Sample with Key
P = (NP intersect Co-NP) is interesting analogue to
intersection of RE and co-RE but may not hold here
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)
Khot's Conjecture and its implications
Week#14: Spring
Break
Week#15: (4/20, 4/22)
Review for exam
On 4/22 we will have the breakout
sessions in which you give your presentations and hear those of
a few other of your fellow students (typically five or six per
breakout room). These will be set up prior to the 22nd.
email:
charles.hughes@ucf.edu
