Course No.: CSE 2101
Course Title: Discrete Mathematics
Prerequisite: CSE 1101 & CSE 1201
Contact hours/week: 3
Credits: 3.00
Course Description
Set: Operations on sets, Algebraic properties of set, Computer Representation of set, Cantor's diagonal argument and the power set theorem, Schroeder-Bernstein theorem.
Relation: Property of relation, binary relations, partial ordering relations, equivalence relations.
Function: type of functions, growth of function.
Propositional logic: Syntax, semantics, valid, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments, predicate and quantifier, universal and existential quantification; modus ponens and modus tollens.
Proof techniques: The structure of formal proofs, direct proofs, proof by counter, proof by contraposition, proof by contradiction, mathematical induction, proof of necessity and sufficiency.
Number Theory: Theorem of Arithmetic, Modular Arithmetic, GCD, LCM, Prime Number, Congruence, Application of Congruence, Application of Number Theory, Chinese Remainder theory.
Introduction to counting: Basic counting techniques - inclusion and exclusion, pigeon-hole principle, permutation, combination, sequence and summations, introduction to recurrence relation and generating function.
Introduction to graphs: Graphs and their basic properties - degree, path, cycle, sub-graphs, isomorphism, Euclidian and Hamiltonian walks, graph coloring, planar graphs.
Grading
Quizzes/Class Test: 20 Marks* (3 best out of 4 quizzes/class tests may be taken for awarding grade)
Homework’s/Attendance: 8 Marks*
Semester Exam: 72 Marks
* - We reserve the right to change the above grading scheme.
Homework's
A new homework is released and is then due after 9 days. No grade will be given to homework submitted afterwards. Homework solutions should be written and submitted individually, but discussions among students are encouraged.
Referred Books
Kenneth H. Rosen - Discrete Mathematics and its Applications, Tata McGraw-Hill.
Mathematics for Computer Science by Eric Lehman, F. Thomson Leighton, Albert R. Meyer.
Rnald L. Graham, Donald E. Knuth and Oren Patashnik – Concrete Mathematics.
S. G. Telang – Number Theory
Other
Notice
CSE 2101
Sessional Based on CSE 2101
Class Outline
Lab Outline
Extra*
Handouts
1. Course Outline and basic defination - Lecture 00.pdf
2. Propositional Logic - Lecture-01.pdf
1.1 Propositional Logic
1.2 Applications
3. Propositional Logic - Lecture-02.pdf
1.3 Propositional Equivalences
4. Predicate Logic - Lecture-03.pdf
1.4 Predicates and Quantifiers
5. Predicate Logic - Lecture-04.pdf
1.5 Nested Quantifiers
6. Proofs - Lecture-05.pdf
1.6 Rules of Inference
7. Proofs - Lecture-06.pdf
1.7 Introduction to proof
8. Proofs - Lecture-07.pdf
1.8 Proof Methods and Strategy
9. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices - Lecture-08
2.1 Sets
10. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices - Lecture-09
2.2 Sets Operations
11. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices - Lecture -10
2.3 Function
12. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices - Lecture -11
2.4 Sequences and Summations
13. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices - Lecture -12
2.5 Cardinality of Sets
14. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices - Lecture -13
2.6 Matrices
15. Algorithms - Lecture - 14
3.1 Algorithms
16. Algorithms - Lecture - 15
3.2 The Growth of Functions
17. Algorithms - Lecture - 16
3.3 Complexity of Algorithms
18. Number Theory and Cryptography - Lecture 17
4.1 Divisibility and Modular Arithmetic
19. Number Theory and Cryptography - Lecture 18
4.2 Integer Representations and Algorithms
20. Number Theory and Cryptography - Lecture 19
4.3 Primes and Greatest Common Divisors
21. Number Theory and Cryptography - Lecture 20
4.4 Solving Congruence's
22. Number Theory and Cryptography -Lecture 21
4.5 Applications of Congruences
23. Number Theory and Cryptography - Lecture 22
4.6 Cryptography