COMP109

Foundations of Computer Science

Aims

  1. To introduce the notation, terminology, and techniques underpinning the discipline of Theoretical Computer Science.
  2. To provide the mathematical foundation necessary for understanding datatypes as they arise in Computer Science and for understanding computation.
  3. To introduce the basic proof techniques which are used for reasoning about data and computation.
  4. To introduce the basic mathematical tools needed for specifying requirements and programs

Syllabus

  1. Number systems and proof techniques: natural numbers, integers, rationals, real numbers, prime numbers, proof by contradiction and proof by induction.
  2. Approaches to describing collections of objects: sets and set operations, unary and binary relations, properties of binary relations, partial orders and equivalence relations, inverse relations, and compositions of relations.
  3. Functions: properties of functions, inverse functions and compositions of functions, the pigeonhole principle.
  4. Propositional logic: syntax and construction of formulas, semantics, interpretations and truth tables, tautologies, contradictions, semantic consequence and logical equivalence
  5. Combinatorics: notation for sums, products, and factorials, Binomial coefficients, counting permutations, subsets, subsequences and functions.
  6. Discrete Probability: sample spaces, events, conditional probability, independence, random variables and expectation.

Learning Outcomes

  • Understand how a computer represents simple numeric data types; reason about simple data types using basic proof techniques;
  • Interpret set theory notation, perform operations on sets, and reason about sets;
  • Understand, manipulate and reason about unary relations, binary relations, and functions;
  • Apply logic to represent mathematical statement and digital circuit, and to recognise, understand, and reason about formulas in propositional and predicate logic;
  • Apply basic counting and enumeration methods as these arise in analysing permutations and combinations.