Skip to main content
Metropolitan State University (Home)

ICS 441 Foundations of Computing Theory

This course establishes the mathematical and logical foundations of the discipline of computer science, with a concentration on the foundations of algorithmics. The concept of Turing Machines is used throughout the course as the means to establish these foundations. It uses these foundations to address the issues theoretically unsolvable problems, and of time and space complexity of algorithms for solvable problems.

Prerequisites

Special information

First day attendance is mandatory.
Note: ICS 340 Data Structures recommended pre-requisite. Students are responsible to both be aware of and abide by prerequisites for ICS courses for which they enroll, and will be administratively dropped from a course if they have not met prerequisites.
4 Undergraduate credits

Effective August 1, 1998 to present

Learning outcomes

General

  • Construct and manipulate context-free grammars, and simulate them with pushdown automata.
  • Construct and manipulate finite automata and associated regular languages.
  • Construct and manipulate Turing machines.
  • Determine whether specified computational problems are or are not solvable, and prove these assertions.
  • Prove theorems relating to finite automata, pushdown automata and Turing machines, using techniques including proof by construction, proof by induction, and proof by contradiction.
  • Use the concepts of deterministic and non-deterministic space complexity to determine the space complexity of algorithms for given problems, to determine the appropriate space complexity class for such algorithms (P, NP, NP-Complete, etc.), and to prove these assertions.
  • Use the concepts of deterministic and non-deterministic time complexity to determine the time complexity of algorithms for given problems, to determine the appropriate time complexity class for such algorithms (P, NP, NP-Complete, etc.), and to prove these assertions.