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

Discrete Structure (IT-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
  • 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
  • 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 Discrere Mathematics — C.L.Liu — TMH
  • Discrete mathematics (Schaum) — Lipschutz — TMH
  • Discrete Mathematical Structures — U.S Gupta — Pearson
  • Discrete Mathematics with Combinatorics and graph theory — S. Santha — Cengage Learning
  • Graph Theory With Applications — Dr.Sukhendu. Dey — Shroff Publishers
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