Block 1: Basic set theory and a little combinatorics

Sets, standard sets, universal sets, set notation, ways of describing sets, cardinality, subsets, proper subsets, the power set of a set, Venn diagrams, union, intersection, set difference, complement of a set, disjoint sets, the definition of a partition, product sets.

The multiplication principle, bits, binary strings, the number of elements in the power set, the number of binary strings of length n, the addition principle, the principle of inclusion-exclusion for 2 and 3 sets, permutations, combinations.

Block 2: Sequences, sigma notation and number systems

Sequences, defined both recursively and by general term. Sigma (summation) notation, conversion from Sigma notation to long notation and vice versa. Number systems, conversion between number systems, the Division Algorithm.

Block 3: Basic number theory for integers

Factors, divisors, multiples, rules for the 'divides'-relation, units, composite numbers, primes, a basic primality test. Linear combinations, gcd, Euclid's algorithm (forwards and backwards). They must know that the numbers that can be written as linear combinations of m and n are precisely all the multiples of the gcd(m,n). Prime factorisation, the Fundamental Theorem of Arithmetic.

Block 4: Modular arithmetic, relations and functions

Congruence modulo n, rules of arithmetic modulo n, the division algorithm revisited, congruence classes mod n, know that they partition Z, class representatives, even/odd numbers. Definition of Z_n, definition of multiplication and addition in Z_n, rules of arithmetic for Z_n, multiplication and addition tables for Z_n, zero-divisors, the zero-divisor law holds for Z_p, when p prime, for no other n. Multiplicative inverses and when they exist, when can cancellation be done in equations in Z_n. Know that multiplicative inverses are unique, using Euclid's algorithm to find multiplcative inverses. Solution to equations modulo n/ equations in Z_n.

Relations on sets, the digraph of a relation.
Properties of relations: reflexivity, symmetry, antisymmetry, transitivity, how to 'see' these from the relation digraph.
Partial orders, complete orders, equivalence relations, equivalence classes, know that the equivalence classes of a relation on X partition X.

Functions, with emphasis on discrete functions. The floor and ceiling function. 1-1, onto, bijections, inverses.

Block 5: Logic and Proof

Basic propositional logic: propositions, negation, and, or, contradiction, tautology, truth tables, rules of logic, if-then statements, truth table for p implies q, the quantifiers 'for all' and 'there exists', the contrapositive statement of p implies q.

Proof: what it means to be 'well-defined', direct proof, using the contrapositive statement to prove a statement, proof by contradiction, proving biconditional statements, proof by counterexample, proof by induction, using induction to prove a conjectured general term for a sequence defined by a recurrence relation.

Solution of linear homogeneous recurrence relations with constant coefficients.

Block 6: Graph Theory

Terminology: Graph, edge, vertex, loops, parallel/multiple edge, simple graph, vertex v incident/not incident with edge e, vertex v adjacent/not adajcent to vertex w, digraph, arc, connected graph, components of a graph, spanning trees. Ways of representing graphs: Diagrams, adjacency lists, adjacency matrix, incidence matrix. The Handshaking Lemma (including proof). Isomorphisms of graphs: be able to prove whether two small graphs are isomorphic or not. Special graphs: The complete graphs, bipartite graphs, trees, cycle-graphs. Paths, cycles, Euler cycles, Hamiltonian cycles. Weighted graphs: Dijkstra's algorithm for finding the shortest path between two vertices in a weighted graph, Prim's and Kruskal's algorithms for finding minimal spanning trees.