COMP8781 Computer Mathematics GE

2015

4.5

3 x 60-minute lectures weekly
1 x 90-minute tutorial weekly

COMP2781 has been successfully completed

A good background in algebra is required. In particular students are expected to know how to solve linear and quadratic equations, and be able to manipulate algebraic expressions. Basic knowledge of elementary functions and their graphs is also desirable. Students without the assumed knowledge should check with the topic coordinator as to the background required, as there will be no additional assistance to compensate for missing background.

This topic includes: Basic Logic (propositional logic, truth tables, tautology, contradiction, logical equivalences, predicate logic, quantifiers, valid arguments); Proof Techniques and Elementary Number Theory (nature of proof, direct/indirect proofs, mathematical induction, proofs by contradiction, existence and constructive proofs, counterexamples, divisibility, factorization theorem, quotient-remainder theorem); Functions, Relations, Sets (set theoretic proofs, functions, cardinality, partial order relations), Basics of Counting (addition/multiplication principle, permutations and combinations, pigeonhole principle, binomial theorem); Recursion (method of iteration, second-order linear homogeneous relations, recursive definitions); Elements of Cryptography (modular arithmetic, congruence relations, Euclid's lemma, Fermat's Little Theorem, Chinese Remainder Theorem, RSA cipher); Graphs and Trees (paths and circuits, Euler and Hamiltonian circuits, matrix representations, Dijkstra's shortest path algorithm, isomorphism of graphs, spanning trees, minimum spanning trees, Kruskal's algorithm). Variety of applications of the covered material will be discussed throughout the topic.

This topic builds a solid discrete mathematics and logic foundation for an IT professional.

At the completion of this topic, students are expected to be able to:

1. Understand and apply formal logic system on which mathematical reasoning is based
2. Analyse and construct valid mathematical arguments - proofs - and understand mathematical statements - theorems
3. Utilize important discrete date structures such as sets, relations, discrete functions, graphs and trees
4. Use various problem-solving strategies including algorithmic thinking (both iterative and recursive) and various counting techniques to create appropriate solutions to computing problems
5. Understand the importance of formal mathematical structures and techniques for computing applications
6. Conduct independent individual studies in discrete mathematics areas, extending those covered in the topic, with the level of understanding allowing for practical applications of the material