DISCRETE STRUCTURES (6 SCU)

Learning Outcomes:

Upon successful completion of this course, students are expected to be able to understand the notion of mathematical thinking, mathematical proofs, and algorithmic thinking, and be able to apply them in problem solving; understand the basics of discrete probability and number theory, and be able to apply the methods from these subjects in problem solving; use effectively algebraic techniques to analyse basic discrete structures and algorithms; understand asymptotic notation, its significance, and be able to use it to analyse asymptotic performance for some basic algorithmic examples; understand some basic properties of graphs and related discrete structures, and be able to relate these to practical examples; apply discrete structures into other computing problems such as formal specification, verification, databases, and cryptography; and apply formal logic proofs and/or informal, but rigorous, logical reasoning to real problems, such as predicting the behaviour of software or solving problems such as puzzles.

Topics:

This course introduces students to basic concepts of discrete mathematics in order to develop a mathematical maturity and ability to deal with abstraction. The course materials serve the interests of the students in relation to further study in pure and applied mathematics, computer science and engineering. Topics covered in this course include concepts of logic and proof; concepts of the language of mathematics including sets, sequences, number systems, relations; algorithms; concepts of counting methods such as permutations and combinations, and discrete probability; concepts of graphs and trees; and Boolean algebra. In addressing the problems students will also gain skills in writing grammars, automata manipulations, regular expressions, proof techniques and reasoning about computational capabilities.

Pre-requisite: None