CSE 30151 Spring 2012

CSE 30151 Spring 2012: Theory of Computing

General Information

Class Schedule

TTh 2:00-3:15pm January 17 - May 2, 2012, at DeBartolo Hall 214
Final exam: TBA

Instructor

Dr. Marina Blanton
Email: mblanton at nd.edu
Office: 326B Cushing Hall
Office hours: MW 4-5pm or by appointment

Teaching Assistants

Wei Zhang
Email: wzhang7 at nd.edu
Office: 213 Cushing Hall
Office hours: Fri 9:30-10:30pm or by appointment

Tao Xu
Email: txu1 at nd.edu
Office: 213 Cushing Hall
Office hours: Tue 3:30-4:30pm or by appointment

Course Description

This course introduces students 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. The topics covered include:

regular languages and finite automata
context-free grammars and pushdown automata
Turing machines
undecidable languages
complexity theory: classes P and NP, NP completeness

Grading

Grading for this course will be based on homework assignments (HW), a course project (CP), two midterm exams (ME), and the final exam (FE). Tentatively, the grade will consist of 30% HW, 15% CP, 15% each ME, and 25% FE. There will be several homeworks and a course programming consisting of three parts.

Textbooks

Textbook:

Michael Sipser, Introduction to the Theory of Computation, Second Edition, Thompson Course Technology, 2006.

Additional resources:

H. Lewis and C. Papadimitriou, Elements of Theory of Computation, Second Edition, Prentice-Hall, 1998.
J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages and Computation, Second Edition, Addison-Wesley, 2001.

Assignment Policies

All homeworks and projects must be done individually unless announced otherwise.
Discussion of homeworks is encouraged until you begin to formulate individual solutions.
Writing homework and projects must be done individually.
Homeworks will be due at the beginning of the class; they can be typed or legibly written.
One-day (24-hour) late homeworks are accepted at 25% deduction in grade. Late homework must be submitted using the dropbox or handed to the instructor. Homeworks that are late by more than 24 hours are not accepted.
One-day (24-hour) late projects are also accepted at 25% grade deduction. Projects that are late by more than 24 hours are not accepted.

Academic Integrity

Computer science, as a profession, requires us to seek truth not only in scientific discoveries, but also in dealing with the public, as the public depends on our expertise and honesty to construct their computing infrastructure. Thus, competence and trust are essential to being a scholar and a computing professional in particular.

