Comp Sci 2MJ3: Theory of Computation
Fall 2011
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Instructor's office hours: Thursdays, 2:30-4:30, starting
on Thursday September 22.
- Course Outline
(updated on September 12, 2011)
- Time: lectures on Mo, We, Th, 1:30-2:20, in
ETB/235.
- Tutorials: Th, 3:30-4:20, JHE/A102, starting on September 22.
The TA is Dragan Rakas, rakasd@muss.cis.mcmaster.ca
- 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.
- Textbook:
Introduction to the Theory of Computation, 2nd Edition, by Michael
Sipser:
Book's web
page
- Check this web page regularly for announcements.
- Previous versions of this course:
2006,
2009,
2010.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 6: I will be in the office most of the day on Wednesday (Dec
7) and Thursday (Dec 8) if you have any questions, or want to pick up
your test. Send me an email if you need to make an appointment for a
particular time.
- Nov 30: Solutions to test 6 posted below.
- Nov 22: The problems related to test 6, the last test!, have
been posted below.
- Nov 21: The solutions to test 5 have been posted below.
- Nov 14: The problems related to test 5 (from chapter 7) have
been posted below.
- Oct 31: Problems related to test 4 have been posted below;
depending on how far we go this week, there may be some more problems
added (from chapter 5).
- Oct 28: I am using Google+
to post news, articles, jobs for students I hear about, etc. If you
are interested please use this link (note that this is something I do
to keep in touch with former and current students, to let them know
about things of general interest — it is not part of this
course):
https://plus.google.com/i/3njsWA-BYKU:hCqvjEtcR7M
- Oct 26: Solutions to test 3 have been posted below.
- Oct 16: The problems for context-free languages (chapter 2 in
the textbook) have been posted below; these are the exercises/problems
that you need to do in order to prepare for test 3 on October 24.
- Oct 8: The solutions to test 2 have been posted below.
- Sept 26: Next week, Oct 3—7, the instructor is away at a
conference. On Monday Oct 3, test 2 will take place as scheduled. On
Wednesday Oct 5, the TA, Dragan Rakas, will have a special tutorial in
the usual lecture time & place. The tutorial will cover the
solutions to test 1 and 2, and any other questions the students might
have. There will be no lecture on Thursday Oct 6; we will make
up for it later.
- Sept 26: Test 1 with solutions has been posted below.
- Sept 16: The first batch of problems has been posted below.
These are the exercises/problems that you should do as preparation for
the test. The test will be based on these problems, and so working
them out is crucial to, first of all, profiting from the course, and
second of all, doing well on the tests.
- The instructor and the TA office hours have been posted above.
The instructor's office hours will take place on
Thursdays, 2:30-4:30, starting on Thursday September 22, in ITB-214. These
will be my regular office hours for the term — please feel free
to make an appointment by email for a different time.
The TA's office hours will be Thursdays, 3:30-4:20, JHE/A102,
starting on September 22.
Problems and tests:
Given that we have 6 tests, and that October 10th is Thanksgiving, and
that tests cannot be scheduled after November 28th, all six tests will
be given on Mondays (to give students the weekend to prepare),
starting Monday September 26. The tests will be written in class, in
the usual classroom — no aids are allowed, and the duration will
be 50 minutes. The aim of the tests is to ensure that students do the
assigned homework, and hence they will be designed based on the
homework. The format, type of questions, and the related homework
will be similar to what was given last year; check the
2010 web page to have an idea
of what to expect.