With effect from Academic Year 2015-2016

CS 202

 

             DISCRETE STRUCTURES

 

Instruction                                                                               4 Periods per week

Duration of University Examination                                      3 Hours

University Examination                                                          75 Marks

Sessional                                                                                 25 Marks

 

Course objectives:

• To introduce fundamentals of logic to evaluate elementary mathematical arguments and identify fallacious reasoning.
• Use of mathematical and logical notation to define and formally reason about mathematical concepts such as sets, relations, functions, integers and algebraic structures
• Use of mathematical and logical notation to define and formally reason about discrete structures like trees, graphs and partial orders.
• To introduce generating functions and recurrence relations to find asymptotic growth rates of different functions.

UNIT-I

Fundamentals of Logic: Basic Connectives and Truth Tables, Logical Equivalence, Logical Implication, Use of Quantifiers, Definitions and the Proof of Theorems.

 

Set Theory: Set and Subsets, Set Operations, and the Laws of Set theory, Counting and Venn Diagrams.

 

Properties of the Integers: The well – ordering principle, Recursive definitions, the division algorithms, fundamental theorem of arithmetic.

 

UNIT-II

Relations and Functions: Cartesian Product, Functions onto Functions, Special Functions, Pigeonhole Principle, Composition and Inverse Functions, Computational Complexity.

 

Relations: Partial Orders, Equivalence Relations and Partitions.

 

Principle of Inclusion and Exclusion: Principles of Inclusion and Exclusion, Generalization of Principle, Derangements, Rock Polynomials, Arrangements with Forbidden Positions.

 

UNIT-III

Generating Functions: Introductory examples, definition and example Partitions of Integers, exponential generating function, summation operator. Recurrence Relations: First – order linear recurrence relation, second – order linear homogenous recurrence relation with constant coefficients, Non homogenous recurrence relation, divide and conquer algorithms.

                                                              

UNIT-IV

Algebraic Structures: Algebraic System – General Properties, semi groups, Monoids, homomorphism, Groups, Residue arithmetic, group codes and their applications.

 

UNIT-V

Graph Theory: Definitions and examples, subgraphs, complements and graph Isomorpshim, Vertex degree, Planar graphs, Hamiltonian paths and Cycles, Graph Coloring.

 

Trees: Definitions, properties and Examples, Rooted Trees, Spanning Trees and Minimum Spanning Trees.

 

Suggested Reading:

 

1.Ralph P.Grimaldi, Discrete and Combinatorial Mathematics, 4th edition, 2003, Pearson

   Education.

 

2.J.P.Tremblay, R.Manohar, Discrete Mathematical Structure with Applications to Computer

   Science, McGraw Hill, 1987.

 

3.Joe L.Mott, A.Kandel, T.P.Baker, Discrete Mathematics for Computer Scientists &

   Mathematicians, Prentice Hall N.J., 1986.

 

4.Thomas Koshy, Discrete Mathematics with Applications, Elsevier Inc.2004.