Instructor:
Charles Hughes; Contact: charles.hughes@ucf.edu;
Use Subject COT6410 Office Hours: Tuesday
10:45AM-11:45AM; Thursday 12:15PM-1:30PM 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 L = { ww | w is in {a,b}+
} is not a CFL
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.
Closure of CFLs under
substitution and intersection with Regular
Decision problems for CFLs:
is L(G) empty or finite/infinite are fine;
Checking ambiguity, equality to Sigma*, equivalence and
non-empty intersection with another CFL are not
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
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 will place about 50 sample
papers out there at SampleTopics
(not live yet). 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
(to be made live later) 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
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)
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)
email:
charles.hughes@ucf.edu
