##
__DISCRETE MATHEMATICAL __

##
__STRUCTURES __

####
Subject Code:18CS36 CIE Marks:40

SEE Marks:60

Number of Contact Hours/Week:3:0:0 Total Number of Contact Hours:40 Exam Hours:3 Hrs

CREDITS –3

####
__Course Learning Objectives: __This course (18CS36) will enable students to:

• Provide theoretical foundations of computer science to perceive other courses in the programme.• Illustrate applications of discrete structures: logic, relations, functions, set theory and counting.

• Describe different mathematical proof techniques,

• Illustrate the use of graph theory in computer science

###
__Module 1__

Fundamentals of Logic: Basic Connectives and Truth Tables, Logic Equivalence – The Laws of Logic, Logical Implication – Rules of Inference. Fundamentals of Logic contd.: The Use of Quantifiers, Quantifiers, Definitions and the Proofs of Theorems.Text book 1: Chapter2

__Module 2__

Properties of the Integers: The Well Ordering Principle – Mathematical Induction,

Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations – The Binomial Theorem, Combinations with Repetition.

Text book 1: Chapter4 – 4.1, Chapter1

__Module 3__

Relations and Functions: Cartesian Products and Relations, Functions – Plain and One-to-One, Onto Functions. The Pigeon-hole Principle, Function Composition and Inverse Functions.Relations: Properties of Relations, Computer Recognition – Zero-One Matrices and Directed Graphs, Partial Orders – Hasse Diagrams, Equivalence Relations and Partitions.

Text book 1: Chapter5, Chapter7 – 7.1 to 7.4

__Module 4__

The Principle of Inclusion and Exclusion: The Principle of Inclusion and Exclusion, Generalizations of the Principle, Derangements – Nothing is in its Right Place, Rook Polynomials.

Recurrence Relations: First Order Linear Recurrence Relation, The Second Order Linear Homogeneous Recurrence Relation with Constant Coefficients.

Text book 1: Chapter8 – 8.1 to 8.4, Chapter10 – 10.1, 10.2

__Module 5__

Introduction to Graph Theory: Definitions and Examples, Sub graphs, Complements, and Graph Isomorphism,

Trees: Definitions, Properties, and Examples, Routed Trees, Trees and Sorting, Weighted Trees and Prefix Codes

Text book 1: Chapter11 – 11.1 to 11.2 Chapter12 – 12.1 to 12.4

__Course Outcomes:__ The student will be able to :

• Use propositional and predicate logic in knowledge representation and truth verification.• Demonstrate the application of discrete structures in different fields of computer science.

• Solve problems using recurrence relations and generating functions.

• Application of different mathematical proofs techniques in proving theorems in the courses.

• Compare graphs, trees and their applications.

####
__Question Paper Pattern:__

• The question paper will have ten questions.• Each full Question consisting of 20 marks

• There will be 2 full questions (with a maximum of four sub questions) from each module.

• Each full question will have sub questions covering all the topics under a module.

• The students will have to answer 5 full questions, selecting one full question from each module.

__Question Bank:__

__Textbooks:__

1. Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, 5th Edition, Pearson Education. 2004.__Reference Books:__

1. Basavaraj S Anami and Venakanna S Madalli: Discrete Mathematics – A Concept based approach, Universities Press, 20162. Kenneth H. Rosen: Discrete Mathematics and its Applications, 6th Edition, McGraw Hill, 2007. 3. Jayant Ganguly: A Treatise on Discrete Mathematical Structures, Sanguine-Pearson, 2010.

4. D.S. Malik and M.K. Sen: Discrete Mathematical Structures: Theory and Applications, Thomson, 2004.

5. Thomas Koshy: Discrete Mathematics with Applications, Elsevier, 2005, Reprint 2008.