210241: DISCRETE STRUCTURES
Teaching SchemeExamination Scheme Lectures: 4 Hrs./week Theory: 100 Marks
Prerequisite: Knowledge of Elementary Mathematics
To learn formal logic, proofs, sets, relations and functions
To use formal logic proofs and logical reasoning to solve problems
To relate the ideas of mathematical induction to recursion and recursively defined structures
To learn graphs, trees and related algorithms
To apply these concepts to various areas of computer science
Logic and Proofs
Propositions, Conditional Propositions, Logical Connectivity, Prepositional calculus, Universal and Existential Quantifiers, Proofs, Proof Techniques, Mathematical Induction
Set Theory - Set, Combination of sets, Finite and Infinite sets, Un-countably infinite sets, Principle of inclusion and exclusion (8)
Combinatorics and Discrete Probability
Permutations and Combinations: rule of sum and product, Permutations, Combinations, Algorithms for generation of Permutations and Combinations.
Discrete Probability, Conditional Probability, Information and Mutual Information, Binomial Coefficients and Combinatorial Identities. (8)
Definitions, Properties of Binary Relations, Equivalence Relations and partitions, Partial ordering relations and lattices, Chains and Anti chains.
Definitions, domain, Range, One-to-One and OnTo, Inverse and Composition, Pigeonhole Principle, Discrete Numeric functions and Generating functions, Job scheduling Problem.
Recurrence Relation, Linear Recurrence Relations With constant Coefficients, Homogeneous Solutions, Total solutions, solutions by the method of generating functions (10)
Basic terminology, multi graphs and weighted graphs, paths and circuits, shortest path in weighted graph, Hamiltonian and Eulerian paths and circuits, factors of a graph, planer graph and Traveling salesman problem. (8)
Trees, rooted trees, path length in rooted trees, prefix codes, binary search trees, spanning trees and cut set, minimal spanning trees, Kruskal’s and prime’s