Discrete Structures

Unit I : Sets and Propositions

Sets, Combination of sets, Finite and Infinite sets, Un-countably infinite sets, Principle of inclusion and exclusion, multisets. Propositions, Conditional Propositions, Logical Connectivity, Propositional calculus, Universal and Existential Quantifiers, Normal forms, methods of proofs, Mathematical Induction.

Unit II : Groups and Rings

Algebraic Systems, Groups, Semi Groups, Monoid, Subgroups, Permutation Groups, Codes and Group codes, Isomorphism and Automorphisms, Homomorphism and Normal Subgroups, Ring, Integral Domain, Field, Ring Homomorphism, Polynomial Rings and Cyclic Codes.

Unit III : Relations and Functions

Properties of Binary Relations, Closure of relations, Warshall’s algorithm, Equivalence Relations and partitions, Partial ordering relations and lattices, Chains and Anti chains. Functions, Composition of functions, Invertible functions, Pigeonhole Principle, Discrete Numeric functions and Generating functions, Job scheduling Problem.

Recurrence Relations Recurrence Relation, Linear Recurrence Relations With constant Coefficients, Homogeneous Solutions, Total solutions, solutions by the method of generating functions.

Unit IV : Graphs

Basic terminology, multi graphs and weighted graphs, paths and circuits, shortest path in weighted graph, Hamiltonian and Euler paths and circuits, factors of a graph, planer graph and Travelling salesman problem.

Unit V : Trees

Trees, rooted trees, path length in rooted trees, prefix codes, binary search trees, spanning trees and cut set, minimal spanning trees, Kruskal’s and Prim’s algorithms for minimal spanning tree, The Max flow –Min cut theorem (transport network).

Unit VI : Permutations, Combinations and Discrete Probability

Permutations and Combinations: rule of sum and product, Permutations, Combinations, Algorithms for generation of Permutations and Combinations. Discrete Probability, Conditional Probability, Bayes’ Theorem, Information and Mutual Information.

Text Books:

1. C. L. Liu and D. P. Mohapatra, “Elements of Discrete Mathematics”, SiE Edition, TataMcGraw-Hill, 2008, ISBN 10:0-07-066913-9

2. R.Johnsonbaugh,“Discrete Mathematics”,5thEdition,PearsonEducation,2001ISBN81–7808–279-9 (Recommended for Unit I and Unit II)

Reference Books:

1. N. Biggs,“Discrete Mathematics”,3rdEdition,Oxford University Press, ISBN 0–19–850717- 8

2. Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 6th edition, McGraw-Hill, 2007. ISBN 978-0-07-288008-3

3. E. Goodaire and M.Parmenter,“Discrete Mathematics with Graph Theory”,2nd edition,Pearson Education,2003 ISBN 81–7808–827–4

4. Semyour Lipschutz & Marc Lipson,“Discrete Mathematics”,McGraw-Hill,3 rd Special Indian Edition, ISBN-13 : 978-0-07-060174-1

5. B. Kolman,R.Busby and S. Ross,“Discrete Mathematical Structures”,4th Edition,Pearson Education,2002, ISBN 81-7808-556-9

6. N. Deo, “Graph Theory with application to Engineering and Computer Science”, Prentice Hall of India,1990, 0 – 87692 – 145 – 4

Discrete Mathematics with Graph Theory

Goodaire