Your instructor will treat you as a professional, and you should plan on conducting yourself in an appropriate way. No behavior that compromises academic honesty (such as use of someone else's work or code, using prohibited materials during tests, or making your work available to others) will be tolerated in this course. If you need assistance with anything, do not hesitate to contact the instructor.

The ND Academic Code of Honor is in effect. It is expected that your work represents your own understanding of the problem. If work of others is used, it must be properly cited. Use of properly cited material is acceptable, but no referencing is treated as claiming the work as your own.

Course Schedule

Homework and project assignments, as well as some other additional resources, are available from Concourse (access to Concourse is also available from insideND).

Date Topic Textbook sections Assignments

Tuesday, January 17 Introduction and course outline Chapter 0 Read chapter 0

Thursday, January 19 Languages and finite automata Section 1.1

Tuesday, January 24 DFAs and NFAs Sections 1.1-1.2 hw1 is assigned

Thursday, January 26 Equivalence of DFA and NFA classes Section 1.2, handout

Tuesday, January 31 State minimization Handout hw1 is due, project 1 is assigned

Thursday, February 2 Closures, finite state transducers Sections 1.1-1.2, handout

Tuesday, February 7 Regular expressions, equivalence with finite automata Section 1.3

Thursday, February 9 Nonregular languages Section 1.4 project 1 is due at midnight, hw2 is assigned

Tuesday, February 14 Nonregular languages Section 1.4

Thursday, February 16 Context-free languages and grammars Section 2.1 hw2 is due, hw3 is assigned

Tuesday, February 21 Context-free grammars, ambiguity Section 2.1

Thursday, February 23 Chomsky normal form, push-down automata
Section 2.2

Tuesday, February 28 Push-down automata, midterm review Section 2.2 hw3 is due

Thursday, March 1 First midterm Chapters 0 and 1 hw4 is assigned

Tuesday, March 6 Equivalence of CFGs and PDAs Section 2.2, handout

Thursday, March 8 Deterministic PDA Handout hw4 is due, project 2 is assigned

Tuesday, March 13 Spring break

Thursday, March 15 Spring break

Tuesday, March 20 Deterministic PDA

Thursday, March 22 Review of first exam

Tuesday, March 27 Non-context-free languages Handout, Section 2.3 project 2 due on 3/26 at midnight, hw5 is assigned

Thursday, March 29 Non-context-free languages and Turing machines Sections 2.3 and 3.1

Tuesday, April 3 Turing machines Section 3.1 hw5 is due

Thursday, April 5 Second midterm Chapters 0 - 2

Tuesday, April 10 Variants of Turing machines, decidability Sections 3.2, 3.3, and 4.1 project 3 is assigned

Thursday, April 12 Undecidable problems Section 4.2

Tuesday, April 17 Reducibility Section 5.1 project 3 is due at midnight, hw6 is assigned

Thursday, April 19 Reducibility, time complexity, class P Sections 5.3, 7.1 and 7.2

Tuesday, April 24 Class NP, review of second exam Section 7.3 hw6 is due, hw7 is assigned

Thursday, April 26 NP-completeness Section 7.4, handout

Tuesday, May 1 Course review, Introduction to cryptography hw7 is due

Date	Topic	Textbook sections	Assignments
Tuesday, January 17	Introduction and course outline	Chapter 0	Read chapter 0
Thursday, January 19	Languages and finite automata	Section 1.1
Tuesday, January 24	DFAs and NFAs	Sections 1.1-1.2	hw1 is assigned
Thursday, January 26	Equivalence of DFA and NFA classes	Section 1.2, handout
Tuesday, January 31	State minimization	Handout	hw1 is due, project 1 is assigned
Thursday, February 2	Closures, finite state transducers	Sections 1.1-1.2, handout
Tuesday, February 7	Regular expressions, equivalence with finite automata	Section 1.3
Thursday, February 9	Nonregular languages	Section 1.4	project 1 is due at midnight, hw2 is assigned
Tuesday, February 14	Nonregular languages	Section 1.4
Thursday, February 16	Context-free languages and grammars	Section 2.1	hw2 is due, hw3 is assigned
Tuesday, February 21	Context-free grammars, ambiguity	Section 2.1
Thursday, February 23	Chomsky normal form, push-down automata	Section 2.2
Tuesday, February 28	Push-down automata, midterm review	Section 2.2	hw3 is due
Thursday, March 1	First midterm	Chapters 0 and 1	hw4 is assigned
Tuesday, March 6	Equivalence of CFGs and PDAs	Section 2.2, handout
Thursday, March 8	Deterministic PDA	Handout	hw4 is due, project 2 is assigned
Tuesday, March 13	Spring break
Thursday, March 15	Spring break
Tuesday, March 20	Deterministic PDA
Thursday, March 22	Review of first exam
Tuesday, March 27	Non-context-free languages	Handout, Section 2.3	project 2 due on 3/26 at midnight, hw5 is assigned
Thursday, March 29	Non-context-free languages and Turing machines	Sections 2.3 and 3.1
Tuesday, April 3	Turing machines	Section 3.1	hw5 is due
Thursday, April 5	Second midterm	Chapters 0 - 2
Tuesday, April 10	Variants of Turing machines, decidability	Sections 3.2, 3.3, and 4.1	project 3 is assigned
Thursday, April 12	Undecidable problems	Section 4.2
Tuesday, April 17	Reducibility	Section 5.1	project 3 is due at midnight, hw6 is assigned
Thursday, April 19	Reducibility, time complexity, class P	Sections 5.3, 7.1 and 7.2
Tuesday, April 24	Class NP, review of second exam	Section 7.3	hw6 is due, hw7 is assigned
Thursday, April 26	NP-completeness	Section 7.4, handout
Tuesday, May 1	Course review, Introduction to cryptography		hw7 is due