The prerequisites for this course are C or better in CS 211 and Math 125. You are expected to have a strong mathematical background and be able to reason abstractly. Programming skill is assumed and you should be comfortable with C or C++.
In this course we will look at the mathematical logic which underlies computer science, formal languages, and at abstactions which model the processes of computation.
From logic we will discuss basic propositional and predicate logic with application to validating programs. We will also have an introduction to logic programming using the programming language Prolog.
We will investigate regular expressions and context-free grammars as formal languages along with their relations to finite automata and push-down automata. In addition to the importance these subjects have to the theory of computer science they have applications to compiler writing and computer translation in general. We will use the programming tool Lex to see some practical application of regular expressions.
Turing Machines provide a formal model of computation. They are used to study, among other things, the limits of computation and complexity of algorithms. We will become acquainted with fundamental ideas from this area.
There will be regular homework, programming assignments, a midterm and a final exam. No late homework will be accepted. Late programs will be accepted but with a five points (out of 100) per day late penalty. There will be no makeup exams except for extreme and well-justified (as judged by me) cases. Grades will be computed from a scored weighted by: