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
Welcome to COMP 330
My name: Prakash Panangaden
Introduction
Panangaden (McGill University)
COMP 330 Winter 2021 Lecture 1
Montr¨al, 7 January 2021 2 / 12
Welcome to COMP 330
My name: Prakash Panangaden How should you address me?
Introduction
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,
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!!
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
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
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 YueWu
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.
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.
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.
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
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.
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.
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.
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
Grading
Introduction
6 assignments : 30%, submitted as pdf files through myCourses
Panangaden (McGill University)
COMP 330 Winter 2021 Lecture 1
Montr¨al, 7 January 2021 6 / 12
Grading
Introduction
6 assignments : 30%, submitted as pdf files through myCourses 5 quizzes : 15% using the myCourses system.
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,
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.
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.
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.
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.
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!!
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.
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
English sloppiness that drives me crazy
Ideology
Writing ¡°can not¡± instead of ¡°cannot¡±: causes a real mistake in meaning.
Panangaden (McGill University)
COMP 330 Winter 2021 Lecture 1
Montr¨al, 7 January 2021 11 / 12
English sloppiness that drives me crazy
Ideology
Writing ¡°can not¡± instead of ¡°cannot¡±: causes a real mistake in meaning.
Mistaking ¡°that¡± and ¡°which¡±; sloppy but we usually understand.
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
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.¡±
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