CSE 30151

Theory of Computing

Overview

Time
TTh 2–3:15pm
Location
126 DeBartolo Hall
Instructor
Dr. David Chiang
Prerequisites
Discrete Mathematics (CSE 20110) or equivalent. You especially need to be comfortable with sets, tuples, functions, relations, and graphs; and writing proofs by contradiction and by induction.
Required text
Michael Sipser's Introduction to the Theory of Computation, in either the 2nd or 3rd edition:
Description
Introduction to formal languages and automata, computability theory, and complexity theory with the goal of developing understanding of the power and limits of different computational models. Topics covered include:
  • regular languages and finite automata
  • context-free grammars and pushdown automata
  • Turing machines; undecidable languages
  • the classes P and NP; NP completeness
Links
The following sites will be used in this course:
  • Sakai for submitting assignments and receiving grades
  • Piazza for questions and answers
  • Notes and assignments will be linked from this site, but you can also:

Staff


Instructor
David Chiang
dchiang@nd.edu
MT 3:30–5pm, 326D Cushing

Graduate TA
Antonis Anastasopoulos
aanastas@nd.edu
TTh 5–6pm, 213 Cushing

Graduate TA
Justin DeBenedetto
jdebened@nd.edu
MW 5–6pm, 213 Cushing

Undergraduate TA
Frank Cipollone
fcipollo@nd.edu
M 6–7pm, 213 Cushing

Undergraduate TA
Shuyang Li
sli8@nd.edu
MT 9–10pm, 213 Cushing

Undergraduate TA
Jennifer Long
jlong8@nd.edu
M 10–11pm, 213 Cushing

Undergraduate TA
Zach Waterson
zwaterso@nd.edu
T 8–9pm, 213 Cushing

Requirements

Component Points
Homework (HW) 9 × 30
Course projects (CP) 3 × 30
Midterm exams (ME) 2 × 60
Final exam (FE) 120
Total 600
Letter gradePoints
A
A−
560–600
540–559
B+
B
B−
520–539
500–519
480–499
C+
C
C−
460–479
440–459
420–439
D 360–419
F 0–359

Schedule

Unit Dates Topic Assignment Due
01/12, 01/14 Introduction and background
I 01/19, 01/21 Finite automata HW1
01/26, 01/28 DFA = NFA = regular expressions HW2
02/02, 02/04 Non-regular languages HW3
02/09, 02/11 Review and midterm Study guide
Closure proofs
II 02/16, 02/18 Context free grammars, pushdown automata HW4
02/23, 02/25 CFG to PDA and PDA to CFG
CP1
03/01, 03/03 Non-context-free languages HW5
Spring break
III 03/15, 03/17
JPW
Turing machines HW6
03/22, 03/24
Easter
The universal TM and undecidability CP2
03/29, 03/31 Reducibility HW7
04/05, 04/07 Review and midterm Study guide
IV 04/12, 04/14 P and NP HW8
04/19, 04/21 NP-completeness CP3
04/26 More NP-completeness HW9
05/06 10:30–12:30Final exam Study guide

Policies

Attendance

Students are expected to attend all classes. Foreseeable absences should be discussed with the instructor ahead of time.

Late Work

In the case of a serious illness or other excused absence, as defined by university policies, coursework submissions will be accepted late by the same number of days as the excused absence.

Otherwise, you may submit some problems on time for full credit, and other problems late with a penalty of 20% per day (rounded down to the nearest point). No problem can be submitted more than once.

Honor Code

All work that you submit must be your own; that is, it must represent your own understanding, in your own words. Discussion of problems is encouraged, but writing solutions together or looking at other students' solutions is not allowed. Any print or online resources that you use must be cited properly; use of solution manuals is not allowed.

Students with Disabilities

Any student who has a documented disability and is registered with Disability Services should speak with the professor as soon as possible regarding accommodations. Students who are not registered should contact the Office of Disability Services.