Assignments: 6 for sure and maybe a seventh; Paper + Video
Presentation with Slides
Exams: Midterm and Final.
Exam Dates (Tentative): Mid
Term: Tuesday, March 7 in HEC-103; Withdraw
Deadline: Friday, March 24; Spring Break: March 13-19; Final:
Thurs., April 27, 7:00AM-9:50AM in HEC-103.
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.
More Discussion of Pumping Lemma for Regular Languages
(Sipser 1.4; HMU 4.1)
Adversarial Nature of use of PL to show a language is 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 (Sipser p. 87)
Decision Problems for Regular
Languages (HMU 3.4; HMU 4.3
Introduction to Grammars (Regular
and CFG mainly) (Sipser 2.1;
Regular Grammars and Regular
Languages (HMU p. 180)
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
Context Free Grammars (A
x where x
(V
)*
) (Sipser 2.1; HMU 5.1)
Use of context free grammars in
parsing and notion of Ambiguity (Sipser 2.1; HMU 5.2, 5.4)
Bottom-Up (Shift-Reduce and
conflicts)
Top-Down (Predictive and guessing
-- recursive descent)
Review of reduced CFGs (HMU 7.1)
Remove Rules: Null, Unit,
Non-Productive, Unreachable (order of removal matters)
Chomsky Normal Form (CNF) (Sipser
2.1; HMU 7.1)
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 (HMU 7.4)
Bottom-Up technique
Great Example of the value of
Dynamic Programming
Pumping Lemma for CFLs (Sipser 2.3;
HMU 7.2)
Show L1 = { an bn
cn | n > 0 } and L2 = { ww | w is in {a,b}+
} are not CFLs
Non-closure of CFLs under
intersection and complement (Sipser 2.3)
Consider
L3 = {
an bn cm | n,m > 0 }, L4
= {
am bn cn | n,m > 0 },
L1 = L3 ∩ L4
L3 and L4 are CFLs, [ For L3 S->Sc | Tc; T->aTb | ab
], but intersection is not
Consider the complement of L2 { 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 L2
complement.
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
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.
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
students 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 55 sample
papers at Sample
Topics. 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.
I also put out a folder that contains some
examples (papers and presentations) from past semesters.
Final Paper
and PowerPoint
Read above and at
Webcourses. Its weight is 125 points.
The split is nominally 75 for the paper and 50 for your
presentation.
Due: 4/21
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)
Khot's Conjecture and its implications
Post's Tag Systems -- deterministic with just one rule per
letter in alphabet; first letter determines action; always
delete the same number of characters from from prefix and add
associated right hand side of rule as postfix.
Exam Review (emphasis on Formal Languages and Computability
topics)
Week#15: (4/18, 4/20)
The old videos for this week are: Day29.mp4
New Videos: Day29.mp4
Exam Review (emphasis on
complexity topics and sample exam questions)
On 4/20 we will have the breakout
sessions in which you give your presentations and hear those of
a few of your fellow students (typically five per breakout
room). These will be set up prior to the 20th.
email:
charles.hughes@ucf.edu
