CS 311 Computational Structures
Credit Hours:  4 
Course Coordinator:  Andrew Black 
Course Description:  Introduces the foundations of computing. Regular languages and finite automata. Contextfree languages and pushdown automata. Turing machines and equivalent models of computation. Computability. Introduction to complexity. An appropriate programming language is used for programming experiments. 
Prerequisites:  CS 250, 251. 
Goals:  The main goal of the course is that students obtain those skills in the theoretical foundations of computing that are used in the study and practice of computer science. A second goal is that students become familiar with Prolog as an experimental tool for testing properties of computational structures.
Upon the successful completion of this course students will be able to:

Textbooks:  Introduction to the Theory of Computation, Michael Sipser, 2012 
References:  none 
Major Topics: 

Laboratory Exercises: 
CAC Category Credits  Core  Advanced 
Data Structures  
Algorithms  
Software Design  
Computer Architecture  
Programming Languages  0.3 
Oral and Written Communications:  Every student is required to submit 3 written reports (not including exams, tests, quizzes, or commented programs) of typically 10 pages in a lab notebook. 
Social and Ethical Issues:  None 
Theoretical Content:  The entire course is theoretical material (algebraic and computational structures). 
Problem Analysis:  The course is devoted to problem solving techniques of algebra and computability. The exercises and tests require problem analysis to find out which tools of algebra and computability are needed to solve a problem. 
Solution Design:  The course is devoted to problem solving techniques. The exercises and tests require students to solve problems by applying the tools of algebra and computability. 