CSE 30151 Spring 2008: Theory of Computing

General Information

Class Schedule

• TTh 12:30-1:45pm Jan 15 - April 30, 2008, at Hayes Healy Center 117
• Final exam 10:30-12:30pm May 8, 2008

Instructor

• Marina Blanton
• Email: mblanton@cse.nd.edu
• Office: 356C Fitzpatrick Hall
• Office hours: MW 4-5pm or by appointment

Teaching Assistant

• Niaz Arifin
• Email: sarifin@nd.edu
• Office: 214 Cushing Hall
• Office hours: Tu 2-3pm or by appointment

Course Description

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

Grading

Textbooks

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

• 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 in class; they can be typed or legibly written.
• One-day late homeworks are accepted at 30% deduction in grade; late homework must be submitted using the dropbox or handed to the instructor.
• One-day late projects are also accepted at 30% grade deduction.

Academic Integrity

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.

Both ND Academic Code of Honor and ND CSE Honest Policy are 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