EECS2001, Fall 2016
EECS2001: Introduction to Theory of Computation
Web page contents:
Instructor: Eric Ruppert
Office: Lassonde Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Lectures: Tuesdays and Thursdays from 16:00 to 17:30 in room 106 of the Life Sciences Building
Tutorials: Mondays from 16:00 to 17:30 in room 106 of the Life Science Building
Email: [my last name]@cse.yorku.ca (Please use a York mail account when sending me email, and start your subject line with "".)
Office hours: The course is over so there are no more office hours.
In this course, you will be invited to develop your ability to think clearly and carefully about computing,
and to improve your skills in expressing those thoughts about computing in a precise way.
By the end of this course, you will be able to do the following things.
- Design machines (e.g., finite automata, Turing machines) to solve specified problems.
The central goal of computer science is the design of algorithms to solve computational problems.
The `machines' that we describe in this course are not physical machines; they are just
ways to formally describe algorithms. We will also talk a bit about how to specify problems formally.
- Design regular expressions and context-free grammars for a given formal language
A formal language is just a set of strings. We will see that they can be used to give
formal specifications of computational problems.
This part of the course looks at some ways to describe these languages in a compact way.
Regular expressions and grammars are also useful in the design of programming languages
and compilers, and in natural language understanding.
- Explain why an object designed according to one of the above two bullets correctly meets its specification
Computer scientists should be able to design solutions for computational problems.
But they must also be able to explain their solution to others. This goal of the course
will help you develop your skills in doing this. You will find that proving that your
solution is correct also helps you find mistakes in your solution.
- Prove simple properties about models of computation (e.g., that the class of regular languages is closed under complement)
Here, we start to develop an overall theory of computing. Rather than thinking about one problem at a time, we look at the class of problems that can be solved by certain kinds of algorithms and prove properties about that class. This gives us deeper insight into how computers can solve problems.
- Demonstrate limits of computing by proving that a problem is not solvable within a particular model of computation
This is one of the most important components of the course. It's important for a computer scientist to know the limitations of computers, to avoid wasting time on trying to solve a task that turns out to be impossible.
- Show how one problem can be reduced to another
This is a skill that computer scientists use all the time. Instead of solving a problem from scratch,
it helps if you can relate it to another problem that has already been solved, and then use the solution
to that second problem to solve the original one.
How to Learn This Material
Some of the skills that you will develop in this course may be quite new to you, and different
from things you have done in previous courses. This is good: it means you're learning new and
(I hope) exciting things. However, it means that you will need practice to master them.
Just participating in classes isn't enough.
There are suggested exercises from the textbook. Web pages for this course in previous terms also
include many more problems to work on. Do lots.
You learn by struggling with problems.
However, if you get too stuck or don't know how to begin,
help is available. Talk to your classmates (however; see the notes below about academic honesty regarding discussing assignment problems with others).
Go to office hours; the instructor and TA are there to help you!
You also learn by making mistakes and getting feedback about them.
Just make sure that you use the feedback to improve your understanding.
Groups of students can
learn a lot by explaining their solutions to the suggested exercises from the textbook to one another and critiquing the solutions
of others. After all, learning how to explain solutions clearly is one of the learning objectives
of this course. Seeing where other students' solutions are unclear to you helps you make
your own explanations clearer.
Be aware that a problem may have many different correct solutions; just because someone's
solution is different from yours doesn't necessarily mean that one of them is wrong.
It takes time to build new skills, so it helps if you work on exercises regularly: don't leave all the work to the days right before a test.
Sometimes students ask for more exercises with worked-out solutions. (The textbook has some,
but maybe not enough.) There is a whole shelf of textbooks that cover the material of this course
in the library (some are recommended below), and many have more examples or exercises with solutions.
|Weekly homework assignments||15%|
|Test 1 ||20%|
|Test 2 ||20%|
|Final exam ||40%|
For each homework assignment, you may either work by yourself or with a partner.
If you work with a partner, the two of you should hand in a single set of solutions with both
of your names on it.
Both partners should work on every problem, since the assignments are intended to
help you learn the material and receive feedback on your work.
If you get stuck when working on a problem, I encourage you to come to office
hours to get help with it.
It is important that you look at the departmental
on academic honesty.
The solutions you hand in should be the work of you and your partner (if you have one).
Thus, if you discuss an assignment problem with anyone other than your partner for that assignment,
you may discuss only the general approach to solving the problem,
not the details of the solution, and you should not take any written notes
away from such a discussion.
Also, you must list on the cover page of your solutions any people (besides your partner) with whom
you have discussed the problems.
While writing your solutions to hand in, you may look at the course textbook and your own lecture
notes, but no other outside sources.
Information may be added to this table thoughout the term.
|First class ||Thursday, September 8|
|Quiz (surnames A-L in CLH C, M-Z in LSB 106) ||Monday, September 19|
|Thanksgiving (no class) ||Monday, October 10|
|Test 1 (surnames A-L in CLH C, M-Z in LSB 106) ||Thursday, October 13|
|Reading day (no class) ||Thursday, October 27|
|Drop deadline ||Friday, November 11|
|Test 2 (surnames A-L in CLH C, M-Z in LSB 106) ||Monday, November 14|
|Last class ||Monday, December 5|
|Exam period ||December 7 to 22|
Michael Sipser. Introduction to the Theory of Computation,
Third Edition. Course Technology, 2012. Errata. (If you have an older edition, it will be fine too.)
Note that the bookstore offers temporary access to an electronic version of the book more cheaply than the price of a hard copy. (However, if you plan to take EECS4115, some instructors use the same textbook for that course.)
If you used Rosen's book, Discrete Mathematics and its Applications, for EECS 1019, it has a chapter on the topics of this course with lots of exercises. (It is chapter 12 in the 6th edition.) This book is available on reserve at the library.
The following list gives other useful references.
- Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
- John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation, Third Edition. Pearson Addison-Wesley, 2007. Solutions to selected exercises and errata can be found on the textbook's web site.
- John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
- Elaine Rich. Automata, Computability and Complexity: Theory and Applications. Pearson Prentice Hall, 2008. Good book for more examples and applications.
- Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes, Fifth Edition. Wiley, 2009.
- Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Dover, 2011.
This schedule is approximate and may be adjusted during the term.
Try not to fall behind in the reading.
The sections refer to the course textbook.
|September 5||0.1-0.4||0.1-0.6, 0.10-0.13 and review exercises|
|September 12||1.1||1.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48 |
|September 19||1.2 ||1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44 |
|September 26||1.3||1.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40 |
|October 3||1.4||1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58 |
|October 10||pages 194-197||4.1, 4.2, 4.3, 4.10, 4.12, 4.13, 4.16, 4.21 |
|October 17||3.1, 3.2||3.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.15, 3.16(a-d), 3.22; 3.10, 3.12, 3.13|
|October 24||3.3, 4.2 ||4.5-4.8 |
|October 31||5.1 (pages 216-220)||5.10, 5.11, 5.13|
|November 7||5.3||5.4-5.7, 5.9, 5.22, 5.23, 5.28-5.30|
|November 14||2.1||2.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.17, 2.19, 2.25, 2.26|
|November 21||2.2, 2.3||2.5, 2.7, 2.10; 2.2, 2.13, 2.30, 2.31, 2.32, 2.35|
|November 28||pages 198-200|| 4.4, 4.5, 4.11, 4.14, 4.31 |
Solutions to tests will be handed out in class. If you missed getting one, ask me for it.
Updated January 3, 2017