Comp 330 Theory of Computation

 
Instructor   Hamed Hatami
TA   TBA
Lecture   Tuesday-Thursday 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.

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 context-free 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, self-reproducing 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 one-day delays, and -40% for two-day 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 non-regular 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 Non-context 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), Multi-tape. Section 3.1, Section 3.2 (Until Theorem 3.16)
13 Non-deterministic 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 Co-recursive 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 NP-completness, 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.

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.