BSc CS sem 1 Discrete Mathematics techmax/notes Download


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