Microsoft PowerPoint – CS332-Lec01-ann
1/25/2021 CS332 ‐ Theory of Computation 1
BU CS 332 – Theory of Computation
• Lecture 1:
• Course information
• Overview
Reading:
Sipser Ch 0
Mark Bun
January 25, 2021
Course Information
1/25/2021 CS332 ‐ Theory of Computation 2
Course Staff
• Me:Mark Bun (he/him)
• At BU since Sept. 2019
• Office hours: Wed 4‐5PM, Th 9‐10AM
• Research interests: Theory of computation (!)
More specifically: Computational complexity, data privacy, cryptography,
foundations of machine learning
• TF: Nadya Voronova
• Office hours: Tu 3‐4PM, Wed 9‐10AM
• …hopefully others
1/25/2021 CS332 ‐ Theory of Computation 3
Course Webpage
https://cs‐people.bu.edu/mbun/courses/332_S21/
1/25/2021 CS332 ‐ Theory of Computation 4
Serves as the syllabus
and schedule
Check back frequently
for updates!
Course Structure
1/25/2021 CS332 ‐ Theory of Computation 5
Automata & Formal Languages Computability Complexity
Start
1/25
Test 1
due 2/25
Test 2
due 3/25
Final
due 5/6 (?)
“Spring Break”
3/29‐4/2
Grading
• Homework (45%): Roughly 10 of these
• Take‐home tests (40%):
• Test 1 (10%)
• Test 2 (10%)
• Final (20%)
• Participation (15%): Gradescope check‐ins, HW0, etc.
Homework Policies
• Weekly assignments due Thursday @ 11:59PM
• No late days, no extensions
• Lowest homework score will be dropped
• Homework to be submitted via Gradescope
• Entry code: 2RB88B
• You are encouraged to typeset your solutions in LaTeX
(resources available on course webpage)
• HW0 out, due Th 1/28 (just some housekeeping)
• HW1 to be released on Th 1/28, due Th 2/4
1/25/2021 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 and write “Collaborators:
none” if you worked alone
• 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/25/2021 CS332 ‐ Theory of Computation 7
Homework Policies: Collaboration
1/25/2021 CS332 ‐ Theory of Computation 8
Details of the collaboration policy may be found here:
https://cs‐
people.bu.edu/mbun/courses/332_S21/handouts/collaboration.pdf
Important: Sign this document to affirm you understand it, and turn
it in via Gradescope by 11:59PM, Th 1/28
Textbook
1/25/2021 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
Gradescope Check‐ins
• Your class participation score (15% of the course grade)
will be determined by your answers to short reflection
questions after each lecture
• Questions will be based on our in‐class polls and
discussions
• You’ll be graded 50% on participation and 50% on
correctness
1/25/2021 CS332 ‐ Theory of Computation 10
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/spring2021/cs332
You can earn bonus points toward your participation grade by
participating thoughtfully on Piazza
1/25/2021 CS332 ‐ Theory of Computation 11
Expectations and
Advice for Succeeding
in CS 332
1/25/2021 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
1/25/2021 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/25/2021 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
Come talk to me if you have questions about your preparation
for the course
1/25/2021 CS332 ‐ Theory of Computation 15
• Asymptotic notation
• Graph algorithms (BFS, DFS)
• Dynamic programming
• NP‐completeness
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.
1/25/2021 CS332 ‐ Theory of Computation 16
• 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
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/25/2021 CS332 ‐ Theory of Computation 17
Academic Integrity
Extremely important: Read and understand the
Collaboration and Honesty policy before you sign it
Violations of the collaboration policy…will result in an automatic failing
grade and will be reported to the Academic Conduct Committee (ACC). The
ACC often suspends or expels students deemed guilty of plagiarism or
other forms of cheating.
If you find yourself in a desperate situation:
• Hand in as much of the assignment as you’re able to
complete
• Remember the lowest HW grade is dropped
• Talk to us! We want to help
…cheating is seriously not worth it
1/25/2021 CS332 ‐ Theory of Computation 18
Course Overview
1/25/2021 CS332 ‐ Theory of Computation 19
Objective
Build a theory out of the idea of computation
1/25/2021 CS332 ‐ Theory of Computation 20
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/25/2021 CS332 ‐ Theory of Computation 21
Other examples of computation?
1/25/2021 CS332 ‐ Theory of Computation 22
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/25/2021 CS332 ‐ Theory of Computation 23
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/25/2021 CS332 ‐ Theory of Computation 24
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/25/2021 CS332 ‐ Theory of Computation 25
What is a (Computational) Problem?
For us: A problem will be the task of recognizing whether
a string is in a language
1/25/2021 CS332 ‐ Theory of Computation 26
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
Ex.
denotes empty string, length 0
∗
= set of all strings using symbols from
• Language: A set of strings
1/25/2021 CS332 ‐ Theory of Computation 27
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/25/2021 CS332 ‐ Theory of Computation 28