Foundations of Computing

Learning Outcomes COMP1600

(see also Programs and Courses)

Upon successful completion, students will have the knowledge and skills to:

• Apply the concepts of standard mathematical logic to produce proofs or refutations of well-formed propositions or arguments phrased in English or in a variety of formal notations (first order logic, discrete mathematics or Hoare Logic).

• Given a description of a regular language, either in English, as a regular expression or as a grammar, generate a finite state automaton that recognizes that language. Similarly, given a deterministic or nondeterministic automaton, give a description of the language which it accepts.

• Given an inductive definition of a simple data structure, write a recursive definition of a given simple operation on data of that type. Given some such recursively defined operations, prove simple properties of these functions using the appropriate structural induction principle.

• Prove simple programs correct using Hoare Logic.

• Design a Turing Machine which will accomplish simple tasks.

Learning Outcomes COMP6260

(see also Programs and Courses)

Upon completion of this course, the student will be able to do the following:

• Apply the concepts of standard mathematical logic to produce proofs or refutations of well-formed propositions or arguments phrased in English or in a variety of formal notations (first order logic, discrete mathematics or Hoare logic). Express problems, presented in English, in these formal notations and demonstrate an awareness of the differences between them.

• Generate a finite state automaton that recognises a given regular language either described in English or presented as a regular expression; similarly, describe the language accepted by a given deterministic or nondeterministic automaton.

• Relate structural induction to other forms of mathematical induction, and write a recursive definition of a given simple operation on data of a given type presented via an inductive definition of the data structure.

• Explain the concept of program correctness and prove simple programs correct using Hoare Logic.

• Demonstrate understanding of Turing Machine computability, and design Turing Machines to accomplish simple tasks.