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
SECTION - B
Theory Course: CSE 2101
Sessional Course: Sessional Based on CSE 2101
Quiz Test - Marks
LAB Attendance
SECTION - C
Theory Course: CSE 2101
Class Test Marks - #3 - Question -
Class Test Marks - #4 - Question - Marks - CT3&4
Class Outline
1st Cycle to 3rd Cycle:
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.
4th Cycle to 6th Cycle:
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.
7th Cycle to 9th Cycle:
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.
10th Cycle to 12 Cycle:
Introduction to graphs: Graphs and their basic properties - degree, path, cycle, sub-graphs, isomorphism, Euclidian and Hamiltonian walks, graph coloring, planar graphs.
LAB Outline:
Handouts
1. Course Outline and basic defination - Lecture 00
2. Propositional Logic - Lecture_01
1.1 Propositional Logic
1.2 Applications
3. Propositional Logic - Lecture-02
1.3 Propositional Equivalences
4. Predicate Logic - Lecture-03
1.4 Predicates and Quantifiers
5. Predicate Logic - Lecture-04
1.5 Nested Quantifiers
6. Proofs - Lecture-05
1.6 Rules of Inference
7. Proofs - Lecture-06
1.7 Introduction to proof
8. Proofs - Lecture-07
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
24-35. Counting and Advance Counting
36. Graph - Lecture 35
10.1 Graphs and Graphs Model
37. Graph - Lecture 36
10.2 Graph Terminology and Special Types of Graph
38. Graph - Lecture 37
10.3 Representing Graph and Graph Isomorphism
39. Graph - Lecture 38
10.4 Connectivity
40. Graph - Lecture 39
Graph Traversing (out of syllabus)
41. Graph - Lecture 40
10.5 Euler and Hamilton Paths
42. Graph - Lecture 41
10.6 Shortest Path Problem (out of Syllabus)
43. Graph - Lecture 42
10.7 Planar Graphs
44. Graph - Lecture 43
10.8 Graph Coloring
45. Relations - Lecture 44
9.1 Relations and their properties
46. Relations - Lecture 45
9.3 Representing Relations
47. Relations - Lecture 46
9.4 Closures of Relations
48. Relations - Lecture 47
9.5 Equivalence Relations
49. Relations - Lecture 48
9.6 Partial Ordering