Preview Workflow

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

Viewing: MATH 3740 : Computational Complexity

Last approved: Tue, 09 May 2017 08:03:46 GMT

Last edit: Fri, 05 May 2017 17:25:23 GMT

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.

Course Attribute
CCAS - GCR: Q & L

candaceg (Sun, 19 Feb 2017 01:05:01 GMT): Rollback: please include all required elements to your syllabus. template attached for further guidance.
Key: 5777