The page uses Browser Access Keys to help with keyboard navigation. Click to learn moreSkip to Navigation

Different browsers use different keystrokes to activate accesskey shortcuts. Please reference the following list to use access keys on your system.

Alt and the accesskey, for Internet Explorer on Windows
Shift and Alt and the accesskey, for Firefox on Windows
Shift and Esc and the accesskey, for Windows or Mac
Ctrl and the accesskey, for the following browsers on a Mac: Internet Explorer 5.2, Safari 1.2, Firefox, Mozilla, Netscape 6+.

We use the following access keys on our gateway

n Skip to Navigation
k Accesskeys description
h Help
    Davidson College
  Oct 19, 2017
Catalog 2017-2018
[Add to Portfolio]

CSC 324 - Theory of Computation


Mathematical models of computation, and the fundamental capabilities and limitations of computers.  Topics include regular languages, finite automata, context-free languages, grammars, Turing machines, the Chomsky hierarchy, the halting problem, algorithms, decidable and undecidable problems, algorithmic reductions, complexity theory, the classes P, NP, and PSPACE, and NP-complete problems.

Counts towards the Mathematics major and minor.
Counts towards the Computer Science major and minor.

Prerequisites & Notes
One of Mathematics 220, 230, or 255. (Offered Spring of odd-numbered years.)

[Add to Portfolio]