Course Syllabus

Course Description

To equip Computer Science students with the necessary mathematical background in enumeration, relations, logic and elements of graph theory. Sets and propositions: Finite and infinite sets, mathematical induction, propositions. Permutations, combinations and discrete probability. Relations and functions: binary, equivalence relations, partitions, partial ordering, functions. Graphs: weighted graphs, paths and circuits, shortest paths. Eulerian and Hamiltonian paths. Trees. Abstract algebra: groups, cosets, Lagrange's theorem, Boolean algebra.

Course Objectives

The objective of this course is to provide the fundamental principles of discrete mathematics and its applications. Students are introduced to basics of logic and proof methods, mathematical induction, counting techniques, recurrence relations and graph theory. Students see extensive practical applications especially in the topics of inference rules, counting and graph theory.

Key Concepts

1. Logic
2. Predicates and Quantifiers
3. Proofs and Reasoning
4. Set Theory
5. Combinatorics
6. Discrete Probability
7. Graph Theory

Learning Outcomes

1. To analyze and solve problems involving logic, boolean algebra, sets, relations, and functions.
2. To be able to construct inductive arguments. To solve various recursive relations.
3. To enumerate combinatorial objects using permutations, combinations and the counting principles.
4. Analyze and solve problems involving trees, spanning trees, rooted trees, binary trees, and tree traversal algorithms.
5. Explain and solve problems involving graphs, paths, circuits, graph coloring, directed graphs, spanning trees, minimal spanning trees, shortest path algorithms

Recommended Textbooks

“Discrete mathematics and its applications”, 7th edition, Kenneth Rosen