# 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