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 oaf 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
Winter 2007
College
College of Engineering and Computer Science
Department
Computer Science
Course Number
CS 701-01
Comments
Section 01 of CS 740: Algorithms, Complexity and the Theory of Computability.