Web page contents:

General Information

Learning Outcomes

• 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

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.

Marking Scheme

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.

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.

Announcements

• (Jan 3) I have posted exam grades and UNOFFICIAL final grades for the course. (The final grades only become official after they are approved by the department.) You can check your grade with the instruction "courseInfo 2001 2016-17 F". You can stop by my office during the next couple of weeks if you would like to view your exam. (If you want to be sure that I am in my office when you come, you can email me to arrange a time.)
• (Nov 22) I have updated my records of students' grades. Please check yours by typing "courseInfo 2001".
• (Nov 22) There will be a review session on Sunday, December 4 from 14:00 to 16:00 in room 115 of the Chemistry Building. You are invited to come ask any questions you might have before the exam, and you can also listen to answers to other students' questions. I will also be available for office hours on Monday, December 5 and Tuesday, December 6 (exact times to be announced).
• (Nov 22) I will be away the week of Nov 28-Dec 2. There will be guest teachers for the tutorial and lectures. The TA will be holding office hours Monday 12:00-13:00, Tuesday 11:00-12:00 and Thursday 11:00-12:00 in Lassonde 2013. I will still be answering questions by email.
• (Nov 22) The results of the Busy Beaver contest (bonus assignment) are now available.
• (Nov 6) The exam schedule has been posted at the Registrar's web site
• (Nov 5) A bonus assignment has been posted below.
• (Oct 20) There is a typo in the solutions that I handed out for assignment 5. In the definition of s, the last exponent should be p, not p-1. (The same change should be made in the two expressions for xz.
• (Oct 20) The deadline for Assignment 6 will be Oct 31, not Oct 27 as originally announced (because Oct 27 is a reading day).
• (Oct 5) I will have an extra office hour on Wednesday, October 12 from 11:00 to 12:00.
• (Oct 4) For Test 1, students with surnames A-L should go to Curtis Lecture Hall C, and students with surnames M-Z should go to LSB 106 (regular classroom).
• (Oct 3) Grades for Assignment 3 have now been posted. You can use courseInfo to see them (as described below). To see the information that the TA used to grade question 1, use the same procedure as described below for assignment 2, except using the file /cs/course/2001/a3q2.txt.
• (Oct 3) In your answer to part (c) of Assignment 4, you may assume that the alphabet Σ is {a₁, a₂, ..., a_n}.
• (Sep 30) I have posted grades for assignment 2. You can check on your grades by logging into a departmental machine and typing "courseInfo 2001". (You can do this from home by ssh'ing into red.cs.yorku.ca.) This assignment was marked automatically. The Java programme I wrote to test your solutions to assignment 2 is available in /cs/course/2001/DFA.java. Feel free to copy the programme into your own directory, so that you can play with it or modify it to do other manipulations of DFA's. The main routine of this code reads two DFAs in YUFAFF and then tests whether the two automata accept the same language (using the algorithm to be discussed in an upcoming lecture). If they do not accept the same language, then it tests all strings of length < maxlength and prints a list of the ones that are handled differently by the two DFAs. The solutions I handed out for assignment 2 are encoded in YUFAFF in /cs/course/2001/a2q1.txt and a2q2.txt. To test your answers (q1.txt and q2.txt), type the following commands

  javac DFA.java
  cat /cs/course/2001/a2q1.txt q1.txt > foo1.txt
  java -ea DFA < foo1.txt
  cat /cs/course/2001/a2q2.txt q2.txt > foo2.txt
  java -ea DFA < foo2.txt
  

  If there were simple syntax errors in your solution, the very kind TA attempted to fix them before running this code.
• (Sep 26) The tutorial on Sep 26 is cancelled due to an illness of the teaching assistant. I apologize for the short notice.
• (Sep 20) I will be away next week (Sep 26-30) so there will be guest teachers for your classes. The office hour on Monday Sep 26 is cancelled. The office hour on Thursday Sep 29 is moved to Lassonde 2013. I will still be responding to email while away.
• (Sep 18) The quiz will be held in two rooms. Students with surnames A-L should go to Curtis Lecture Hall C, and students with surnames M-Z should go to LSB106 (regular classroom).
• (Sep 18) Clarification for Assignment 2: A Leutonian word must contain at least one character.
• (Sep 6) Bethune College is seeking a class representative for this course. See this link for more details.
• (Sep 2) There will be a York programming contest on Monday, September 12 from 19:00 to 21:00 in Lassonde 1004. All are welcome to attend. (Make sure you have an EECS login beforehand; see the lab monitor in Lassonde 1006 to get one.) See this link for more information.

Important Dates

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

Resources

Textbook

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.)

Other References

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.

Web Links

• The web page for this course the last time I taught it is here.
• Jeff Edmonds has some online notes that he uses when he teaches this course.
• links to web pages on theoretical computer science
• Scooping the Loop Snooper, a poem by Geoffrey K. Pullum that proves the halting problem is undecidable.

Reading

Week	Section	Suggested Exercises
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

Course Handouts

• Mathematical prerequisites for the course
• Review exercises on mathematical prerequisites
• Declaration to be handed in with the first assignment
• Assignment 1
• Sample Quiz from a previous year
• Assignment 2
• Some Java code that will allow you to test your solution to Assignment 2 before you submit it
• Instructions for submitting Assignment 2 online Note: as an alternative, you can also submit using the web interface.
• Assignment 3
• Assignment 4
• An example of constructing a regular expression from a DFA using the method described in the October 4 lecture
• Sample Test 1 from a previous year, and another.
• Assignment 5
• Assignment 6 (with updated deadline)
• TM.java contains some Java code that you can play with to execute Turing machines that are specified in YUTMFF. Try running it on your solution to Assignment 6 before you hand submit the assignment. See comments at the top of the code for details. There is an example of how to encode a TM in YUTMFF here.
• Assignment 7
• MarkTM.java is the programme used to mark your submission for Assignment 6. (You also have to download TM.java above.) Then run 'java -ea MarkTM < yoursolution.txt'.
• Bonus Assignment
• Sample test 2 from a previous year, and another.
• Review questions on decidability and recognizability
• Assignment 8
• Practice for exam: an old exam and hints for the solutions. A set of exam review questions and hints for answering them. Another old exam
• Assignment 9
• Assignment 10

Updated January 3, 2017