CS203

DISCRETE STRUCTURES

Objectives

  • To get familiar and understand the fundamental notions in discrete mathematics
  • To understand and demonstrate the basic concept of an algorithm and its application in combinatorial mathematics
  • To identify the basic properties of graphs and trees and model simple applications

 

Outcomes

  • Ability to distinguish between the notion of discrete and continuous mathematical structures
  • Ability to construct and interpret finite state diagrams and DFSA
  • Application of induction and other proof techniques towards problem solving

 

Unit – I

Set Theory And Logic - Sets, Functions, Relations, Equivalence Relation,Poset. Functions Logic: Propositional Logic, Truth Tables, Tautologies, Resolution Proof System, Predicate Logic.

 

Unit – II

Induction And Combinatorics - Peano's Axioms - Mathematical Induction - Pigeon-Hole Principle - Principle Of Inclusion And Exclusion - Review Of Permutations And Combinations - Distribution Problems - Derangements - Bijection Principle.

 

Unit – III

Algebraic Structures- Semi-Groups, Monoids, Groups, Subgroups And Their Properties -Cyclic Groups - Cosets - Permutation Groups - Lagrange's Theorem - Cayley's Theorem -Normal Subgroups - Homomorphism Of Groups - Quotient Groups –Introduction To Rings And Fields.

 

Unit – IV

Linear Algebra And Recurrence Relations- Linear Algebra: Vector Space, Basis, Dimension, Orthogonality.Recurrence Relations :Homogeneous And Inhomogeneous Recurrences And Their Solutions - Solving Recurrences Using Generating Functions.

 

Unit – V

Graph Theory- Definitions And Basic Results - Representation Of A Graph By A Matrix And Adjacency List - Trees - Cycles - Properties - Paths And Connectedness - Subgraphs - Graph Isomorphism - Operations On Graphs - Vertex And Edge Cuts - Vertex And Edge Connectivity.

 

TEXT BOOKS

  • C.L.Liu And D.P.Mohapatra, " Elements Of Discrete Mathematics: A Computer Oriented Approach", Mcgraw Hill, Third Edition, 2012.
  • Kenneth H. Rosen, "Discrete Mathematics And Its Applications" Mcgraw Hill, Seventh Edition, 2012 (Indian Adaptation By Kamala Krithivasan, Iit Madras).

REFERENCE:

  • R. Balakrishnan and K. Ranganathan, "A Text Book Of Graph Theory", Springer
  • Thomas Koshy, "Discrete Mathematics with Applications", Elsevier, 2009.
  • Gary Haggard, John Schlipf, and Sue Whitesides, “Discrete Mathematics for Computer Science”, Cengage Learning Publisher, 2005.
  • B. Bollobás, “Modern Graph Theory”, Springer, New York 1998