|(3 cr.) This course provides an introduction to the
classical theory of computer science. The aim is
to develop a mathematical understanding of the
nature of computing by trying to answer one
overarching question: What are the fundamental
capabilities and limitations of computers?
Specific topics include finite automata and formal
languages (How do we define a model of
computation?), computability (What can be
computed? and How do
we prove something cannot be computed?), and
complexity (What makes some problems so much
harder than others to solve? and What is the P
versus NP question and why is it important?).
Prerequisite: CSC 215 or MA 301; Minimum grade C-; Every Other Year, Fall|