Discrete Mathematics

Overview

In order to be able to formulate what an algorithm is supposed to achieve, or to prove that it does meet its specification, or to reason about its time and space complexity, the computing scientist needs to absorb and master a number of mathematical ideas, notations and techniques. For instance, to specify computational problems in suitably abstract terms one needs to understand basic ideas of sets, relations and functions. To prove that a proposed solution actually does work, one needs to understand the principles of mathematical logic, including mathematical induction. One also needs to be familiar with the properties of common functions, of permutations, of orderings and their properties, and so on. Finally, to reason about the complexity of programs, one needs to master recurrence relations, summations, and asymptotic notation. The Discrete Mathematics course addresses some of this mathematical background, leaving out the material on logic and proof, which is provided in a separate course.

Learning Outcomes

This is an introductory course on discrete mathematics.

Students will:

• Learn a number of fundamental mathematical concepts, definitions and results.
• Learn how certain mathematical results can be proved by induction
• Learn how to use recursive definitions, and to analyse them.
• Learn how to count different types of discrete mathematical structures