Comp 330 Theory of Computation
Instructor 

Hamed Hatami 
TA 

TBA 
Lecture 

TuesdayThursday 01:05  2:25pm 
Office hours 

TBA 
Outline 

course outline 
Textbook 

Michael Sipser, Introduction to the Theory of Computation, (1st, 2nd, or 3rd edition). 
Description
This is the principal undergraduate course in theoretical computer science at the School of Computer Science (SOCS).
It focuses on the central concepts that constitute the foundations of computer science.
 What kinds of problems can be solved mechanically?
 What does it mean that there is a process (algorithm) that solves a problem?
 What is an algorithm?
These important questions are raised in the early twentieth century (before the invention of the modern computers), and by the mid twentieth century satisfactory answers were provided by the contribution of great mathematicians such as Turing, Church, Hilbert, Godel, Tarski, Post, Markov, Kleene. Some of these results are now considered to be among the greatest scientific achievements in the twentieth century.
To investigate these questions one has to introduce rigorous models of computations, and then study their capabilities and limitations. In this course we study models of computation of increasing power. We begin with finite automata and regular languages which are models of computations with very limited power. The next phase deals with contextfree languages invented by linguistics and now an essential aspect of every modern programming language. Finally we explore the limits of computability with the study of Turing machines (the theoretical model for modern computers), recursive sets, enumerable sets, selfreproducing programs and undecidability theory.
Be prepared to see lots of proofs and abstract mathematical concepts in this course. If you are used to rigorous mathematical proofs, then this course will be easy for you. But if not, then you need to familiarize yourself with such proofs, and this can only be achieved by solving a lot of problems. The prerequisites are COMP 251 and MATH 240.
Remote Teaching
Currently the plan is to have a mixture of prerecorded material, online virtual whiteboard lectures, discussion boards, and collective problem solving tuitorials, but we are still thinking about these things, and I might change it if I find out about better ways of teaching online.
Grading
Homework + Participation + Exam (I will post more information about this as we get closer to the fall)
Late homeworks can be submitted until 48 hours after the deadline. There will be a penalty of 25% for oneday delays, and 40% for twoday delays on late homeworks.
Tentative plan
Part I 


Lecture 
Topic 
Reading 
1 
Course overview and basic background 
Chapter 0 
2 
DFA's 
Section 1.1 
3 
NFA's 
Section 1.2 (until Corollary 1.40) 
4 
regular expressions 
Section 1.2, 1.3 
5 
regular languages and regular expressions 
Theorem 1.54 
6 
nonregular languages 
Section 1.4 
7 
Pumping Lemma 
Section 1.4 and Problem 1.54 
8 
Context free grammars 
Section 2.1 and the proof that they include regular languages 
9 
PDA's, and CFG's can be converted to PDA's. 
Section 2.2 until Lemma 2.27 
10 
Noncontext free grammars 
Section 2.3 
Part II 


Lecture 
Topic 
Reading 
11 
Turing Machines 
Section 3.1 (Until Example 3.10) 
12 
Turing Machines (Example 3.11 in full details), Multitape. 
Section 3.1, Section 3.2 (Until Theorem 3.16) 
13 
Nondeterministic Turing Machines, 
Section 3.2, 3.3. 
14 
Decidability (mostly examples of decidable and r.e. languages) 
Section 4.1 
15 
Undecidability (countable sets, diagonalization method, undecidable languages) 
Section 4.2 
16 
Undecidability, Recursive Enumerable and Corecursive enumerable languages 
4.2, 5.1 
17 
Undecidability of Post Correspondence Problem 
5.2 
18 
Mapping reductions and Turing Reductions 
5.3, 6.3 
19 
First order logic, Godel's completeness theorem. 
6.2 
20 
Godel's incompleteness theorem, Kolmogorov Complexity 
6.2, 6.4 
21 
Time Complexity, Running Time, Complexity class P 
7.1, 7.2 
22 
Complexity class NP 
7.3 
23 
NPcompletness, relativization of P vs NP 
7.4 
Some advice on how to do well in this course:
Your (i) background, your (ii) efforts, and more importantly (iii) the efficiency of your efforts will be the main determining factors on how well you will master the subject. This course covers a wide range of new material. Unfortunately, considering that it is only a semester long course, I will not have time to spend sufficient time explaining each topic, and it will be very important that you set aside some time off class to read and learn these topics in more depth.
 Your background is the most important factor on how you will do in this course. If you are coming with a good understanding of logic, proofs, and have good problemsolving skills, you will do well in this course. If you lack in these skills, it is better to postpone this course until you acquire them.
 Avoiding distractions and staying focused is probably the most important contributing factor to the efficiency of your study. Same goes for the lectures. Use of cellphones is not allowed in the class. Even a quick look at a text message, or an email can break your concentration and you might be lost for the rest of the lecture. If you are using a laptop to take notes, make sure that it is not connected to the Internet. I recommend following the same rule at home when you are studying for this course, or when trying to do the assignments. (When doing research, I stay away from my computer and cellphone). Also try to see how you can get your focus. What works for me is starting by reading a research paper or a book on the subject first, and once I get a good focus, I start working on research problems, but different things work for different people, so you should find your own formula.
 Solve problems: Solve as many problems as you can. Avoid the temptation to look at the solution, searching the Internet, or discussing it with other students. Try your absolute hardest before giving up. If it didn't work, then look for some hints, and then the last stage is to actually read the solution. Try to understand why you couldn't solve it by yourself. In my experience solving a problem by yourself, without any hints, has the greatest learning effect, and reading the solution to a problem has the least effect. Solving one difficult problem is probably better than reading the solutions to 100 problems.
 Be skeptical of your solutions, and learn to distinguish between correct and incorrect solutions. Sometimes students complain to me that their incorrect proof or solution deserves more partial marks. Such solutions are sometimes an indication that the student has not been able to tell that his/her proof was incorrect. It happens very often that I see the students who understood the course better and solve the harder questions, leave the answer to some difficult questions blank as they are well aware of the fact that they were not able to solve that particular question. Because of this high partial marks are only given to solutions that are correct but have some minor mistakes.
 Try hard! It sounds obvious but it takes a long time to acquire this skill. Trying hard for one hour is much more productive (and much more tiring) than sitting in front of your desk for five hours and lazily thinking about a problem.
 Avoid overworking, and do not believe in the myth of the genius either: Unfortunately, people like to perpetuate the belief in two mythical scientists: One that works night and day and does not even sleep, and the other is the borngenius that does not need to make any effort and everything comes to him/her easily. The reality (at least as far as I know) is quite different. It is all about the efficiency of their efforts, and the continuity of it. It is a schedule of trying hard and efficiently, and then resting, and repeating this continuously, sometimes for a life time. If you are trying hard, you will get tired quickly, and you need to get a good rest to recover from it. Continuity is also essential. Working hard for a week and taking a two week break after that is a sure way to undo the gains from that hard work. The famous quotation of Gauss
If others would but reflect on mathematical truths as deeply and as continuously as I have, they would make my discoveries
is a good way to summarize these two points.
Policies
Academic honesty. McGill University values academic integrity. Therefore all students must
understand the meaning and consequences of cheating, plagiarism and other academic offenses under
the Code of Student Conduct and Disciplinary Procedures (see http://www.mcgill.ca/integrity
for more information). Most importantly, work submitted for this course must represent your own
efforts. Copying assignments or tests from any source, completely or partially, allowing others
to copy your work, will not be tolerated.
Submission of written work in French. In accord [sic] with McGill University's Charter of
Students' Rights, students in this course have the right to submit in English or in French any
written work that is to be graded.