Foundations of Computation (CS580 A7): Fall 2022

Instructor:

Vinayak Prabhu

Office:

Office hours:

Email:

GTA:

Bassem Ghorbel

Email:

Office hours:

Course material on Canvas
Please do not use Canvas to contact me. Use my email, and prefix the subject line with "CS422:".

Course Description:

CS 422 is a core course in the foundations of computing. We will cover many of the central fundamental theoretical concepts underlying modern computing systems, without worrying about specifics of ever-changing programming languages and/or computing platforms. These concepts and techniques form the basis of core algorithms and frameworks in diverse application domains, eg., verification and testing, program analysis, circuit deign, cryptography, optimization, and models of computation. Here is a potential list of topics we will cover, and application domains you might encounter the concepts in.
- 1. Automata theory, regular languages (application domains: verification, testing, and control; program analysis; security; string processing; circuit design; models of computation, composing systems; compiler construction).
- 2. Grammars, pushdown automata, context-free languages (application domains: verification and testing; program analysis; compiler construction; NLP; models of computation).
- 3. Turing machines, decidability, reducibility (applications domains: limits of computation -- can a problem be solved by computers? program analysis; security; cryptography; verification and testing).
- 4. First order logic (application domains: verification and testing; security; AI; theorem proving; abstract reasoning).
Course focus: Our focus in the course will be on rigorous thinking and problem solving, based on the above topics. The types of problems can be found in the course textbook, which is very well written.
CS220 Background: We will revisit sets and propositional logic. These core concepts are crucial for many (most?) CS domains. While there will not be dedicated lectures on these topics, I will post references and will assign a couple of sections of readings for you to recall these concepts. Additionally, problems from these topics (sets and propositional logic) will appear in homeworks and exams, enabling you to practice and develop active skills in these areas. We will also discuss sticking points in lectures.

Textbook (required):

Introduction to the Theory of Computation by Michael Sipser.
Note: either the 3rd or the 2nd edition will suffice.
Note: I will assume you have a physical copy of the textbook from November 1 .

Note: Many of the homework problems will be from hardcover US versions (2nd or 3rd ed) of the course textbook.
For 3rd ed:
ISBN-13: 978-1133187790 ISBN-10: 113318779X
For 2nd ed:
ISBN-13: 978-0534950972 ISBN-10: 0534950973

Paperback international editions of the textbook have changed the order of the problems (this is standard practice unfortunately). If you have such a textbook, you will need to map homework problems to the appropriate ones in your book.

Additional References:

Mathematical Structures for Computer Science by Judith L. Gersting (7th edition).
This book is good for the CS220 background we will need. Sections from the textbook from the first chapter on Propositional and Predicate logic will be placed on electronic reserve.

Weekly Schedule (tentative)
Week	Topics	Assigned reading	Homework
8/22-8/26	Introduction, DFAs, NFAs, closure properties	MCS:Chapter 1, MCS: Sections 4.1,4.2,4.3; Chapter 0, Chapter 1 (till page 54)	Homework 0, Homework 1
8/29-9/02	NFAs, determinization: subset construction, closure properties, regular expressions	Chapter 1 till page 66	Homework 2, Prereq Quiz (Sets, Propositional logic)
9/05-9/09	CS220 revisit (Sets, Propositional logic), Regular expressions, non-regular languages	Chapter 1, till Section 1.3	Homework 3
9/12-9/16	Pumping lemma and non-regular languages, Characterizing non-regular languages, first order logic	Chapter 1	Homework 4
9/19-9/23	First order logic Henkin-Hintikka evaluation games, DFA minimization	Gersting:Sections 1.2, 1.3	Homework 5
9/26-9/30	Myhill-Nerode Theorem, Context-free grammars, review	Section 2.1	Midterm prep
10/03-10/05	Midterm 1, Pushdown automata	Section 2.2	Homework 6
10/10-10/14	Midterm 1 solutions, PDA-CFG equivalence	Section 2.3	Homework 7
10/17-10/21	Pumping lemma for CFLs, CYK algorithm, Turing machines	Chapter 3	Homework 8
10/24-10/28	Non-deterministic Turing machines, Undecidability	Chapter 4	Homework 9
10/31-11/04	Undecidability, Turing reducibility	Sections 5.1, 6.3	Midterm prep
11/07-11/11	Review, Midterm 2 (comprehensive)		Midterm prep
11/14-11/18	Many-one reducibility	Section 5.3	Homework 10
11/28-12/02	Midterm solutions, theories in first order logic, arithmetic heirarchy		Homework 11
12/05-12/09	Review
12/12-12/16	Final exam (open book)

Lectures:

Tuesday, Thursday, 5:00pm-6:15pm, CSB 130

Prerequisites:

The main prerequisite is the ability to reason at an abstract level (eg., CS320 or MATH366 or ECE312 or permission of the instructor).

Grading:

The course grade will be based on the following elements (minor adjustments to the weights may be made).

Homework + Prereq quiz. (weight 24%)
Mid-term exam 1 (04 October, 5pm-7:30pm). (weight 20%)
Mid-term exam 2 (10 November 5pm-7:30pm). (weight 28%)
Final Exam (14 December). (weight 28%)

Some of the exams may be open book.

Homework and Readings:

Written homework will be regularly assigned (posted on Canvas) and you will be expected to solve the problems. You are also expected to read the relevant sections from the textbook.
Note: Posted lecture notes are not a substitute for textbook readings.