CS147-10 Discrete Mathematics and Its Applications 2

Introductory description

This module is designed to introduce students to language and methods of the area of Discrete Mathematics.

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Big-Oh notation and its use in the analysis of algorithms.
Basic concepts from graph theory; such as trees, matchings, euler tours, colorings and cuts.
Applications of discrete probability; such as probabilistic method, random walks and entropy.

Learning outcomes

By the end of the module, students should be able to:

• Understand the notion of mathematical thinking, mathematical proofs, and algorithmic thinking, and be able to apply them in problem solving.
• Understand asymptotic notation, its significance, and be able to use it to analyse the runtimes of algorithms.
• Understand some basic properties of graphs and discrete probability, and be able to apply the methods from these subjects in problem solving.

Indicative reading list

To be finalised.

Subject specific skills

Basic knowledge of graph theory and its applications in algorithms
Basic knowledge of discrete probability and its applications in algorithms
Understanding and using asymptotic notations in design and analysis of algorithms

Transferable skills

Communication - Reading and writing mathematical proofs
Critical thinking - problem solving