Faculty member proposing: Ching-Kuang Shene

Email address: shene@mtu.edu

Course syllabus:

	Knowledge  Turing Machines  Familiarity     Turing machines as language accepters and as language recognizers     Turing machines as computers of number-theoretic functions     One-way infinite tape Turing machines     Multitape Turing machines     Universal Turing machines     Nondeterministic machines     Not Turing-computable functions     Classes P and NP		Skills  Turing Machines   Familiarity     Construction of various types of Turing machines     Using deterministic Turing Machines to simulate     one-way Turing machines     multitape Turing machines     Nondeterministic Turing machines
	Recursion Theory  Familiarity     Primitive and partial recursive functions     Recursive and recursively enumerable sets     The equivalence between Turing-computable functions and the class of partial recursive functions  Exposure     Computable but non-primitive recursive functions (the Ackermann's function)     The s-m-n theorem     The recursion theorem		Recursion Theory   Familiarity     Able to determine if a set if recursive or recursively enumerable     Able to prove basic uncomputability of some functions
	Register Machines  Familiarity     The class of register machines (RAMs)     The equivalence among the class of register machines, the class of partial recursive functions, and Turing-computable functions  Exposure     if and while programs     Encoding if and while programs     The computability of if and while programs     The equivalence of if and while programs, Turing machines, register machines and recursion theory     Register machines and formal languages		Register Machines   Familiarity     Able to construct the simulation between Turing machines and register machines
	Other Computational Models  Familiarity     Parallel computational models     Flynn's taxonomy     The data-parallel model     Brent's principle     The PRAM model     Hypercube-based machines  Exposure     Post systems     Logic circuits		Other Computational Models   Familiarity     Able to design basic algorithms under the PRAM model     Simulating Trees, arrays and hypercubes on the PRAM
	The Bounds of Complexity  Familiarity     Computability     Church-Turing Thesis     The halting problem and its application     Rice's theorem and its application     Complexity     Reducibility and NP-Completeness     NP-Complete problems     P-Completeness for parallel computation     The class NC     The limitation of parallel computation     Complexity Classes     Space and Time hierarchies     Time-bounded and space-bounded complexity classes and their relations     Complement classes  Exposure     PSPACE-Completeness and PSPACE-complete problems		The Bounds of Complexity   Familiarity     The techniques of proving NP-Completeness and P-Completeness     Able to use Rice's theorem to prove non-recursiveness of basic functions
	Modern Developments  Exposure     Turing machines and complexity for REAL numbers     Quantum computational models     DNA-based computers		Modern Developments