Foundations of Computation (CS580 A7)

Instructor:

Office:

Office hours:

Email:

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

Course Description:

This 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).
- 5. Time and space complexity (application domains: design of efficient algorithms).
Course focus: Our focus on 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.

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 October 4.

Weekly Schedule (tentative)
Week	Topics	Assigned reading	Homework
8/23-8/27	Introduction, DFAs, NFAs, closure properties	Chapter 0, Chapter 1 (till page 54)	Homework 0, Homework 1
8/30-9/03	NFAs, determinization: subset construction, closure properties	Chapter 1 till page 66	Homework 2
9/06-9/10	Regular expressions, Non-regular languages	Chapter 1, till Section 1.3	Homework 3
9/13-9/17	Pumping lemma and non-regular languages, Myhill-Nerode theorem	Chapter 1	Homework 4
9/20-9/24	Characterizing non-regular languages, DFA minimization, Context-free grammars	Section 2.1	Homework 5
9/27-10/01	Pushdown automata, review	Section 2.2	Midterm prep
10/04-10/08	Midterm 1, PDA-CFG equivalence	Section 2.2	Homework 6
10/11-10/15	Midterm 1 solutions, pumping lemma for CFLs, CYK algorithm	Section 2.3
10/18-10/22	Turing machines, non-determinism	Chapter 3	Homework 7
10/25-10/29	Decidability, Reducibility	Chapter 4, Section 5.1	Homework 8
11/01-11/05	Reducibility	Sections 5.1, 5.3, 6.3
11/08-11/12	Reducibility, Review		Midterm preparation
11/15-11/19	Midterm 2, Reducibility		Homework 9
11/29-12/03	First-order logic	Section 6.2, notes	Homework 10
12/06-12/10	Midterm 2 solutions, review
12/13-12/17	Final exam

Lectures:

Tuesday, Thursday, 5:00pm-6:15pm, E204 Engineering

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. (weight 10%)
Mid-term exam 1 (TBD). (weight 20%)
Mid-term exam 2 (TBD). (weight 35%)
Final Exam (TBD). (weight 35%)

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.