Course Description

Contents and Objectives:

 
This class covers the theoretical foundations necessary for the effective understanding of computation and the analysis of algorithms. Topics include automata theory, formal languages, computability, and complexity theory. Students successfully completing this course will have gained important insights into the theory of computation and be able to apply formal techniques to the analysis and development of algorithms.

Prerequisites:

 
All students are expected to have passed the courses Discrete Structures (CSE 2315) and Calculus I (Math 1426) or an equivalent before attending this course.

Textbook:

 
H.R. Lewis and C.H. Papadimitriou, ``Elements of the Theory of Computation'' (second edition), Prentice-Hall, 1998.

Course Materials:

 
Additional course materials such as lecture notes, assignments, and solutions will be available electronically on the course web page. Changes and corrections, if any, will also be announced by e-mail.

E-mail and WWW page:

 
There is a course web page at http://www-cse.uta.edu/~huber/cse3315 . All changes and supplementary course materials will be available from this site. In addition, necessary changes or important announcements will also be distributed by e-mail. In order to receive class-related messages you have to send an e-mail to the instructor (huber@omega.uta.edu).

Teaching Assistant:

 
The TA for this course is Nibedita Maulik. She will hold office hours in WH 310, MW 2:30 - 4:00, F 4:30-5:00.

Tentative Office Hours:

 
Office hours for the course will be held by the instructor in 302 Nedderman Hall,
TTh 5:30 - 6:30 pm, W 3:00 - 4:00, or by appointment. The first office hours will be held on Thursday, August 30. Times are subject to change and will be posted on the course page. If for some reason you can not make it to any of these office hours, please inform the instructor.