Discrete Structure (CS-302)
Objective-
This course introduces the applications of discrete mathematics in the field of computer science. It covers sets, logic, proving techniques, combinatorics, functions, relations, Graph theory and algebraic structures. These basic concepts of sets, logic functions and graph theory are applied to Boolean Algebra and logic networks while the advanced concepts of functions and algebraic structures are applied to finite state machines and coding theory.
rgpv bhopal, diploma, rgpv syllabus, rgpv time table, how to get transcript from rgpv, rgpvonline,rgpv question paper, rgpv online question paper, rgpv admit card, rgpv papers, rgpv scheme
B.Tech RGPV notes AICTE flexible curricula Bachelor of technology
Syllabus
UNIT 1:
Set Theory, Relation, Function, Theorem Proving Techniques : Set Theory: Definition of
sets, countable and uncountable sets, Venn Diagrams, proofs of some general identities
on sets Relation: Definition, types of relation, composition of relations, Pictorial
representation of relation, Equivalence relation, Partial ordering relation, Job-Scheduling
problem Function: Definition, type of functions, one to one, into and onto function,
inverse function, composition of functions, recursively defined functions, pigeonhole
principle. Theorem proving Techniques: Mathematical induction, Proof by contradiction.
UNIT 2:
Algebraic Structures: Definition, Properties, types: Semi Groups, Monoid, Groups,
Abelian group,
properties of groups, Subgroup, cyclic groups, Cosets, factor group, Permutation groups,
Normal
subgroup, Homomorphism and isomorphism of Groups, example and standard results,
Rings and Fields: definition and standard results
UNIT 3:
Propositional Logic: Proposition, First order logic, Basic logical operation, truth tables,
tautologies, Contradictions, Algebra of Proposition, logical implications, logical
equivalence, predicates, Normal Forms, Universal and existential quantifiers.
Introduction to finite state machine Finite state machines as models of physical system
equivalence machines, Finite state machines as language recognizers
UNIT 4:
Graph Theory: Introduction and basic terminology of graphs, Planer graphs, Multigraphs
and weighted
graphs, Isomorphic graphs, Paths, Cycles and connectivity, Shortest path in weighted
graph, Introduction to Eulerian paths and circuits, Hamiltonian paths and circuits, Graph
coloring, chromatic
number, Isomorphism and Homomorphism of graphs.
UNIT 5:
Posets, Hasse Diagram and Lattices: Introduction, ordered set, Hasse diagram of
partially, ordered set,
isomorphic ordered set, well ordered set, properties of Lattices, bounded and
complemented lattices.
Combinatorics: Introduction, Permutation and combination, Binomial Theorem,
Multimonial Coefficients Recurrence Relation and Generating Function: Introduction to
Recurrence Relation and Recursive algorithms , Linear recurrence relations with constant
coefficients, Homogeneous solutions, Particular solutions, Total solutions , Generating
functions , Solution by method of generating functions.
NOTES
- Unit 1
- Unit 2
- Unit 3
- Unit 4
- Unit 5
Outcome
After this completion student will be familiar with relational algebra,Functions and graph theory.
Books Recommended
1. C.L.Liu, “Elements of Discrete Mathematics” Tata Mc Graw-Hill Edition.
2. Trembley, J.P & Manohar; “Discrete Mathematical Structure with Application CS”,
McGraw Hill.
3. Kenneth H. Rosen, “Discrete Mathematics and its applications”, McGraw Hill.
4. Bisht, “Discrete Mathematics”,Oxford University Press
5. Biswal,”Discrete Mathematics & Graph Theory”, PHI
You May Also Like
- ES-301 - Energy & Environmental Engineering
- CS-303 - Data Structure
- CS-304 - Digital Systems
- CS-305 - Object Oriented Programming & Methodology
- CS-306 - Computer Workshop
- BT-107 - Evaluation of Internship-I completed at I year level
- BT-307 - 90 hrs Internship based on using various softwares –Internship -II