SE 4I03: Theoretical Foundations of Computation
Fall 2002
- 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.
Announcements:
- April 2003: Click here for the
2002 deferred exam.
- Dec 17 2002: Click here for the 2002 final exam.
- Dec 6: Click here for a practice
exam (given in 2001 as a deferred exam).
- Nov 29: Once again, make sure that you check your term marks (see
below). I will not post the final exam marks, or the
final mark for that matter, on the web, since the Registrar's Office
is responsible for posting the final marks.
- Nov 29: For the Turing machines portion of the course, you are
responsible for all of Chapter 8 and 9, except for 8.5.
- Nov 27: Click here to see your term
mark. If there is a discrepancy, please bring the relevant piece of
work to class.
- Nov 26: Click here for slides from
today's lecture.
- Nov 26: Office hour announcements:
- If you have marking concerns about Assignment 4, please see Tylor
on Friday, December 6 usual time and place. There
will be no office hours on Nov 29.
- You can pick up Test 2 on Wednesday, Nov 27, in ITC222, at 11:30.
Ebtesam will be there from 11:30 until 1:30. She will not be
available later to discuss Test 2, so please pick up your test then,
and resolve your marking concerns right away.
- Nov 21: If you took my book by mistake, please return it
by putting it in my mailbox!!! I got the book back, thanks!
- Nov 19: The solutions to Assignment 4 have been posted below.
- Nov 15: Assignment 4 has been extended to Tuesday, Nov 19. Test
2 is going to be written in class on Friday Nov 22. To prepare for
Test 2, do all the suggested exercises, review the class notes, and
the assignments 3 and 4. The sections in the textbook are the
following:
- Chapter 5: all sections except 5.3
- Chapter 6: all sections except 6.4
- Chapter 8: all sections except 8.5 and 8.6
- Old Announcements
Tests, Assignments, and Suggested Exercises:
- Assignment 1 (Revised Sept 10) and
solutions
- Suggested exercises: pp 53,54, 2.2.1--11
- Suggested exercises: pp 66-68, 2.3.1--7
- Assignment 2 and
solutions
- Suggested exercises: 2.5.1--3
- Suggested exercises: 3.1.1--5
- Suggested exercises: 4.1.1--2 and 3.2.4--7
- Suggested exercises: 3.2.1--2
- Suggested exercises: 3.4.1--4
- Suggested exercises: 4.2.1, 4.3.1--5, 4.4.1--2
- Test 1 with Solutions
- Assignment 3 (revised Oct 24: corrected
due date--Oct 31--and replaced "regular expression" by "boolean
expression" in Q2), and solutions.
- Suggested exercises: 5.1.1--3
- Assignment 4 (Last One!) and
solutions
- Suggested exercises: 5.4.1--3
- Suggested exercises: 6.1.1
- Suggested exercises: 6.2.1--2, 6.2.5--8
- Suggested exercises: 6.3.1--4
- Suggested exercises: 8.2.1--4
- Suggested exercises: 9.1.1--3, 9.2.1--6
- Test 2 with Solutions
- Suggested exercises: 9.3.1--3, 9.5.1--2
- Click here for a practice exam.
- Click here for the exam.