210241: DISCRETE STRUCTURES
Teaching Scheme Examination Scheme
Lectures: 4 Hrs/week Theory: 100 Marks
Discrete mathematics- the mathematics of integers and of collections of object –
underlies the operation of digital computer, and is used widely in all fields of
computer science for reasoning about data structures algorithms and complexity. The
primary objective of subject is to prepare students mathematically for the study of
computer engineering. Topics covered in the course include proof techniques, logic
and sets, functions, relations, counting techniques, probability and recurrences. By the
end of the course, students should be able to formulate problems precisely, solve the
problems, apply formal proof techniques, and explain their reasoning clearly.
Prerequisite: Basic Mathematics
Learning objectives: … the student will be able to
· Use appropriate set, function, or relation models to analyze practical
examples, interpret the associated operations and terminology in context.
· Determine number of logical possibilities and probability of events
· Learn logic and proof techniques to expand mathematical maturity
· Formulate problems precisely, solve the problems, apply formal proof
techniques, and explain their reasoning clearly.
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 (8 Hrs)
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
(8 Hrs)
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 (10 Hrs)
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. (8 Hrs)
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). (8 Hrs)
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
(8 Hrs)
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”, 5th Edition, Pearson Education, 2001
ISBN 81 – 7808 – 279 - 9 (Recommended for Unit I and Unit II)
Reference Books:
1. N. Biggs, “Discrete Mathematics”, 3rd Edition, 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, 3rd
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
Teaching Scheme Examination Scheme
Lectures: 4 Hrs/week Theory: 100 Marks
Discrete mathematics- the mathematics of integers and of collections of object –
underlies the operation of digital computer, and is used widely in all fields of
computer science for reasoning about data structures algorithms and complexity. The
primary objective of subject is to prepare students mathematically for the study of
computer engineering. Topics covered in the course include proof techniques, logic
and sets, functions, relations, counting techniques, probability and recurrences. By the
end of the course, students should be able to formulate problems precisely, solve the
problems, apply formal proof techniques, and explain their reasoning clearly.
Prerequisite: Basic Mathematics
Learning objectives: … the student will be able to
· Use appropriate set, function, or relation models to analyze practical
examples, interpret the associated operations and terminology in context.
· Determine number of logical possibilities and probability of events
· Learn logic and proof techniques to expand mathematical maturity
· Formulate problems precisely, solve the problems, apply formal proof
techniques, and explain their reasoning clearly.
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 (8 Hrs)
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
(8 Hrs)
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 (10 Hrs)
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. (8 Hrs)
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). (8 Hrs)
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
(8 Hrs)
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”, 5th Edition, Pearson Education, 2001
ISBN 81 – 7808 – 279 - 9 (Recommended for Unit I and Unit II)
Reference Books:
1. N. Biggs, “Discrete Mathematics”, 3rd Edition, 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, 3rd
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
No comments:
Post a Comment