•   Visitors:

Course Overview

• 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.

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 SumsIteration, Substitution

BLOCK 2 : Graph Theory

Unit 1 : Basic Properties of Graphs

What Graphs are
Degree, Regularity and Isomorphism SubGraphs

Unit 2 : Connectedness

Connected Graphs
Paths, Circuits and Cycles
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

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

Course Enquiry

Placed Learners