BIT 111 Discrete Mathematics

Programme Bachelor of Computer Science

Course name: Discrete Mathematics
Course code: BIT 111
Level of Year One Semester One
course:
Credit units: 3
Brief Course Is a branch of mathematics that deals with mathematical
Description structures that are distinct, separated in contrast with
calculus that deals with continuous change. It provides
mathematical basis for understanding of computers and
modern computation. Discrete mathematics provides
important tools for improving reasoning and problem-
solving capabilities. This course covers elementary
discrete mathematics for computer science and
engineering. The topics of study include: sets, relations,
functions, logic and proofs, graphs theory, trees, algebra,
enumeration techniques, Arithmetic algorithms,
probability, induction and recursion.
Objectives (i) To introduce students to concepts of elementary
logic and methods of proof.
(ii) To introduce concepts of sets, relations and
functions.
(iii) To teach students graph theory and models
and trees and their application in solving problems
in real life situations.
(iv) To introduce students to mathematical
concepts of cryptography and algorithms
(v) To teach concepts of number theory and how they
apply to problems involving arithmetic operations.
Learning By the end of the course, students should be able to:
Outcomes: (i) Ability to apply mathematical logic and proofs to
solve problems.
(ii) Apply sets. relations, functions and discrete
structures in problem solving.
(iii) Evaluate some elementary algorithms: searching
algorithms, sorting, greedy algorithms, and their
complexity.
(iv) Enumerate objects which begins with the basic
techniques of counting.
(v) Able to model and solve real world problems
using graph theory and trees.
(vi) Apply number theory in classical and modern
cryptography.

Contents Week 1: Sets ( 3 hours)

The Language of Sets: The Concepts of a Set, Operations
with Sets, Venn diagrams, Computer Operations with
Sets, The Cardinality of a Set, Recursively Defined Sets.

Week 2: Relations ( 3 hours)

Boolean Matrices, Relations and Digraphs, Computer
Representations of Relations, Properties of Relations,
Operations on Relations, Transitive Closure, Equivalence
Relations, Partial and Total Ordering.

Week 3: Functions (3 hours)

The concept of Functions, Special Functions, Properties of
Functions, The Pigeonhole principle, Composite Functions,
Sequences and the Summation Notation.
Week 4-5: Graphs (6 hours)
Computer Representation of Graphs, Isomorphic Graphs,
Paths, Cycles, and Circuits, Eulerian and Hamiltonial
Graphs, Planar Graphs, Graph Coloring, Digraphs, DAGs,
Weighted Digraphs, DFS and BFS Algorithms, Cut vertices
and Edges, Covering, Matching.

Week 6: CAT 1 WEEK

Week 7: Trees
(3 hours)
Introduction to trees: Application of trees, tree traversal;
Spanning trees, Minimum spanning trees; definitions,
types (rooted, ordered, binary), paths, applications;
Kruskal’s and Prim’s Algorithm.

Week 8-9: Induction and Recurssion (6

hours)
The Division Algorithm, Divisibility Properties, Non
decimal Bases, Mathematical Induction, Algorithm
Correctness, The Growth Functions, Complexity of
Algorithms. Recursion: Recursively Defined Functions,
Solving Recurrence Relations, Generating Functions,
Recursive Algorithms, Correctness of Recursive
Algorithms, Complexities of Recursive Algorithms.

Week 10-11: Propositional Logic and Proofs.

(6hours)
Logical equivalence and implication, Predicates and quantifiers,
 Equivalence of statements, Logical reasoning, Truth tables, DE
Morgan’s Laws.

Week 12: CAT 2

Week 13-14: Number theory and Cryptography

(6 hours)
Counting: Basic rules, Pigeonhole principles, Permutations and
combinations, Binomial coefficients and Pascal triangle Number Theory
and Cryptography.
Week 15 &16
Examinations
Mode of This will be done through: Lecturing, Tutorials and Group
delivery: Assignments
Mode of Coursework = 40%
assessment Examination = 60%
Total = 100%
References 1. Discrete Mathematics and its Applications, Kenneth
H. Rosen, 8th Edition, McGraw Hill education.
2. Dicrete Mathematics 4th edition by Dossey, Otto,
Spence and Vanden Eynden
3. Lipschutz, S., and Lipson, M., 2007, Schaum’s
Outline of Theory and Problems of Discrete
Mathematics, McGraw Hill [ISBN 9780071511018]
4. Moller, F, and Struth, G, 2013, Modelling Computing
Systems: Mathematics for Computer Science,
Springer [ISBN 9781848003224]
5. Discrete Mathematics for Teachers (2010) by Ed.
Wheeler and Jim brawner