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

Logic
Predicates and Quantifiers
Proofs and Reasoning
Set Theory
Combinatorics
Discrete Probability
Graph Theory

14-Week Outline

Week	Topic
1	General introduction. Propositional logic. Equivalences.
2	Congruence. LCM(Least common multiplies) and gcd(great common divisors) Predicates and quantifiers
3	Set Theory. Functions. Inference rules.
4	Mathematical reasoning. Mathematical induction. Applications of mathematical induction.
5	Counting. Product and sum rules. Principle of inclusion-exclusion.
6	Pigeonhole principle.Permutations & combinations.Binomial coefficients
7	Combinations with repetition. Summary 1
8	Midterm
9	Probability, discrete probability. Examples .
10	Advanced counting techniques. Solving recurrence relations.
11	Graph connectivity. Graph isomorphism.
12	Euler and Hamilton paths, shortest path problems, the Dijkstra's algorithm
13	Trees. Their applications. Tree traversals. Polish notation.
14	(Overview). General review. Summary 1 and summary 2.

Learning Outcomes

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

Assessment Methods

Method	% Each	Quantity
Midterm Exam(s)	40	1
Final Exam	60	1

Recommended Textbooks

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

Back to Program

DISCRETE MATHEMATICS