Faculty of Science

Objectives

This course introduces the student to the theoretical foundations of Computer Science. Students taking the course are expected to have knowledge in mathematics equivalent to or better than GCE advanced level algebra.

Contents

Basics of counting Counting arguments. Set cardinality and counting. Sum and product rule. Inclusion-exclusion principle. Arithmetic and geometric progressions. The pigeonhole principle. Permutations and combinations: Basic definitions, Pascal’s identity, The Binomial theorem. Basic modular arithmetic. Sets, Relations, and Functions Sets: Venn diagrams; Union, intersection, complement; Cartesian product; Power sets; Cardinality of finite sets. Relations: Reflexivity, symmetry, transitivity; Equivalence relations, partial orders. Functions: Surjections, injections, bijections; Inverses; Composition

Basic Logic Propositional logic: Logical connectives; Truth tables; Normal forms (conjunctive and disjunctive); Validity of well-formed formula. Propositional inference rules (concepts of modus ponens and modus tollens). Predicate logic: Universal and existential quantification. Limitations of propositional and predicate logic (e.g., expressiveness issues)

Proof Techniques: Notions of implication, equivalence, converse, inverse, contrapositive, negation, and contradiction. The structure of mathematical proofs. Direct proofs. Disproving by counterexample. Proof by contradiction. Induction over natural numbers. Structural induction. Weak and strong induction (i.e., First and Second Principle of Induction). Recursive mathematical definitions. Well orderings.

Basic Automata, Computability, and Complexity. Finite-state machines. Regular expressions. The halting problem. Context-free grammars. Introduction to the P and NP classes and the P vs NP problem. Introduction to the NP-complete class and exemplary NP-complete problems (e.g., SAT, Knapsack)