Haiping Xu, PhD

Theoretical basis of the development of computer science. The course details particular formalisms used in the design of hardware and software systems. Intrinsic limitations of computation are described. Advanced topics of automata theory and analysis of algorithms are included. The course also covers Turing machines, the halting problem, models of computation, intractable computations, polynomial reductions, P vs. NP, parallel algorithms, various formal descriptions and specifications of programs and computations, and proofs of program correctness and interactive proof systems.

Prerequisite: Completion of three core courses. Research leading to submission of a formal thesis. This course provides a thesis experience, which offers a student the opportunity to work on a comprehensive research topic in the area of computer science in a scientific manner. Topic to be agreed in consultation with a supervisor. A written thesis must be completed in accordance with the rules of the Graduate School and the College of Engineering. Graded A-F.