CIS Logo SVC Logo

   Computing & Information Systems


Schoology Facebook        Search CIS Site      Tutorials

CS 171 Home Page

Inntroduction to Computability

Spring 2020

This course emphasizes the mathematical and theoretical foundations of computer science. The primary topics are computability theory and Turing machines, complexity theory (including the classes P, NP, NP-complete, and NP hard), grammars and parsing, push-down automata, and running time analysis (especially using recurrence relations and generating functions). Important fundamental questions will be answered, such as whether all functions are computable and the existence of unsolvable problems. Also included is an introduction to proofs of program correctness and some running time analysis for algorithms to solve the traveling salesperson problem.

Further Information

Examples and Class Materials

Homework and Announcements

  • Now in Schoology

Instructor: Br. David Carlson

Maintained by: Br. David Carlson
Last updated: January 15, 2020