ICS 441

Foundations of Computing Theory

4 Undergraduate credits
Effective August 1, 1998 – Present

Graduation requirements this course fulfills

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.

Special information

Note: ICS 340 Data Structures recommended pre-requisites. 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.

Learning outcomes

General

  • 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.
  • Construct and manipulate context-free grammars, and simulate them with pushdown automata.
  • Construct and manipulate finite automata and associated regular languages.