Discrete Mathematics

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.

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.

• Susanna S. Epp, Discrete Mathematics with Applications, 4^th ed., Brooks/Cole Cengage Learning, Boston, MA, 2011
• R. P. Grimaldi, Discrete and Combinatorial Mathematics: An applied introduction, 5^th 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, 7^th ed., McGraw-Hill, ΝΥ, 2012
• K. A. Ross and C. R. B. Wright, Discrete Mathematics, 5^th ed., Prentice Hall, NJ, 2003
• R. Sedgewick and P. Flajolet, An introduction to the analysis of algorithms, 2^nd ed., Pearson Education Inc., Westford, MA, 2013

 Mandatory written exams at the end of the semester.