Logic: Propositions, truth tables, logical equivalence, predicates and qualifiers. Sets, relations and functions: operations, subsets, power sets, Cartesian products, generalized unions and intersections; partial and total orders, equivalence relations, partitions and equivalence classes. Proofs: rules of inferences, fallacies, universal/existential instantiation/generalizations, methods of proving theorems; proof by mathematical induction; Algorithms: pseudocodes, search algorithms, Euclidean algorithm, recursive algorithm, complexity of algorithms. Graph theory: isomorphic graphs, planar graphs, Euler characteristics, representation of graphs, trees, weighted graphs. Boolean algebra and logic circuits. Recurrence, recurrence relations, solving recurrence relations.
Contact hours:
5 lectures/tutorials per week.Assessment:
2 tests (25%), 3e assignments (15%) and final exam (60%)Prerequisite: 1.10802
Text:
Rosen, K. H., 1999, Discrete Mathematics and Its Applications, 4th Edition, WCB/McGraw-Hill, London