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, Go ̈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 prakash@cs.mcgill.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 ́etudiant a le droit de soumettre en franc ̧ais ou en anglais tout travail ́ecrit.
4