Mathematics I

PURPOSE
To introduce learners to a selection of topics from Discrete Mathematics which are relevant to study and application in the field of Information Technology.

LEARNING OUTCOMES

• Define and identify the elements of logical expressions (atomic propositions, logical operations - negation, conjunction, disjunction, implication, equivalence, compound propositions).
• Demonstrate knowledge of logical variables, logical operators and operator precedence by formalizing natural language statements as syntactically and semantically correct logical expressions and by evaluating logical expressions.
• Produce truth tables for compound expressions.
• Define tautology, contradiction, contingency, logical equivalence, logical implication.
• Use truth tables to verify/refute the aforementioned.
• Use the Laws of Logic to verify/refute the aforementioned and simplify expressions.
• Use deductive proofs (Rules of Inference) to test the validity of arguments.
• Define sets, including the empty set, and the universal set with specific reference of the standard universal sets.
• Describe sets by enumeration and comprehension.
• Define and evaluate set cardinality.
• Define and use set equality and set inclusion.
• Define and obtain power sets and evaluate their cardinality.
• Define and use set operations.
• Know and apply the Principle of Inclusion and Exclusion.
• Recall and use the laws of set theory to simplify set algebraic expressions and to prove set identities.
• Explain what sequences are.
• Evaluate the general term of, and enumerate a sequence.
• Recognize and describe the difference between recursive and non-recursive definitions.
• Define sequences by means of recursive definitions and enumerate sequences defined recursively.
• Recall and use the division theorem.
• Define and establish divisibility.
• Recognize and use the ?mod? function.
• Define modular congruence and perform congruence arithmetic.
• Define prime and composite numbers, demonstrate use of the Sieve of Eratosthenes, and find prime factorisations using trial division. Knowledge and use of the smallest prime factor theorem is essential.
• Recall the Fundamental Theorem of Arithmetic.
• Define the greatest common denominator, determine by factorisation and by the Euclidean algorithm.
• Define the term coprime (relatively prime) and test for coprimality.
• Recall the linear combination theorem and express the gcd as a linear combination.
• Recall the theorem regarding the divisibility of congruences, define and obtain the inverse modulo m and define and solve linear congruences.
• Demonstrate the application of number theory to: hash functions, pseudorandom number generators, and simple ISBN check digit evaluation and the correction of single digit errors.
• Discuss and analyze cryptosystems with reference to: encryption and decryption, keys and keyspaces, shift ciphers, and affine ciphers.
• Define and recognize matrices and vectors and demonstrate knowledge of the notation used to refer to matrices, vectors, and their elements.
• Demonstrate knowledge of matrix terminology i.e. element, row vector, column vector, square matrix, null matrix, identity matrix, unit matrix, diagonal element, principal diagonal, diagonal matrix, symmetric matrix, triangular matrix.
• Evaluate matrix algebra expressions involving equality, transposition, addition, subtraction, scalar multiplication, vector product, matrix product, matrix power, including the join, meet, product and powers of Boolean matrices.
• Define, explain and recognize essential graph theoretical terminology.
• Know and apply selected graph theoretical theorems.
• Represent graphs using adjacency matrices and know and apply essential theorems relating to their use to answer questions regarding connectivity of graphs.
• Use Dijkstra's algorithm to solve shortest path problems.
• Define and identify trees, subtrees, and rooted trees and with regard to the vertices of rooted trees: root, parent, child, sibling, ancestor, descendant, internal vertex, leaf, level, height, balanced tree, m-ary tree, full m-ary tree, and binary tree.
• Recall and use the theorems relating to trees.
• Perform the three tree traversal algorithms: inorder, preorder, postorder.
• Demonstrate the use of binary trees for binary search trees, prefix codes and expression trees.
• Define spanning trees and minimum spanning trees and produce minimum spanning trees by means of Prim?s algorithm.

CORE CONTENT

• Propositional logic.
• Set theory.
• Sequences and recursion.
• Number theory and applications.
• Elementary matrix algebra.
• Graph structures and applications.
• Tree structures and applications.