Colgate University Computer Science Department

This course is an introduction to the modern theory of computing. The course introduces students to different models of computation and focuses on the relative strength of each model, and the relationship of one model to another. Concepts introduced include sets and relations, data types, finite automata, regular expressions and languages, context-free grammars, push-down automata, Turing machines and Turing machine schema, diagonalization arguments, Church's Thesis, the Halting Problem, and computational complexity. In the required credit-bearing weekly two-hour laboratory, students acquire concrete experience experimenting with and implementing the concepts and computational strategies introduced in the lecture.

Format: Lecture and two-hour laboratory.

Prerequisites: COSC 102 and 290

Offered: Fall semester only

COSC Course Offerings for Spring 2008