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 a computer scientist.
Timetable details for 2021 are no longer published.
This information is from current details held on the Student Information System. Please report any errors or omissions to the relevant College Office.
You consent to the use of our cookies if you proceed.