MCS-033 Advanced Discrete Mathematics
(2 Credits)
Objectives
This course assumes the knowledge of the course MCS-013, “Discrete Mathematics”. In the two blocks of this course, we discuss recursion and graph theory, respectively. The first block is aimed at developing the understanding of a very important tool for analyzing recursive programmes, namely, recurrence relations. In the second block we aim to develop a basic understanding of graph theory, which is a very useful modeling tool for computer programming.
Syllabus
BLOCK 1:
Recurrences
Unit 1:
Recurrence Relations
·
The Fibonacci Sequences, The
Tower of Hanoi
, Catalan Numbers
·
Related Definitions
·
Divide and Conquer Methods
Unit 2
Generating Functions
·
Definitions and
Constructions
·
Applications for Finding the Number
of Integers Solutions of Linear Equations
·
Exponential Generating Functions
·
Solving Recurrence
Relations using Generating Functions
·
Applying Generating Functions for
Combinatorial Identities and Partitions
Unit 3
Solving Recurrences
·
Linear Homogeneous Recurrences
·
Linear Non- Homogeneous Recurrences
·
Methods of Inspection, Telescoping
Sums, Iteration, Substitution
BLOCK 2:
Graph Theory
Unit 1: Basic Properties of Graphs
·
What Graphs are
·
Degree, Regularity and Isomorphism
·
SubGraphs
Unit 2
Connectedness
·
Connected Graphs
o
Paths, Circuits and Cycles
o
Components
o
Connectivity
·
Bipartite Graphs
Unit 3
Eulerian and Hamiltonian Graphs
·
Eulerian Graphs
·
Hamiltonian Graphs
·
Travelling Salesperson Problem
Unit 4
Graph Colourings
·
Vertex Colouring
·
Edge Colouring
·
Planar Graphs
·
Map Colouring Problem