Expected Learning Outcomes:
1) To provide overview of theory of discrete objects, starting with relations and partially ordered sets.
2) Study about recurrence relations, generating function and operations on them.
3) Give an understanding of graphs and trees, which are widely used in software.
4) Provide basic knowledge about models of automata theory and the corresponding formal languages.
10
Unit I
Recurrence Relations
(a) Functions: Definition of function. Domain, co domain and the range of a function.
Direct and inverse images. Injective, surjective and bijective functions. Composite
and inverse functions.
(b) Relations: Definition and examples. Properties of relations , Partial Ordering sets,
Linear Ordering Hasse Daigrams , Maximum and Minimum elements, Lattices
(c) Recurrence Relations: Definition of recurrence relations, Formulating recurrence
relations, solving recurrence relations- Back tracking method, Linear homogeneous
recurrence relations with constant coefficients. Solving linear homogeneous
recurrence relations with constant coefficients of degree two when characteristic
equation has distinct roots and only one root, Particular solutions of non linear
homogeneous recurrence relation, Solution of recurrence relation by the method
of generation functions, Applications- Formulate and solve recurrence relation for
Fibonacci numbers, Tower of Hanoi, Intersection of lines in a plane, Sorting
Algorithms.
15L
Unit II
Counting Principles , Languages and Finite State Machine
(a) Permutations and Combinations: Partition and Distribution of objects,
Permutation with distinct and indistinct objects, Binomial numbers, Combination
with identities: Pascal Identity, Vandermonde’s Identity, Pascal triangle, Binomial
theorem, Combination with indistinct objects.
(b) Counting Principles: Sum and Product Rules, Two-way counting, Tree diagram for
solving counting problems, Pigeonhole Principle (without proof); Simple examples,
Inclusion Exclusion Principle (Sieve formula) (Without proof).
(c) Languages, Grammars and Machines: Languages , regular Expression and Regular
languages, Finite state Automata, grammars, Finite state machines, Gödel
numbers, Turing machines.
15L
Unit III
Graphs and Trees
(a) Graphs : Definition and elementary results, Adjacency matrix, path matrix,
Representing relations using diagraphs, Warshall’s algorithm- shortest path ,
Linked representation of a graph, Operations on graph with algorithms - searching
in a graph; Insertion in a graph, Deleting from a graph, Traversing a graphBreadth-First search and Depth-First search.
(b) Trees: Definition and elementary results. Ordered rooted tree, Binary trees,
Complete and extended binary trees, representing binary trees in memory,
traversing binary trees, binary search tree, Algorithms for searching and inserting
in binary search trees, Algorithms for deleting in a binary search tree
15L
11
Textbook:
1. Discrete Mathematics and Its Applications, Seventh Edition by Kenneth H. Rosen, McGraw Hill Education
(India) Private Limited. (2011)
2. Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon Press, Oxford 1989.
3. Data Structures Seymour Lipschutz, Schaum’s out lines, McGraw- Hill Inc.
Additional References:
1. Elements of Discrete Mathematics: C.L. Liu , Tata McGraw- Hill Edition .
2. Concrete Mathematics (Foundation for Computer Science): Graham, Knuth, Patashnik Second Edition,
Pearson Education.
3. Discrete Mathematics: Semyour Lipschutz, Marc Lipson, Schaum’s out lines, McGraw- Hill Inc.
4. Foundations in Discrete Mathematics: K.D. Joshi, New Age Publication, New Delh