Document Type
Syllabus
Description
The objective of this course is to use the formal algorithmic system provided by Turing machines as a tool to analyze the complexity of decision and optimization problems and the algorithms that solve them. The topics to be covered include
• the definition of the time and space complexity of a deterministic algorithm
• the classes of deterministic polynomial and non-polynomial time languages
• the complexity of nondeterministic algorithms
• the P=NP question (relationship between solvability by deterministic and nondeterministic polynomial time algorithms)
• the implications of a solution to the P=NP question
• NP completeness and examples of NP complete problems
• classes of NP complete problems
• techniques for approximate solutions of NP complete problems
Publication Date
Spring 2008
College
College of Engineering and Computer Science
Department
Computer Science
Course Number
CS 740
