Please select which topics you would prefer to be covered in the final lecture.

I will cover them in order of popularity - so don't vote for all topics otherwise your vote will be nullified...

DFAs, NFAs, Regular Expressions

Regular languages, Pumping lemma for Regular Languages, Myhill-Nerode

CFGs, PDAs, Pumping Lemma for CFGs, CKY algorithm

Turing Machines, (Un)decidability

P, NP, and NP-completeness

coNP, PSPACE, PSPACE-completeness

L, NL, logspace reductions

Oracles, Alternation

Proabilistic computation

Approximation and optimization

You can't submit an answer to this poll because you're not part of this course!

Back to top

COMP4141 20T1 (Theory of Computation) is powered by WebCMS3
CRICOS Provider No. 00098G