CSE 355 is an introduction to formal language theory and automata; Turing machine, decidability/undecidability, recursive function theory, and introduction to complexity theory. This class is a first introduction to the theoretical concepts of Computer Science. It covers basic mathematical concepts, the concept of formal languages, and the theoretical machines which ecognize them. The class also covers Turing machines and the problem of decidability and computability.

Students are expected to have background in Advanced data structures and algorithms (CSE 310), Mathematical foundations (MAT 243).

Course Information:	CSE 355:  Introduction to Theoretical Computer Science   http://www.public.asu.edu/~ccolbou/src/cse355f06.html
Schedule Line Number:	36965
Class Meeting Time:	T Th 10:40-11:55  BYAC 270
Instructor:    Office Hours:	Charlie Colbourn Office:  Brickyard 444  Charles.Colbourn@asu.edu Monday 2:00-3:00, Thursday 2:00-3:00
TA:    Office Hours:	Donglin Xia Office:  Brickyard 498AC  Phone:  480-727-6389  dxia@asu.edu Tuesday 1:00-2:00, Wednesday 1:00-2:00
Prerequisites:	Data structures; Discrete mathematics.
Special Needs:	If you are entitled to extra accommodation for any reason (such as a disability), we make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor at the beginning of the course.
Academic Honesty:	Work in this course, unless explicitly stated in writing to the contrary, is to be an effort by the individual student. It is not acceptable to use work other than your own without full attribution and acknowledgment. While you are welcome to discuss problems with others, it is not acceptable to discuss solutions with them. If in doubt about anything related to academic integrity, see the instructor.
TextBooks:
Required Text:	Thomas Sudkamp, Languages and Machines, Third Edition, Pearson Addison-Wesley, 2006. Author's web site, including errata