Discrete Structures — DU B. Voc – Software Development Previous Year Question Papers

CREDIT DISTRIBUTION, ELIGIBILITY AND PRE-REQUISITES OF THE COURSE Course title Credits Credit distribution of the Eligibility Pre- & Code course criteria requisite Lecture Tutorial Practical/ of® the Practice course Discrete 4 3 0 1 Class XII NIL Structures with Learning objectives: 1. To teach students how to think logically and mathematically. 2. To stress on mathematical reasoning and describe different ways in which mathematical problems could be solved. 3. To cover four thematic areas: mathematical reasoning, combinatorial analysis, discrete structures, and mathematical modelling. 4. To touch upon topics like logic, proofs, set theory, counting, probability theory (the discrete part of the subject), graph theory, trees, Boolean algebra, and modelling computation. Learning Outcomes: 1. Relate mathematical concepts and terminology to examples in the domain of Computer 2. Model real world problems using various mathematical constructs. 3. Use different proofing techniques; construct simple mathematical proofs using logical arguments. 4. Divide a problem or a proof into smaller cases. 5. Formulate mathematical claims and construct counterexamples. UNT-1 (7 hours) Sets, Functions, Sequences and Summations, Relations. Sets: Set Operations, Computer Kepresentation of Sets, Countable and Uncountable Set, Principle of Inclusion and Exclusion, Multi-sets; Functions: One-to-one and Onto Functions, Inverse Functions and Compositions of Functions, Graphs of Functions Sequences and Summations: Sequences, Special Integer Sequences, Summations; Relations: Properties of Binary Relations, Equivalence relations and Partitions, Partial Ordering Relations and Lattices. UNIT-II (8 hours) Logic and Proofs. Propositional Logic, Propositional Equivalences, Use of first-order logic to express natural language predicates, Quantifiers, Nested Quantifiers, Rules of Inference, Introduction to Proofs, Proof Methods and Strategies, Mathematical Induction. UNIT-II (7 hours) Number Theory. Division and Integers, Primes and Greatest Common Divisors, Representation of Integers, Algorithms for Integer Operations, Modular Exponentiation, Applications of Number UNIT-IV (8 hours) Combinatorics/Counting. The Pigeonhole Principle, Permutations and Combinations, Binomial Coefficients, Generalized Permutations and Combinations, Generating Permutations and UNIT-V (10 hours) Graphs and Trees. Graphs: Basic Terminology, Multigraphs and Weighted Graphs, Paths and Circuits, Eulerian Paths and Circuits, Hamiltonian paths and Circuits, Shortest Paths, Spanning Trees, Graph Isomorphism, Planar Graphs; Trees: Trees, Rooted Trees, Path Lengths in Rooted UNIT-VI (5 hours) Recurrence. Recurrence Relations, Generating Functions, Linear Recurrence Relations with Constant Coefficients and their solution. 1. C.L. Liu & Mahopatra, Elements of Discrete mathematics. 3'd edition. Tata McGraw 2. Kenneth R., Discrete Mathematics and Its Applications. O' edition. Mc Graw Hill. List of practicals (30 Hours)