Skip to content
CampusPrep
CS-302 · Discrete Structure/Official Syllabus

Discrete Structure (CS-302) - Official Syllabus

1
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
2
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
3
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
4
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
5
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

Reference Books

  • Elements of Discrete Mathematics — C.L.Liu — Tata Mc Graw-Hill Edition
  • Discrete Mathematical Structure with Application CS — Trembley, J.P, Manohar — McGraw Hill
  • Discrete Mathematics and its applications — Kenneth H. Rosen — McGraw Hill
  • Discrete Mathematics — Bisht — Oxford University Press
  • Discrete Mathematics & Graph Theory — Biswal — PHI
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in