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.
- 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.