Discrete Structures

CMSACOR04T: Discrete Structures Theory: 75 Lectures AdditionalTutorial: 15 Lectures

1. Introduction: (20 Lectures) 

Sets - finite and Infinite sets, uncountably Infinite Sets;

 functions,relations, Properties of Binary Relations, Closure, Partial Ordering Relations;

 counting - Pigeonhole Principle, Permutation andCombination; 

Mathematical Induction, Principle of Inclusion and Exclusion.

2. Growth of Functions: (10 Lectures) Asymptotic Notations, 

Summation formulas and properties, 

Bounding Summations, 

approximation by Integrals

3. Recurrences: (12 Lectures) 

Recurrence Relations, generating functions, 

Linear RecurrenceRelations with constant coefficients and their solution, 

Substitution Method, Recurrence Trees, 

Master Theorem

4. Graph Theory (18 Lectures) 

Basic Terminology, Models and Types, 

multigraphs and weighted graphs,

 Graph Representation, Graph Isomorphism,

 Connectivity, 

Euler and Hamiltonian Paths and Circuits, 

Planar Graphs, Graph Coloring, 

Trees, Basic Terminology and properties of Trees, 

Introduction to Spanning Trees

5. Prepositional Logic (15 Lectures) 

Logical Connectives, Well-formed Formulas, Tautologies,

 Equivalences, Inference Theory