Introduction to Theory of Computation (COMP 3803)
Fall 2021
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel(@scs.carleton.ca)
Lectures:
- Official lecture times: Tuesday and Thursday, 16:05 - 17:25am.
- There won't be live lectures. Instead, links to pre-recorded video
lectures are posted in the section "What was done in class".
Fall term:
- First lecture is on Thursday September 9.
- October 25-29: Fall break, no classes.
- Last lecture is on Thursday December 9.
Office hours:
- Office hours will start on Monday September 13 and will be online.
- Michiel Smid:
Monday and Wednesday 10-11am, on Google Meet, click on the name.
- Marc Vicuna:
Tuesday and Thursday 10-11am, on Zoom, click on the name.
Meeting ID: 983 8610 1683, passcode: theory
Course objectives:
Theoretical aspects of computer science.
Topics covered include:
Formal languages and automata theory (regular languages, finite
automata, context-free languages, pushdown automata),
computability theory (Turing machines, Church-Turing Thesis,
decidability, Halting Problem).
Textbook:
Important dates:
- Assignment 1: posted September 23, due October 7
- Assignment 2: posted October 7, due October 21
- Midterm: Thursday November 4, online, during the official lecture
time
- Assignment 3: posted November 11, due November 26
- Assignment 4: posted November 25, due December 10
- Final exam: Wednesday December 22, 9-11am, online
Grading scheme:
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
Assignments:
- Late assignments will not be accepted.
- You are encouraged to use
LaTeX to type
your solutions. In case you want to learn LaTeX,
here is a tutorial.
- You can use the freely available
Ipe
drawing editor to make figures.
- Each assignment must be submitted as one single PDF file through
Brightspace.
- You can type your solutions, or write them by hand and scan them
(for example, using a scan app on your phone or using a real
scanner).
- Assignment 1 is due Thursday October 7, before 23:59.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here and
here are the figures.
- Here are the solutions
for Assignment 1.
- Assignment 2 is due Thursday October 21, before 23:59.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here is the figure.
- Here are the solutions
for Assignment 2.
- Assignment 3 is due Friday November 26, before 23:59.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions
for Assignment 3.
- Assignment 4 is due (NEW!) Friday December 10, before 23:59.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions
for Assignment 4.
Midterm:
- The midterm will be on Thursday November 4, between 3:50pm and
5:40pm.
- Sign in to Brightspace on Thursday November 4 by 3:50 and click
the Midterm link to begin. If you have trouble finding the link, go
to Tools-->Quizzes. Once you start, you have 90 minutes.
- It will be a multiple-choice exam with 18 questions. There will only
be questions about regular languages. Thus, you are supposed to know
everything that was done in class up to, and including, the pumping
lemma, as well as the first two assignments.
- Here is an old midterm so that
you get an idea of what to expect.
Final exam:
- The final exam will be on Wednesday December 22, between 8:50 and
11:10am.
- Sign in to Brightspace on Wednesday December 22 by 8:50 and click the
Final Exam link to begin. If you have trouble finding the link, go
to Tools-->Quizzes. Once you start, you have 120 minutes.
- The final exam will be multiple choice. There will be 25 questions
about every topic that we covered in class and in the assignments.
- Here is an old exam. Note that
this was a 3-hour exam.
Academic Integrity (New, Please Read):
As of 2020, there are new penalties in place for academic integrity
violations. These will be issued by the Associate Dean (Undergraduate
Affairs) of Science to students who copy, in whole or in part, work
they submit for assignments.
- First offence, first-year students (less than 4.0 credits completed):
No credit for assessment(s) in question, or a final grade reduction of
one full letter grade (e.g., A- becomes B-), whichever is a greater
reduction.
- First offence (anyone else): A grade of F in the course.
- Second offence (anyone): A grade of F in the course and a one-term
suspension from studies.
- Third offence: Expulsion from the University.
Note: While these are the standard penalties, more severe penalties may
be applied when warranted. For more information, click
here.
What was done in class:
- September 9:
- September 14:
- September 16:
- Union/intersection/complement of regular languages is regular;
regular operations: union, concatenation, and star (Section 2.3);
- Video
lecture 3.
- September 21:
- Nondeterministic finite automata (Sections 2.4.1, 2.4.2, and
2.4.3), definition of nondeterministic finite automaton
(Section 2.4.4).
- Video
lecture 4.
- September 23:
- Equivalence of deterministic and nondeterministic finite
automata (Section 2.5).
- Video
lecture 5.
- September 28:
- Closure under the regular operations (Section 2.6);
Exercise 2.18.
- Video
lecture 6.
- September 30:
- Regular expressions (Section 2.7); how to convert a regular
expression to an NFA (Section 2.8.1).
- Video
lecture 7.
- October 5:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video
lecture 8.
- October 7:
- October 12:
- Pumping Lemma, more examples (Section 2.9); introduction to
context-free grammars (Section 3.1).
- Video
lecture 10.
- October 14:
- Context-free grammars (Section 3.1); examples of context-free
grammars (Section 3.2).
- Video
lecture 11.
- October 19:
- More examples of context-free grammars (Section 3.2); converting
a DFA to a CFG, every regular language is context-free
(Section 3.3); Chomsky Normal Form (Section 3.4; definition of
CNF only, no details).
- Video
lecture 12.
- October 21:
- Deterministic pushdown automata; properly nested parentheses
(Sections 3.5, 3.6.1).
- Video
lecture 13.
- October 25-29: Fall break, no classes:
- November 2:
- Deterministic pushdown automata (Section 3.6.2);
nondeterministic pushdown automata (Section 3.6.3).
- Video
lecture 14.
- November 4: Midterm.
- November 9:
- Converting a context-free grammar to a nondeterministic pushdown
automaton (Section 3.7); statement of the pumping lemma for
context-free languages (Section 3.8); first example in
Section 3.8.2.
- Video
lecture 15.
- November 11:
- Proof of the pumping lemma (Section 3.8.1); example of a
language that is not context-free (Section 3.8.2).
- Video
lecture 16.
- November 16:
- One more example of a language that is not context-free
(Section 3.8.2).
-
Turing machines
(Section 4.1); accepting palindromes using a one-tape Turing
machine (Section 4.2.1).
- Video
lecture 17.
- November 18:
- Accepting palindromes using a two-tape Turing machine
(Section 4.2.2).
- More examples of Turing machines (Sections 4.2.3, 4.2.5);
equivalence of multi-tape Turing machines and single-tape Turing
machines (Section 4.3).
- Video
lecture 18.
- November 23:
- What is an algorithm? Church-Turing Thesis (Section 4.4);
definition of a language being decidable (Section 5.1);
the languages A_DFA, A_NFA, and A_CFG are decidable; every
context-free language is decidable (Sections 5.1.1, 5.1.2,
5.1.3).
- Video
lecture 19.
- November 25:
- November 30:
- The Halting Problem revisited (Section 5.2.1); Rice's Theorem
(Section 5.3).
- Video
lecture 21.
- December 2:
- December 7:
- Language A is decidable if and only if both A and its complement
are enumerable (Section 5.7); Halt is enumerable, but its
complement is not enumerable (Section 5.7); both EQ_TM and its
complement are not enumerable (Section 5.8); the set of all
enumerable languages is countable (Section 5.6.1); the set of
all languages is not countable (Section 5.6.2).
- Video
lecture 23.
- December 9:
Tentative schedule, based on the last time I taught this course.