Course information

DISCRETE MATHEMATICS

Module Code: GENDM601

Credit Hours: 8

 Contact Hours: 48 Hours

Prerequisites: NA

1. Module Overview

Discrete Mathematics is a foundational course that provides the mathematical backbone for computer science, information technology, and modern engineering. Unlike continuous mathematics (calculus), this module focuses on distinct, separable, and countable mathematical structures. It equips students with the essential tools for rigorous logical reasoning, algorithm design, data structure analysis, and secure communication. By exploring logic, combinatorics, number theory, graph theory, and automata, students will develop the analytical mindset required to solve complex, non-continuous computational problems.

2. Module Objectives (Learning Outcomes)

Upon successful completion of this module, students will be able to:

1.       Logic and Proofs: Formulate, parse, and evaluate complex logical statements using propositional and predicate logic, and construct rigorous mathematical proofs using various techniques.
2.      Counting and Probability: Apply fundamental counting principles, permutations, and combinations to solve combinatorial problems and calculate discrete probabilities.
3.      Number Theory and Cryptography: Utilize concepts of divisibility, modular arithmetic, and prime numbers to understand and implement foundational cryptographic algorithms.
4.       Graph Theory and Automata: Model real-world problems using graph theory and understanding the basic theoretical limits of computation through finite automata machines.
5.       Sequences and Series: Analyze discrete sequences, solve linear recurrence relations, and evaluate finite series relevant to algorithmic complexity.

3. Module Content (Learning Units)

Unit 1: Mathematical Logic and Proofs

Focus: Developing rigorous thinking and argumentation skills.

1)      Propositional Logic: Syntax, semantics, logical connectives, truth tables, tautologies, and contradictions.

2)      Predicate Logic: Quantifiers (universal and existential), nested quantifiers, and logical equivalences.

3)      Rules of Inference: Valid arguments, fallacies, and methods of proof.

4)      Proof Techniques: Direct proof, proof by contraposition, proof by contradiction, and mathematical induction (weak and strong).

5)      Applications: Logical circuits and Boolean algebra basics.

Unit 2: Counting Techniques and Discrete Probability

Focus: Enumerating possibilities and understanding likelihood in discrete spaces.

1)      Basic Counting: The sum and product rules.

2)      Advanced Counting: Permutations, combinations, combinations with repetition, and the Binomial Theorem.

3)      Principles: The Pigeonhole Principle and the Inclusion-Exclusion Principle.

4)      Discrete Probability: Sample spaces, events, axioms of probability.

5)      Conditional Probability: Independence, Bayes’ Theorem, and expected value in discrete settings.

Unit 3: Number Theory and Cryptography

Focus: The mathematics of integers and its application to data security.

1)      Fundamentals: Divisibility, division algorithm, prime numbers, and prime factorization.

2)      Arithmetic: Greatest Common Divisor (GCD), Least Common Multiple (LCM), and the Euclidean Algorithm.

3)      Modular Arithmetic: Congruences, modular exponentiation, and solving linear congruences.

4)      Cryptography Applications: Introduction to classical ciphers (Caesar, Affine) and modern public-key cryptography (RSA Algorithm).

Unit 4: Graph Theory and Automaton Machine

Focus: Modeling networks, relationships, and abstract computing machines.

1)      Graph Basics: Vertices, edges, directed/undirected graphs, weighted graphs, degree of vertices, and handshaking theorem.

2)      Graph Traversal & Paths: Euler paths and circuits, Hamiltonian paths and circuits, Dijkstra’s shortest path algorithm.

3)      Trees: Properties of trees, rooted trees, spanning trees, and minimum spanning trees (Kruskal’s/Prim’s algorithm).

4)      Automaton Theory: Introduction to formal languages, Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), and state transition diagrams.

Unit 5: Sequences and Series

Focus: Understanding ordered lists and summations, crucial for algorithm analysis.

1)     Sequences: Definition, arithmetic and geometric progressions, and limit concepts (basic).

2)     Summations: Sigma notation, properties of summations, and special summation formulas.

3)     Recurrence Relations: Defining sequences recursively, solving linear homogeneous recurrence relations with constant coefficients.

4)     Applications: Generating functions (introduction) and analyzing the time complexity of recursive algorithms (e.g., Tower of Hanoi, Fibonacci, Merge Sort).

 

4. Teaching and Learning Methodology

1)      Interactive Lectures: Introduction of core theoretical concepts and theorems.

2)      Tutorial Sessions: Problem-solving workshops where students work through guided exercises.

3)      Collaborative Learning: Group assignments focusing on real-world applications (e.g., designing a simple DFA or modeling a network as a graph).

4)      Software Tools (Optional but recommended): Utilization of tools like Python (for basic cryptography/counting), JFLAP (for automata visualization), or GeoGebra.

5. Assessment Strategy

Assessment Type	Weight	Description
Continuous Assessment	30%	Quizzes, homework, and short in-class tests focusing on specific units (e.g., logic proofs, counting problems).
Midterm Examination	20%	Covers Units 1 and 2. Tests foundational logic and combinatorial skills.
Project / Assignment	10%	A applied project (e.g., implementing the RSA cipher, or modeling a transport network using graph theory).
Final Examination	40%	Comprehensive exam covering all 5 units, emphasizing conceptual understanding and problem-solving under timed conditions.

6. Recommended Textbooks and Resources

1.       Primary Textbook: Discrete Mathematics and Its Applications by Kenneth H. Rosen (McGraw-Hill).
2.       Alternative Textbook: Discrete Mathematics with Applications by Susanna S. Epp (Cengage Learning).
3.       Supplementary Resource: Book of Proof by Richard Hammack (Virginia Commonwealth University).
4.       Digital Tool: JFLAP (Java Formal Languages and Automata Package) - for Unit 4 visual learning.