Discrete Mathematics

Course Title: Discrete Mathematics

Course No: BDS254

Nature of the Course: THEORY

Semester: 4

Full Marks: 45 + 30

Pass Marks: 18 + 12

Credit Hours: 3

Course Description

This course deals with mathematical structures that are discrete in nature rather than continuous. It covers the key combinatorial topics of combinatorial enumeration and is useful and accessible for applied fields. It has many real-world applications that can be explained using only a few simple definitions. Elementary number theory, Modular arithmetic, Induction, Counting techniques, Recurrence relations are key topics treated in a way that will facilitate the students in being able to think logically and mathematically, and finally making them capable of applying the techniques of discrete mathematics in solving problems.

Course Objectives

After successful completion of this course the student will be able to • Use Modular arithmetic • Work with prime numbers and the fundamental theorem of arithmetic, • Solve systems of linear congruences and counting problems. • Apply the principles of mathematical induction in proofs. • Model with recurrence relations

Course Contents

1. Logic and Proofs

9 hrs

1.1. Propositional logic

1.2. Application of propositional logic

1.3. Propositional equivalences

1.4. Predicates and quantifiers

1.5. Nested quantifiers

1.6. Rules of inference

1.7. Introduction to proofs

1.8. Proof methods and strategy

2. Number Theory

9 hrs

2.1. Divisibility and modular arithmetic

2.2. Integer representations and algorithms

2.3. Primes and greatest common divisors

2.4. Solving congruences

2.5. Applications of congruences

2.6. Cryptography

3. Induction and Recursion

9 hrs

3.1. Mathematical induction

3.2. Strong induction and well-ordering

3.3. Recursive definitions and structural induction

3.4. Recursive algorithms

4. Counting Techniques

13 hrs

4.1. Basics of counting

4.2. Pigeonhole principle

4.3. Permutations and combinations

4.4. Binomial coefficients and identities

4.5. Generalized permutations and combinations

4.6. Recurrence relations and its applications

4.7. Solving linear homogeneous recurrence relations with constant coefficients

4.8. Linear non homogeneous recurrence relations with constant coefficients

4.9. Generating functions

4.10. Inclusion-exclusion

5. Relations

8 hrs

5.1. Relations and their properties

5.2. n-ary relations and their applications

5.3. Representing relations

5.4. Closures of relations

5.5. Equivalence relations

5.6. Partial orderings

Reference Books

1.Kenneth H. Rosen, Discrete Mathematics and its Applications, 8th edition, McGraw Hill, New York
2.Susanna S. Epp (2011). Discrete Mathematics with Applications, Brooks/Cole
3.Kevin Ferland (2009). Discrete Mathematics an Introduction to Proofs and Combinatorics, Houghton Mifflin Company
4.Peter J. Cameron (1995). Combinatorics: Topics, Techniques, Algorithms, CUP
5.Dieter Jungnickel (2005). Graphs, Networks, and Algorithms, Springer
6.Ian Anderson (2001). A First Course in Discrete Mathematics, Springer
7.Alan Camina and Barry Lewis (2011). An Introduction to Enumeration, Springer

Notes:

This syllabus follows the official Bachelor in Data Science curriculum of Tribhuvan University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative.

Discrete Structure

Discrete Structure

Select University

Select Program

TabFlux . Discrete Mathematics . TU . BDS

Discrete Mathematics

Course Description

Course Objectives

Course Contents

Reference Books

Notes: