The CIM Courses system will be down temporarily undergoing routine maintenance.

Catalog Pages referencing this course

Programs referencing this course

Columbian College of Arts and Sciences

Mathematics (MATH)

MATH

3740

Computational Complexity

Computational Complexity

Fall 2017

3

Course Type

Lecture

Default Grading Method

Letter Grade

No

No

MATH 2971 or MATH 2971W

Corequisites

40

Frequency of Offering

Term(s) Offered

Are there Course Equivalents?

No

No

Fee Type

No

Automata and languages; deterministic and nondeterministic Turing machines; space and time complexity measures and classes; P-versus-NP problem; traveling salesman problem and other NP-complete problems; intractability; circuit complexity; introduction to probabilistic and quantum algorithms.

Learning Outcomes

As a result of completing this course students should be able to:

1.Design finite automata, push-down automata, and Turing machines, and relate the languages they accept to Chomsky's hierarchy;

2.Demonstrate that a language is not regular, not context-free, or not decidable;

3.Know various time and space complexity classes and apply complex- ity analysis to specific problems;

4.Analyze polynomial reductions of NP-complete problems;

5.Compare and contrast quantum computing and classical computing.

As a result of completing this course students should be able to:

1.Design finite automata, push-down automata, and Turing machines, and relate the languages they accept to Chomsky's hierarchy;

2.Demonstrate that a language is not regular, not context-free, or not decidable;

3.Know various time and space complexity classes and apply complex- ity analysis to specific problems;

4.Analyze polynomial reductions of NP-complete problems;

5.Compare and contrast quantum computing and classical computing.

Uploaded a Course Syllabus

Course Attribute

CCAS - GCR: Q & L

Key: 5777