Discrete Mathematics | DIT, BIT YR1 Sem 1

TEACHING PORTFOLIO

Course Title: Discrete Mathematics
Course Code: BIT 1103 (or assign appropriately)
Credit Units: 3 CU
Contact Hours: 45 Hours
Level: Year I – Semester I
Lecturer: Muwanguzi Benard
Contact: +256 708 646 603
Email: info@ictconnect.org | muwanguzibenard2017@gmail.com

Course Description

This course introduces learners to the foundational concepts of Discrete Mathematics, which is the mathematical language of computer science and information systems. It equips students with knowledge and skills in logic, sets, functions, relations, combinatorics, graph theory, group theory, and probability.

The course emphasizes problem-solving and application of mathematical structures that are discrete (non-continuous) in nature — forming the theoretical foundation for subjects such as algorithms, data structures, database design, and artificial intelligence.

Course Objectives

The course aims to:
a) Develop a solid understanding of discrete mathematical structures and their applications in computing.
b) Introduce logical reasoning and mathematical proof techniques used in software and system design.
c) Apply counting, combinatorics, and probability to solve computational and real-life problems.
d) Explore graphs, trees, and relations for modeling real-world networks and data structures.
e) Enhance analytical and critical thinking through mathematical modeling and reasoning.

Learning Outcomes

By the end of this course, students should be able to:

1. Apply principles of counting and probability in solving mathematical and computing problems.

2. Analyze and construct logical propositions and Boolean expressions.

3. Demonstrate understanding of sets, relations, and functions and their applications.

4. Model systems using graph and tree representations.

5. Explain and apply concepts of group theory in encryption, symmetry, and computing systems.

6. Solve problems using mathematical induction and recurrence relations.

Detailed Course Outline

Unit 1: Counting Theory (6 Hrs)

• Basics of counting

• The Rule of Sum and Rule of Product

• Permutations and combinations

• Factorials and multinomial coefficients

• The Pigeonhole Principle

• Applications in computing (e.g., password generation, algorithm complexity)

Unit 2: Group Theory (5 Hrs)

• Definition and examples of groups

• Subgroups, identity elements, and inverses

• Cyclic groups and order of elements

• Homomorphisms and isomorphisms

• Applications in cryptography and coding theory

Unit 3: Sets, Relations, and Functions (6 Hrs)

• Definition of sets and set operations

• Venn diagrams

• Relations and their properties (reflexive, symmetric, transitive)

• Equivalence relations and partitions

• Functions: one-to-one, onto, bijective

• Composition of functions and inverse functions

• Applications in database design and logic

Unit 4: Graph Theory (6 Hrs)

• Basic terminology: vertices, edges, degree, paths, cycles

• Directed and undirected graphs

• Connectedness and components

• Eulerian and Hamiltonian paths

• Adjacency matrix representation

• Applications: network routing, social networks, circuit design

Unit 5: Mathematical Logic and Boolean Algebra (6 Hrs)

• Propositional logic and truth tables

• Logical connectives and equivalence

• Predicate logic and quantifiers

• Rules of inference and proof techniques

• Boolean algebra: laws and simplifications

• Karnaugh maps (K-maps) and circuit simplification

• Applications in computer hardware and programming

Unit 6: Mathematical Induction and Recurrence Relations (5 Hrs)

• Principle of mathematical induction

• Strong induction

• Recurrence relations and their solutions

• Examples from algorithm analysis (e.g., Fibonacci sequence, divide and conquer)

• Applications in programming and sequence generation

Unit 7: Probability (6 Hrs)

• Basic probability concepts and definitions

• Sample spaces and events

• Conditional probability and independence

• Bayes’ theorem

• Expected value and variance

• Applications in risk analysis, AI, and data science

Unit 8: Trees and Data Presentation (5 Hrs)

• Definition and properties of trees

• Rooted trees, binary trees, and m-ary trees

• Tree traversal (preorder, inorder, postorder)

• Spanning trees and minimal spanning trees

• Data representation using trees (decision trees, parse trees)

• Applications in data structures and file systems

Teaching Methodology

• Lectures and interactive tutorials

• Problem-solving exercises and assignments

• Group discussions and presentations

• Real-life computational examples and simulations

• Practical demonstrations using software tools (e.g., MATLAB, Graphviz, Python for combinatorics)

Assessment Methods

References

1. Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill Education.

2. Tremblay, J. P., & Manohar, R. (2017). Discrete Mathematical Structures with Applications to Computer Science. McGraw-Hill.

3. Epp, S. S. (2018). Discrete Mathematics with Applications. Cengage Learning.

4. Grimaldi, R. P. (2017). Discrete and Combinatorial Mathematics: An Applied Introduction. Pearson.

5. Liu, C. L. (2012). Elements of Discrete Mathematics. McGraw-Hill.

Grade Scale