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.