COMP 330 Winter 2021 Lecture 1
COMP 330 Winter 2021 Lecture 1
Prakash Panangaden1
1School of Computer Science
McGill University
McGill University,Montréal, January 2021
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 1 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Welcome to COMP 330
My name: Prakash Panangaden
How should you address me?
Prof. Panangaden,
not Prof. Prakash!!
Prakash (no title) is fine also
as is Sir
but not “Your lordship.”
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 2 / 12
Introduction
Course Title
Official Title
Theory of Computation
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 3 / 12
Introduction
TAs
1 Johanna Schwartzentruber
2 James Bodzay
3 Florestan Brunck
4 Qungyi Sun
5 Roland Riachi
6 Lin Xiao Zheng
7 Yue Wu
Responsible for answering queries on the discussion group, office
hours and helping with grading assignments, mid-terms and finals.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 4 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Course Administration
1 cs.mcgill.ca/~prakash/Courses/330/comp330.html
Lecture notes, assignments and solutions will be posted there.
2 I will never use slides again.
3 Office hours: Tuesdays, Thursdays 1:30 to 3:00.
4 on Zoom
5 I will set up a MyCourses page with links to the course web site
and grades.
6 Instructors and students will communicate technical discussions
on myCourses.
7 There are sure to be Facebook groups; I will not be a part of them
nor will my TAs answer questions there.
8 Do not send me, or the TAs, messages through Facebook.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 5 / 12
Introduction
Grading
6 assignments : 30%, submitted as pdf files through myCourses
5 quizzes : 15% using the myCourses system.
1 online midterm: 10% of your grade,
Final exam online 3 hours: 45% of your total grade.
Final exam, midterm and quizzes must be done by yourself
without looking up solutions on the internet or discussing with your
friends.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 6 / 12
Introduction
Grading
6 assignments : 30%, submitted as pdf files through myCourses
5 quizzes : 15% using the myCourses system.
1 online midterm: 10% of your grade,
Final exam online 3 hours: 45% of your total grade.
Final exam, midterm and quizzes must be done by yourself
without looking up solutions on the internet or discussing with your
friends.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 6 / 12
Introduction
Grading
6 assignments : 30%, submitted as pdf files through myCourses
5 quizzes : 15% using the myCourses system.
1 online midterm: 10% of your grade,
Final exam online 3 hours: 45% of your total grade.
Final exam, midterm and quizzes must be done by yourself
without looking up solutions on the internet or discussing with your
friends.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 6 / 12
Introduction
Grading
6 assignments : 30%, submitted as pdf files through myCourses
5 quizzes : 15% using the myCourses system.
1 online midterm: 10% of your grade,
Final exam online 3 hours: 45% of your total grade.
Final exam, midterm and quizzes must be done by yourself
without looking up solutions on the internet or discussing with your
friends.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 6 / 12
Course contents
Finite state automata
Basic mathematics and logic
Deterministic finite automata, regular languages
Nondeterministic finite automata
Regular expressions
Minimization
The pumping lemma
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 7 / 12
Course contents
Context-free languages
Grammars
Pushdown automata
Parsing
The pumping lemma for context-free languages
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 8 / 12
Course contents
Computability
Models of computation
Undecidable problems
Reduction techniques
Advanced topics
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 9 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
The role of language
We all speak natural language(s) with varying degrees of
precision and accuracy.
But sloppy use of language causes confusion in mathematics.
In mathematical discussions we need to use precise mathematical
notation.
The so-called “popular” books are more confusing than the real
thing.
Computers are completely unforgiving!!
In order to train our minds we need to learn to speak carefully.
Every sentence has to be constructed with care.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 10 / 12
Ideology
English sloppiness that drives me crazy
Writing “can not” instead of “cannot”: causes a real mistake in
meaning.
Mistaking “that” and “which”; sloppy but we usually understand.
“I would like eggs and bacon or sausages.” Ambiguity
“Dr. Lex Luthor is a former alumni of Gotham State.”
Clearly does not know what “alumnus” means nor what is the
singular form. I saw this in a newspaper article.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 11 / 12
Ideology
English sloppiness that drives me crazy
Writing “can not” instead of “cannot”: causes a real mistake in
meaning.
Mistaking “that” and “which”; sloppy but we usually understand.
“I would like eggs and bacon or sausages.” Ambiguity
“Dr. Lex Luthor is a former alumni of Gotham State.”
Clearly does not know what “alumnus” means nor what is the
singular form. I saw this in a newspaper article.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 11 / 12
Ideology
English sloppiness that drives me crazy
Writing “can not” instead of “cannot”: causes a real mistake in
meaning.
Mistaking “that” and “which”; sloppy but we usually understand.
“I would like eggs and bacon or sausages.” Ambiguity
“Dr. Lex Luthor is a former alumni of Gotham State.”
Clearly does not know what “alumnus” means nor what is the
singular form. I saw this in a newspaper article.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 11 / 12
Ideology
English sloppiness that drives me crazy
Writing “can not” instead of “cannot”: causes a real mistake in
meaning.
Mistaking “that” and “which”; sloppy but we usually understand.
“I would like eggs and bacon or sausages.” Ambiguity
“Dr. Lex Luthor is a former alumni of Gotham State.”
Clearly does not know what “alumnus” means nor what is the
singular form. I saw this in a newspaper article.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 11 / 12
Ideology
English sloppiness that drives me crazy
Writing “can not” instead of “cannot”: causes a real mistake in
meaning.
Mistaking “that” and “which”; sloppy but we usually understand.
“I would like eggs and bacon or sausages.” Ambiguity
“Dr. Lex Luthor is a former alumni of Gotham State.”
Clearly does not know what “alumnus” means nor what is the
singular form. I saw this in a newspaper article.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 11 / 12
Ideology
Logical reasoning
Many of the problems students have with this class are caused by
imprecise use of language. Please read the first handout that I wrote.
Panangaden (McGill University) COMP 330 Winter 2021 Lecture 1 Montréal, 7 January 2021 12 / 12
Introduction
Course contents
Ideology