# Discrete Mathematics

Course ID
2CI02
Επίπεδο
Είδος
Compulsory
Εξάμηνο
2
Περίοδος
Spring Semeter
ECTS
5
Ώρες Θεωρίας
3
Ώρες Εργαστηρίου
-

#### Instructor

Vasileios Drakopoulos

#### Description

Introduction to logic and proofs; propositional logic, propositional equivalences, predicates and quantifiers. Set theory; set operations, finite and infinite sets. Relations and functions; properties of binary relations, equivalence relations, partial orderings, chains and antichains. Counting; the pigeonhole principle, permutations and combinations, generating functions. Computability; languages and grammars, finite-state machines, language recognition. Graphs; planar, weighted and directed graphs, trails, paths and circuits, Euler paths and circuits, Hamilton paths and circuits, the travelling salesman problem. Trees; spanning and binary trees, algorithms for trees and graphs. Algorithms; complexity of algorithms, properties of integer numbers, primes and greatest common divisors, mathematical induction and recursion, discrete arithmetic functions.

#### Course objectives

On completion of 2ΚΠ02, students will be able to explain and apply the basic methods of discrete (noncontinuous) mathematics in Computer Science and Informatics. They will be able to use these methods in subsequent courses in the design and analysis of algorithms, computability theory, software engineering and computer systems. In particular, students will be able to

• reason mathematically about basic data types and structures (such as numbers, sets, graphs, and trees) used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesise elementary proofs, especially proofs by induction.
• model and analyse computational processes using analytic and combinatorial methods.
• apply principles of discrete probability to calculate probabilities and expectations of simple random processes.
• work in small teams to accomplish all the objectives above.

#### Textbooks/Bibliography

• Susanna S. Epp, Discrete Mathematics with Applications, 4th ed., Brooks/Cole Cengage Learning, Boston, MA, 2011
• R. P. Grimaldi, Discrete and Combinatorial Mathematics: An applied introduction, 5th ed., Pearson Education Limited, Boston, MA, 2004
• F. Harary, Graph Theory, Perseus Books, Cambridge, MA, 1994
• S. V. Pemmaraju and S. S. Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge Univ. Press, NY, 2009
• K. H. Rosen, Discrete Mathematics and its Applications, 7th ed., McGraw-Hill, ΝΥ, 2012
• K. A. Ross and C. R. B. Wright, Discrete Mathematics, 5th ed., Prentice Hall, NJ, 2003
• R. Sedgewick and P. Flajolet, An introduction to the analysis of algorithms, 2nd ed., Pearson Education Inc., Westford, MA, 2013

#### Assessment method

Mandatory written exams at the end of the semester.