Discrete Mathematics

Learning Outcomes

The course is a basic introduction to the concepts of discrete mathematical objects and the relationships between them. The course material aims to introduce students to the basic concepts of mathematical structures that are fundamentally distinct. The objects studied in discrete mathematics – such as integers, graphs, propositions of logic, recursive relations – form the basis for the study and description of objects and problems in computer science, specifically computational algorithms, programming languages, cryptography, in automated theorem proving and software development.

Upon successful completion of the course, the student will be able to:

• Understand the basic concepts of discrete mathematics.
• Know the methods and techniques of Logic, Proof, Calculation, Relations, and Graphs.
• Apply these methods to solve algorithmic problems.
• Develop mathematical reasoning.
• Draw mathematical conclusions.

Indicative Module Content

• Introduction to set theory, set operations, finite and infinite sets.
• Introduction to logic and proofs, mathematical induction, propositional calculus.
• Relationships and functions, properties of binary relations, equivalence relations, order and partial order.
• Typical languages, grammars, finite state machines, language recognition.
• Introduction to graph theory, levels, weighted and directed graphs, paths, circuits.
• Euler paths and circuits, Hamilton paths and circuits, the problem of the traveling salesman.
• Trees, overlapping trees, binary trees, tree and graph algorithms.
• Boolean algebra, circuit minimization.