Welcome to COMP 330 Winter 2021
Theory of Computation
Instructor : Prakash Panangaden
8th January 2021
Welcome to COMP 330. This is the principal undergraduate course at the School of Computer
Science on the principles1 of theoretical computer science. In this course we will focus on the
foundations of the subject. It is fascinating that the history of computer science2 began several
thousand years before electronic computers were invented. In ancient times people invented algo-
rithms for all kinds of purposes, but it was only in the last 70 years that the electronic computer
was invented. If you look up the word “computer” in a 1946 dictionary it is defined as a person
who performs computations.
The question of what constitutes an algorithm was raised early in the twentieth century3. Early
investigations by logicians: Hilbert, Gödel, Tarski, Post, Markov, Kleene and above all Turing and
Church gave answers that we accept today. Remarkably, they discovered that there were intrinsic
limits of computability. By “intrinsic” I mean inherent in the nature of logic and nothing whatever
to do with technology. This led to the subject of computability theory: one of the main topics of
this term. All this also happened before the invention of the electronic computer.
It may seem that machine architecture is far removed from these theoretical considerations. In fact,
the idea that algorithms could be represented by symbolic data, and that there was a “universal”
machine which could execute these algorithms with a fixed instruction set, was a direct result of
the logical investigations. Today, of course, these symbolic representations are called “software”
and the universal machines are available for sale to every household: we call them phones4, tablets
and personal computers. They are even embedded in cars, washing machines, refrigerators and
microwave ovens.
Two other important inputs into the subject are (1) the theory of the brain which led to automata
theory (the first one-third of the course) and (2) linguistics, which led to the notion of formal
languages. One type of formal language is called a “context-free” language and is the basis for the
syntax of all programming languages today.
1Note the difference between “principal” and “principle”.
2what a silly name for a subject! Computers as physical artefacts are only one aspect of computation.
3Actually, in the last year of the 19th century.
4The word “phone” is a historical relic, they are really quite powerful computers.
1
Lectures
There two lectures per week: on Tuesdays and Thursdays at 11:35 to 12:55 delivered via Zoom.
The link for the Zoom lecture will be available on myCourses. The lectures will be recorded and
the videos will be available for offline viewing and downloading.
Administration
I am responsible for all the administration aspects of the class and for all the assignments. Please
send me questions by email to .ca and I will try to get back to you. There
are teaching assistants as well. They mark the assignments according to strict guidelines made up
by me. We will set up a discussion group for questions related to the class on myCourses. We will
not use Piazza as it has moved to a pay model.
I hate Facebook as a forum for such discussions but that’s where many people seem to be. My
experience with Facebook groups is that there tend to a few people who spout off opinions passed
off as “definitely true” and mislead everyone. But if that’s what you want to do it is not up to me
to stop you.
Assignments
There will be 6 assignments. You will be expected to give mathematically rigorous proofs in
these assignments. Assignments should be submitted through myCourses as pdfs. Please submit
everything in one file. Only the last submission will be kept. The assignments will be mostly
marked by the teaching assistants under my supervision and according to my grading guidelines. I
will mark some of the questions from time to time. You can discuss with a TA whether your answer
is correct but you cannot debate with them how much a question is worth. You can discuss
that with me if you like: but so far I have never been persuaded to change my mind. I also include
spiritual growth questions: these are very hard and may not even be straight questions but an
invitation to speculate. They will earn you no credit whatsoever for the class. However, if you
solve one of them you will feel great personal satisfaction. Assignments are due on Thursdays on
the dates indicated on the lecture schedule at 5pm. Don’t even ask for an extension because
you are busy. I only consider cases where you have a medical excuse.
Quizzes
There will be 5 quizzes which will be done through myCourses. Each quiz will be multiple choice
and will take place on Fridays on the dates indicated on the lecture schedule. The quiz will last
an hour and the system will not give you any extension after the hour is up. You can take the
quiz any time between 7am and 7am the next day; so you have a 24-hour window to complete the
quiz.
References
The recommended textbook for the course is called
Introduction to the Theory of Computation by Michael Sipser.
2
I will follow it loosely – to do well in the course you must know the material that I covered in
my lectures. Another excellent book – in fact, the textbook in an earlier year – is Automata and
Computability by Dexter Kozen. I will also occasionally put some notes on the web site. In principle,
the notes should be enough.
Grading
The homework accounts for 30% of the total course marks. There will be 5 quizzes; these are to be
done online using myCourses. Each quiz will be 3% for a total of 15%. The midterm examination
accounts for 10% and the final examination will be 45% of the total. The midterm examinations
will be online, the final examination will be in the final examination period and will also be an
online 3 hour exam with a 72 hour window for completing it. The mid-term and the final exam
will be open book but you are not allowed to use the internet or to discuss answers with each other
during the exam.
From statistical evidence from my colleagues we have seen that there is massive cheating, which is
very hard to control in these pandemic conditions. If you are not interested in learning the material
and wish to cheat your way to a good grade there is not much I can do. If I find evidence of cheating
I will report you to the disciplinary officer. But in the end, if you do not want to expand your mind
and learn this beautiful subject, you are cheating yourself.
Staying in touch
I will hold office hours twice a week:
Tuesday 1:30 to 3:00 and Wednesdays 1:30 to 3:00 by Zoom.
Please do come and see me during those hours. Do not feel that you are infringing on my time – my
office hours represent time that I have reserved specifically to see you. I recommend using email
to ask me questions. The TAs will also hold office hours which I will post on the course web page.
There will be a class web page. Please ensure that you have access to it. The URL is
www.cs.mcgill.ca/~prakash/Courses/Comp330/comp330.html
I will use the myCourses system to maintain a discussion board. Your marks will be disseminated
through this system. I will check the discussion board from time to time but do not rely on it as a
way of getting a last-minute response to a crucial homework question.
Hints for taking this course
This course is considered by many to be the hardest course at SOCS and by some others the easiest.
I am not sure why there is such a wide variation in performance, but here are a few hints that
might help.
1. Do the homework. Finding videos of lectures on the web is no substitute for thinking for
yourself. You can, of course, find many homework questions solved on the web, but if you do
not engage with the material you will learn nothing and you will suffer during the tests.
2. Read the solutions. I write them with some care. You can learn a lot from seeing how the
solutions are presented.
3
3. The lectures are intended to be thought about and discussed. If you do not understand
everything that is going on in the classroom, do not be either discouraged or surprised. I
expect that you have to think about these ideas before they sink in. Do try and come to
class. Looking at notes taken by others just does not have the same impact. The course is
conceptual not factual.
4. Please come to my office hours. Sometimes it requires a dialogue to unblock a miscon-
ception. There is no shame in seeking help.
5. Learn to read mathematics. For most of you this is your biggest obstacle. It has nothing
to do with intelligence: it has everything to do with care and discipline. I have seen people
confuse “for all” and “there exists” even when they can explain perfectly what the difference
is. If you express yourself clearly and read accurately there is little in the course that is really
tricky.
6. Use language carefully and precisely. In speaking to me, I will insist on correct usage because
much of the confusion about a topic goes away if you learn to express yourself precisely.
Academic Integrity I am required to include the following statement in my course outline:
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,
or allowing others to copy your work, will not be tolerated.
I am okay with students working together, but in the end you should understand what you turn
in. I will take action if you turn in a perfect solution which you then cannot explain
to me.
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.
Chaque étudiant a le droit de soumettre en français ou en anglais tout travail écrit.
4