Course code

Course Name

L-T-P Credits

Year of Introduction

CS201

DISCRETE COMPUTATIONAL STRUCTURES

3-1-0-4

2016

Pre-requisite: NIL

Course Objectives

1.        To introduce mathematical notations and concepts in discrete mathematics that is essential for computing.

2.        To train on mathematical reasoning and proof strategies.

3.        To cultivate analytical thinking and creative problem solving skills.

Syllabus

Review of Set theory, Countable and uncountable Sets, Review of Permutations and combinations, Pigeon Hole Principle, Recurrence Relations and Solutions, Algebraic systems (semigroups, monoids, groups, rings, fields), Posets and Lattices, Prepositional and Predicate Calculus, Proof Techniques.

Expected Outcome:

Students will be able to

1.        identify and apply operations on discrete structures such as sets, relations and functions in different areas of computing.

2.        verify the validity of an argument using propositional and predicate logic.

3.        construct proofs using direct proof, proof by contraposition, proof by contradiction and proof by cases, and by mathematical induction.

4.        solve problems using algebraic structures.

5.        solve problems using counting techniques and combinatorics.

6.        apply recurrence relations to solve problems in different domains.

Text Books

1.  Trembly J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub.Co.Ltd, New Delhi, 2003.

2.  Ralph.    P.    Grimaldi,   “Discrete    and    Combinatorial   Mathematics:   An          Applied Introduction”, 4/e, Pearson Education Asia, Delhi, 2002.

References:

1.        Liu C. L., “Elements of Discrete Mathematics”, 2/e, McGraw–Hill Int. editions, 1988.

2.        Bernard Kolman, Robert C. Busby, Sharan Cutler Ross, “Discrete Mathematical Structures”, Pearson Education Pvt Ltd., New Delhi, 2003

3.        Kenneth H.Rosen, “Discrete Mathematics and its Applications”, 5/e, Tata McGraw – Hill Pub. Co. Ltd., New Delhi, 2003.

4.        Richard Johnsonbaugh, “Discrete Mathematics”, 5/e, Pearson Education Asia, New Delhi, 2002.

5.        Joe L Mott, Abraham Kandel, Theodore P Baker, “Discrete Mathematics for Computer Scientists and Mathematicians”, 2/e, Prentice-Hall India, 2009.

Course Plan

Module

Contents

Hou rs (54)

End Sem Exam Marks

Review of elementary set theory :

Algebra of sets – Ordered pairs and Cartesian products –

3

Countable and Uncountable sets

Relations :-

Relations on sets –Types of relations and their properties –

6

I

Relational  matrix  and  the  graph  of  a  relation  –  Partitions –

Equivalence   relations   –   Partial   ordering-   Posets   –  Hasse

15 %

diagrams – Meet and Join – Infimum and Supremum

Functions :-

Injective,  Surjective  and  Bijective  functions  –    Inverse of a

1

function- Composition

Review of Permutations and combinations, Principle of

3

inclusion exclusion, Pigeon Hole Principle,

Recurrence Relations:

Introduction-    Linear    recurrence    relations   with    constant

4

II

coefficients– Homogeneous solutions – Particular solutions –

Total solutions

15 %

Algebraic systems:-

Semigroups and monoids – Homomorphism, Subsemigroups

2

and submonoids

FIRST INTERNAL EXAM

III

Algebraic systems (contd…):-

Groups, definition and elementary properties, subgroups, Homomorphism and Isomorphism, Generators – Cyclic Groups, Cosets and Lagrange’s Theorem

Algebraic systems with two binary operations- rings, fields-sub rings, ring homomorphism

6

2

15 %

IV

Lattices and Boolean algebra :-

Lattices –Sublattices – Complete lattices – Bounded Lattices – Complemented Lattices – Distributive Lattices – Lattice Homomorphisms.

Boolean algebra – sub algebra, direct product and homomorphisms

7

3

15 %

SECOND  INTERNAL EXAM

Propositional Logic:-

V

Propositions – Logical connectives – Truth tables

2

20 %

Tautologies and contradictions – Contra positive – Logical

3

equivalences and implications

Rules of inference: Validity of arguments.

3

VI

Predicate Logic:-

Predicates – Variables – Free and bound variables – Universal and Existential Quantifiers – Universe of discourse.

Logical equivalences and implications for quantified statements

–   Theory of inference : Validity of arguments.

Proof techniques:

Mathematical induction and its variants – Proof by Contradiction

–   Proof by Counter Example – Proof by Contra positive.

3

3

3

20 %

END SEMESTER EXAM