Lecture 1:
• Overview
• Course information • Finite automata
Mark Bun January 22, 2020
Reading:
Sipser Ch. 0, 1.1
Course Information
1/22/2020 CS332 – Theory of Computation 2
Course Staff
• Me: Mark Bun
• At BU since Sept. 2019
• Office hours: Wed 4:00-6:00, MCS 114
• Research interests: Theory of computation (!)
More specifically: Computational complexity, data privacy, cryptography, foundations of machine learning
• TF: Nadya Voronova
• Leading 9:30 and 12:30 discussion sections • Office hours: Fri 2:30-4:30, Location TBD
• Tim Jackman
• Leading 11:15 discussion section
1/22/2020 CS332 – Theory of Computation 3
Course Webpage
https://cs-people.bu.edu/mbun/courses/332_S20/
Serves as the syllabus and schedule
Check back frequently for updates!
1/22/2020 CS332 – Theory of Computation 4
Course Structure
Start 1/22
Spring Break 3/9-3/14
Automata & Formal Languages
Computability
Complexity
Grading
• •
•
Homework (30%): Roughly 10 of these Exams (60%):
• Midterm I (15%)
• Midterm II (15%)
• Final (30%)
Participation (10%): TopHat
Midterm I 2/24
Midterm II 4/1
Final 5/7 (?)
1/22/2020 CS332 – Theory of Computation
5
Homework Policies
• Weekly assignments due Mondays @ 2PM
• No late days, no extensions
• Lowest homework score will be dropped
• Homework to be submitted via Gradescope • Entry code: MKB65D
• You are encouraged to typeset your solutions in LaTeX (resources available on course webpage)
• HW1 to be released on Mon 1/27, due Mon 2/3
1/22/2020 CS332 – Theory of Computation 6
Homework Policies: Collaboration
• You are encouraged to work with your classmates to discuss homework problems
• HOWEVER:
• You may collaborate with at most 3 other students
• You must acknowledge your collaborators
• You must write your solutions by yourself
• You may not share written solutions
• You may not search for solutions using the web or other outside resources
• You may not receive help from anyone outside the course (including students from previous years)
1/22/2020 CS332 – Theory of Computation 7
Homework Policies: Collaboration
Details of the collaboration policy may be found here:
https://cs- people.bu.edu/mbun/courses/332_S20/handouts/collaboration.pdf
Important: Sign this document to affirm you understand it, and turn it in via Gradescope by 2PM, Mon 1/27
1/22/2020 CS332 – Theory of Computation 8
Textbook
1/22/2020
CS332 – Theory of Computation 9
Introduction to the Theory of Computation (Third Edition)
by Michael Sipser
• It’s fine if you want to use an older edition, but section numbers may not be the same
• Other resources available on course webpage
Piazza
• We will use Piazza for announcements and discussions • Ask questions here and help your classmates
• Please use private messages / email sparingly
https://piazza.com/bu/spring2020/cs332
You can earn bonus points toward your participation grade by participating thoughtfully on Piazza
1/22/2020 CS332 – Theory of Computation 10
TopHat
• Your class participation score (10% of the course grade) will be determined by your engagement with TopHat
https://tophat.com/ Entry code: 400708
• You will be graded only on participation, not correctness
• Answering 80% of the questions in TopHat will earn you a full participation grade
1/22/2020 CS332 – Theory of Computation 11
Expectations and Advice for Succeeding in CS 332
1/22/2020 CS332 – Theory of Computation 12
Our (the Course Staff’s) Responsibilities
• Guide you through difficult parts of the material in lecture
• Encourage active participation in lectures / section
• Assign practice problems and homework that will give
you a deep understanding of the material
• Give detailed (formative) feedback on assignments
• Be available outside of class (office hours, Piazza)
• Regularly solicit feedback to improve the course Anonymous feedback to Mark:
https://forms.gle/AV38CBgLKTSBmtqRA
1/22/2020 CS332 – Theory of Computation 13
Your Responsibilities
• Concepts in this course take some time to sink in. Keep at it, and be careful not to fall behind.
• Do the assigned reading on each topic before the corresponding lecture.
• Take advantage of office hours.
• Participate actively in lectures/sections and on Piazza.
• Allocate lots of time for the course: comparable to a project-based course, but spread more evenly.
1/22/2020 CS332 – Theory of Computation 14
Prerequisites
This class is fast-paced and assumes experience with mathematical reasoning and algorithmic thinking
You must have passed CS 330 – Intro to Algorithms This means you should be comfortable with:
• Set theory
• Functions and relations • Graphs
• Pigeonhole principle
• Propositional logic
• Asymptotic notation
• Graph algorithms (BFS, DFS) • Dynamicprogramming
• NP-completeness
Come talk to me if you have questions about your preparation for the course
1/22/2020 CS332 – Theory of Computation 15
Advice on Homework
• Start working on homework early! You can get started as soon as it’s assigned.
• Spread your homework time over multiple days.
• You may work in groups (of up to 4 people), but think about each problem for at least 30 minutes before your group meeting.
• To learn problem solving, you have to do it:
• Try to think about how you would solve any presented
problem before you read/hear the answer
• Do exercises in the textbook in addition to assigned homework problems
1/22/2020 CS332 – Theory of Computation 16
Advice on Reading
• Not like reading a novel
• The goal is not to find out the answers, but to learn and
understand the techniques
• Always try to predict what’s coming next
• Always think about how you would approach a problem before reading the solution
• This applies to things that are not explicitly labeled as exercises or problems!
1/22/2020 CS332 – Theory of Computation 17
Course Overview
1/22/2020 CS332 – Theory of Computation 18
Objective
Build a theory out of the idea of computation
1/22/2020 CS332 – Theory of Computation 19
What is “computation”
• Examples:
• Paper + pencil arithmetic
• Abacus
• Mechanical calculator
• Ruler and compass geometry constructions • Java/C programs on a digital computer
• For us: Computation is the processing of information by the unlimited application of a finite set of operations or rules
1/22/2020 CS332 – Theory of Computation 20
What do we want in a “theory”?
• General ideas that apply to many different systems • Expressed simply, abstractly, and precisely
• Generality
• Independence from Technology: Applies to the future as well as the
present
• Abstraction: Suppresses inessential details
• Precision: Can prove formal mathematical theorems
• Positive results (what can be computed): correctness of algorithms
and system designs
• Negative results (what cannot be computed): proof that there is no algorithm to solve some problem in some setting (with certain cost)
1/22/2020 CS332 – Theory of Computation 21
Parts of a Theory of Computation
• Models for machines (computational devices)
• Models for the problems machines can be used to solve
• Theorems about what kinds of machines can solve what kinds of problems, and at what cost
This course: Sequential, single-processor computing Not covered:
– Parallel machines – Real-time systems
– Distributed systems – Mobile computing
– Quantum computation – Embedded systems
1/22/2020 CS332 – Theory of Computation 22
What is a (Computational) Problem?
A single question with infinitely many instances Examples:
Parity: Given a string consisting of 𝑎’s and 𝑏’s, does it contain an even number of 𝑎’s?
Primality: Given a natural number 𝑥 (represented in binary), is 𝑥 prime?
Halting Problem: Given a C program, can it ever get stuck in an infinite loop?
For us: Focus on decision problems (yes/no answers) on discrete inputs
1/22/2020 CS332 – Theory of Computation 23
What is a (Computational) Problem?
For us: A problem will be the task of recognizing whether a string is in a language
• Alphabet: A finite set Ʃ Ex. Ʃ = {𝑎, 𝑏, … , 𝑧}
• String: A finite concatenation of alphabet symbols (order matters)
Ex. 𝑏𝑞𝑟, 𝑎𝑏𝑎𝑏𝑏
𝜀 denotes empty string, length 0 Ʃ ∗ = set of all finite strings over Ʃ
• Language: A (possibly infinite) set 𝐿 of strings
1/22/2020 CS332 – Theory of Computation 24
Examples of Languages
Parity: Given a string consisting of 𝑎’s and 𝑏’s, does it contain an even number of 𝑎’s?
Ʃ= 𝐿=
Primality: Given a natural number 𝑥 (represented in
binary), is 𝑥 prime? Ʃ= 𝐿=
Halting Problem: Given a C program, can it ever get stuck in an infinite loop?
Ʃ= 𝐿=
1/22/2020 CS332 – Theory of Computation 25
Machine Models
Computation is the processing of information by the unlimited application of a finite set of operations or rules
𝑎
𝑏
𝑎
𝑎
Input
…
Finite control
Abstraction: We don’t care how the control is implemented. We just require it to have a finite number of states, and to transition between states using fixed rules.
1/22/2020 CS332 – Theory of Computation 26
Machine Models
• Finite Automata (FAs): Machine with a finite amount of unstructured memory
𝑎
𝑏
𝑎
𝑎
Input
…
Finite control
Control scans left-to-right
Can check simple patterns
Can’t perform unlimited counting
Useful for modeling chips, simple control systems, choose-your- own adventure games…
1/22/2020 CS332 – Theory of Computation 27
Machine Models
• Pushdown Automata (PDAs): Machine with unbounded structured memory in the form of a stack
𝑎
𝑏
𝑎
𝑎
Input
…
𝑏
𝑏
𝑎
Finite control
Control scans left-to-right
Can use stack to count, balance parentheses
Useful for modeling parsers, compilers, some math calculations
Memory: Infinite Stack
1/22/2020 CS332 – Theory of Computation 28
Machine Models
• Turing Machines (TMs): Machine with unbounded, unstructured memory
𝑎
𝑏
𝑎
𝑎
Input
…
Control can scan in both directions Control can both read and write
Finite control
Model for general sequential computation
Church-Turing Thesis: Everything we intuitively think of as “computable” is computable by a Turing Machine
1/22/2020 CS332 – Theory of Computation 29
What theorems would we like to prove?
We will define classes of languages based on which machines can recognize them
Inclusion: Every language recognizable by a FA is also recognizable by a TM
Non-inclusion: There exist languages recognizable by TMs which are not recognizable by FAs
Completeness: Identify a “hardest” language in a class Robustness: Alternative definitions of the same class
Ex. Languages recognizable by FAs = regular expressions
1/22/2020 CS332 – Theory of Computation 30
Why study theory of computation?
• You will learn how to formally reason about computation
• You will learn the technology-independent foundations of CS
Philosophically interesting questions:
• Are there well-defined problems which cannot be solved by computers?
• Can we always find the solution to a puzzle faster than trying all possibilities?
• Can we say what it means for one problem to be “harder” than another?
1/22/2020 CS332 – Theory of Computation 31
Why study theory of computation?
• You will learn how to formally reason about computation
• You will learn the technology-independent foundations of CS
Connections to other parts of science:
• Finite automata arise in compilers, AI, coding, chemistry
https://cstheory.stackexchange.com/a/14818
• Hard problems are essential to cryptography
• Computation occurs in cells/DNA, the brain, economic systems, physical systems, social networks, etc.
1/22/2020 CS332 – Theory of Computation 32
Why study theory of computation?
Practical knowledge for developers
“Boss, I can’t find an efficient algorithm. I guess I’m just too dumb.”
“Boss, I can’t find an efficient algorithm because no such algorithm exists.”
Will you be asked about this material on job interviews?
No promises, but a true story…
1/22/2020 CS332 – Theory of Computation 33