NPTEL Video lectures on Discrete Structure...

http://nptel.iitm.ac.in/video.php?subjectId=106106094

Unit I Topicwise references

Unit I Sets and Propositions

Topic	Resource
Sets, Combination of sets, Finite and Infinite sets, Un-countably infinite sets, Principle of inclusion and exclusion, multisets.	C. L. Liu and D. P. Mohapatra,*** Kenneth H. Rosen, J.P.Trembly and R.Manohar E. Goodaire and M. Parmenter,
Propositions, Conditional Propositions, Logical Connectivity, Propositional calculus, Universal and Existential Quantifiers	R. Johnsonbaugh Kenneth H. Rosen B. Kolman, R. Busby and S. Ross, J.P.Trembly and R.Manohar
Normal forms	C. L. Liu and D. P. Mohapatra J.P.Trembly and R.Manohar
Methods of proofs	R. Johnsonbaugh Kenneth H. Rosen
Mathematical Induction.	C. L. Liu and D. P. Mohapatra R. Johnsonbaugh Kenneth H. Rosen

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 GraphTheory”, 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 MathematicalStructures”, 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

7. J.P.Trembly and R.Manohar,”Discrete Mathematical structures withapplication to computer science”, McGraw-Hill, ISBN 0-07-100322-3

8. G.Shankar Rao,”Discrete Mathematical Structures”, new age International Publishers, ISBN 81-224-1424-9 

***Note: Reference in  red is important reference 

Discrete Structure syllabus

Unit	Topic and sub topics covered	Approx Lectures	Topic wise reference
I	Sets and Propositions: Introduction to subject,  Sets, Combination of sets, Finite and Infinite sets, Un-count-ably infinite sets	2	T1,T2 R1, R4,R5
	Principle of inclusion and exclusion, multi-sets.	1
	Propositions, Conditional Propositions, Logical Connectivity, Prepositional calculus,	1
	Universal and Existential Quantifiers, Normal forms, methods of proofs,	2
	Mathematical Induction, examples
	Class Tutorial: Problems on set theory, addition principle and mathematical induction	1
	Home Tutorial:  more examples on mathematical induction and normal form
II	Relations and Functions: Properties of Binary Relations, composition of matrices and relation, types of relation, Closure of relations,	1	T1,T2 R1,R3,R5
	Warshall’s algorithm, Equivalence relations and partitions	1
	Partial ordering relations and lattices, Chains and Anti chains.	1
	Functions, Composition of functions, Invertible functions, Pigeonhole Principle,	1
	Discrete numeric functions and Generating functions	1
	Job scheduling Problem, problem solving	1
	Recurrence Relation, Linear Recurrence Relations With constant Coefficients, Homogeneous Solutions, Total solution	1
	Class Tutorial: objective type problem and puzzles on relation and functions, game for conclusion: word search	1
	Home Tutorial:  supplementary problem on relation and functions.
III	Groups and Rings: Algebraic Systems, Groups, Semi Groups, Monoids, Subgroups	1	T2,T1 R7,R8
	Permutation Groups, Codes and Group codes,	1
	Isomorphism and Automorphisms, Homomorphism and Normal Subgroups,	1
	Ring, Integral Domain, Field, Ring Homomorphism	1
	Polynomial Rings and Cyclic Codes	1
	Problem solving	1
	Class Tutorial:  problem on algebraic system	1
	Home Tutorial: different problems on Groups, Semi-Group, Permutation group, Rings
IV	Graph Theory: Basic terminology, representation of a graph in computer memory, Matrix representation of graph, multi-graphs and weighted graphs,	1	T2,T1 R1,R3, R6, R8
	Sub-graphs, Isomorphic graphs, Complete, regular and bipartite graphs, operations on graph,	1
	paths and circuits, Hamiltonian and Euler paths and circuits,	1
	Shortest path in weighted graphs (Dijkstra’s algorithm), factors of a graph,	1
	Planar graph and Traveling salesman problem, Graph Coloring.	2
	Class Tutorial: real time problems on graph theory.	1
	Home Tutorial: supplementary problems on Dijkstra’s algorithm, Traveling salesman problem,
V	Trees: Basic terminology and characterization of trees, Prefix codes and optimal prefix codes	1	T1,T2 R1,R2,R6,R8
	binary search trees, Tree traversal	1
	Spanning trees, Fundamental Trees and cut sets	1
	Minimal Spanning trees, Kruskal’s algorithms for minimal spanning trees	1
	Prim’s algorithms for minimal spanning trees	1
	The Max flow-Min Cut Theorem (Transport network).	1
	Class Tutorial: objective type questions and puzels and real time problems on trees.	1
	Home Tutorial: supplementary problem on trees
VI	Permutations, Combinations and Discrete Probability rule of sum and product, Permutations, Combinations	1	T1,T2 R3, R4,R5,R8
	Algorithms for generation of Permutations and Combinations. Discrete Probability	1
	Conditional Probability and problems on Conditional Probability	1
	Bayes’ Theorem and problem on Bayes’ theorem	1
	Information and Mutual Information	1
	Problem solving	1
	Class tutorial: brainstorming type questions on Permutations and Combinations and Probability theory.	1
	Home tutorial: problems on Permutations and Combinations and Probability theory.