SE 4I03: Theoretical Foundations of Computation
Fall 2003
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Information
- Course outline: Models of computation: finite
automata, regular expressions, context-free grammars, push-down
automata, and Turing machines. Relationships between these models
(e.g., finite automata are equivalent to regular expressions).
Determinism and non-determinism in computations, and quantum
computers. Limitations of the different models (e.g., Pumping Lemma
for showing that a language is not regular, and the Halting Problem).
Recursive and recursively enumerable languages, Rice's theorem.
Feasible problems, intractable problems, and the complexity classes P
and NP. Click here for a more
detailed course syllabus.
- Textbook:
Introduction to Automata Theory, Languages, and Computation,
by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman,
SECOND EDITION:
- Check this web page regularly for announcements. Some documents
will be available in PostScript; if you need a PostScript previewer,
go to Ghostview Software.
- Previous versions of this course:
2001 and
2002.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 8: This year's exam has been posted below.
- Dec 3: Today's Office Hours Change of Time: today's office
hours will take place one hour later, from 3:30 until 4:20, still in
room ITB-222, as most students are writing an exam until 3:30.
- Dec 1:
- Test 3 is ready to pick up. Please come by my office
(ITB-214)---the tests are going to be in a box in front of my door.
- Test 3 average is 28/50.
- Test 3 comments: Tyler and
Marc.
- Click here to check your term
marks, listed by student number. Please let me know if there are
mistakes (I may ask you to bring the relevant test). If you have
given me a note from the Dean's office regarding a missed test, it
should say "note" in the relevant column.
- There are going to be "double" office hours on Wednesday (Dec
3rd), 2:30--3:20 in ITB-222 (both Marc and Tyler are going to be there
to deal with marking issues in test 3). Marc will hold his usual
office hour today (Monday) as well.
- Nov 25: Problem Set 6 posted below.
- Nov 25: Click here for the slides
from today's lecture.
- Nov 21: Solutions to Test 3 have been posted below.
- Nov 19: Note that there is a mistake in question 4 on Problem Set
5: the value should be "20" not "18".
- Nov 19: CLick here for a note on
the Pumping Lemma for Context-Free Languages by Marc Bender.
- Nov 18: Click here for the slides
from today's lecture.
- Nov 14: Test 2 average is 33/50.
- Nov 14: Test 3:
- Nov 21, 9:30--10:20.
- Just as Test 2, Test 3 will be written in ABB/B163.
- Problem Set 5, posted below, contains the exercises for Test 3.
- Test 3 will be on Chapters 8 and 9 in the textbook.
- Nov 14: Test 2 marking scheme:
- Nov 14: Click here for Marc's
marking scheme for Test 1.
- Nov 12: Problem Set 5 (Chapters 8 and 9) has been posted below.
- Nov 12: Click here for today's slides.
- Nov 5: I am posting this a little late, but here are the marking
scheme and comments from Test 1 by Tyler. Marc's comments are coming
up.
- Nov 4: Test 2 with solutions has been posted below.
- Oct 27: Problem Set 4 (Chapter 7 in the textbook) has been posted
below. Test 2 will be on the material in chapters 5, 6, and
7---Context-Free Languages. The relevant problems are included in
Problem Sets 3 and 4.
- Oct 24: Test 2 CHANGE to: Nov 4th, 9:30--10:20 in
ABB/B163.
- Oct 16: Problem set 3, containing exercises for chapters 5 and 6,
has been posted below.
- Oct 11: Just a reminder that there is no class on Oct 14
(Tuesday).
- Oct 9:
- Test 2: October 31st, 9:30--10:20, in ABB/B163
- Test 3: November 21st, 9:30--10:20, in ABB/B163
- Oct 3: Test 1 with solutions has been posted below.
- Sep 25: Problem Set 2 has been posted below. Test 1 will be
based on the exercises in Problem Set 1 and 2.
- Sep 23: Test 1: Friday, October 3. The tests are going to
be written in the usual classroom, during the usual lecture hours
(9:30--10:20am). The test will comprise chapters 2,3,4 in the
textbook. In particular, you are responsible for the material
relevant to the exercises.
- Sep 16: Problem Set 1 has been posted below.
- Sep 12: The office hours will be held in ITB/222 on the
following times:
- Mondays: 5:00--5:50
- Wednesdays: 2:30--3:20
The TAs for the course are:
You should make good use of the TA office hours. As was explained in
class, you are responsible for all the assigned exercises, and even
though you do not have to hand them in, the tests will be based on
them. Thus, to prepare for the tests, you should know how to do all
the assigned problems.
Tests and suggested exercises: