Course No.: CSE 2101
Course Title: Discrete Mathematics
Prerequisite: CSE 1101 & CSE 1201
Contact hours/week: 3
Credits: 3.00
Course Description
Logic and Proof: Propositional Logic, Applications of Propositional Logic, Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Rules of Inference, Introduction to Proofs, Proof Methods and Strategy.
Set: Using Set Notation with Quantifiers, Truth Sets and Quantifiers, Generalized Unions and Intersections, Computer Representation of set.
Function: One-to-One and Onto Functions, Inverse Functions and Compositions of Functions, The Graphs of Functions, floor and ceiling function with their properties, Partial Functions.
Sequences and Summations: Sequences, recurrence relations and Summations.
Cardinality of Sets: Countable Sets, Uncountable Set, Uncomputable Functions.
Number Theory: Divisibility and Modular Arithmetic, Primes and Greatest Common Divisors, Solving Congruences, Applications of Congruences.
Induction and Recursion: Mathematical Induction, Strong Induction and Well-Ordering, Recursive Definitions and Structural Induction.
Counting: The Pigeonhole Principle, Binomial Coefficients and Identities, Generalized Permutations and Combinations, Generating Permutations and Combinations. Applications of Recurrence Relations, Generating Functions, Inclusion–Exclusion, Applications of Inclusion–Exclusion.
Relation: Property of relation, Representing Relations, Closures of Relations, Equivalence Relations, Partial Orderings.
Graphs: Graphs and Graph Models Graph Terminology and Special Types of Graphs, Representing Graphs, Graph Traversing, Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Planar Graphs, Graph Coloring.
Grading
Theory Courses
Class Participation and Attendance - 10 Marks
Class Test: 20 Marks (3 best out of 4 class tests may be taken for awarding grade)
Assignment/Project/Viva-voice/Presentation/Others: 10 Marks
Semester Exam: 60 Marks
Sessional Course
Class Participation and Attendance - 10 Marks
Quiz: 20 Marks (3 best out of 4 class tests may be taken for awarding grade)
Lab Performace, Lab report, Lab Final, Presentation/Viva and Other: 45 Marks
Board Viva: 25 Marks
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 - A
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 - Marks
Class Test Marks - #4 - Question - Marks
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