Aims and Objectives
The course aims to introduce the students to the basic ideas of discrete mathematics such as basic formal logic, counting techniques, graph theory and their applications in computer science. The main goal of the course is to provide students with a good understanding of the basic theory and some applications of discrete mathematics.
Key Contents
Elements of Set Theory: Introduction, Definition of Sets, Set operations, Powersets, Enumerable – non Enumerable Sets, Cardinality of a Set, Relations and Functions, Equivalence Relations, Partial Order Relations.
Propositional Logic: Propositions – Syntax, Connectives – Truth Tables, Tautology – Contradiction, Tautological Equivalence.
Mathematical Induction: Basic and Strong form of Mathematical Induction.
Combinatorial Analysis: Sum and Product Rules, Permutations, Combinations, Balls and Bins.
Generating Functions: Ordinary Generating Functions, Properties, Exponential Generating Functions, Application to Combinatorial Analysis.
Recursive Relations: Recursive Sequences and Relations, Solution of Linear Recursive Relations using Generating Functions.
Elements of Graph Theory: Definitions – Terminology, Directed and Undirected Graphs, Vertex Degree , Paths , Connected Graphs, Subgraphs, Special types of Graphs, Isomorphic Graphs, Euler and Hamilton Cycles, Graphs and Matrices, Shortest Path and Dijkstra’s Algorithm, Trees, Rooted Trees, Weighted Trees, Minimum Spanning Tree, Binary Trees.
Bibliograpy
EPP, SUSANNA S.: Discrete Mathematics with Applications, Wadsworth, 1990.
GRAHAM, R., KNUTH, D., PATASHNIK, O.: Concrete Mathematics, Addison Wesley, 1994.
GRIMALDI, R.: Discrete and Combinatorial Mathematics. An Applied Introduction, Addison Wesley, 1994.
HALL, M., Jr.: Combinatorial Theory, John Wiley & Sons, 1986.
HARARY, F.: Graph Theory, John Wiley & Sons, 1986.
KIROUSIS-BOURAS-SPIRAKIS: Discrete Mathematics, (in Greek), Gutenberg, 1999.
LIPSCHUTZ, S.: Set Theory, McGraw Hill, 1964.
LIU, C.: Introduction to Combinatorial Mathematics, McGraw Hill, 1968.
LIU, C.: Elements of Discrete Mathematics, McGraw Hill, 1986.
REINGOLD, M., NIERERGELT, J., DEO, N.: Combinatorial Algorithms Theory and Practice, Prentice Hall, 1977.
ROSS, K. A., WRIGTH, C. R. B. : Discrete Mathematics, Prentice Hall, 1992.
TOMESCU, I. And MELTER, R.: Problems in Combinatorial and Graph Theory, John Wiley & Sons, 1985.
VOUTSADAKIS-KIROUSIS-BOURAS-SPIRAKIS: “Discrete Mathematics. Problems and Solutions”, (in Greek) Guttenberg, 1994.
WITALA, S, A.: Discrete Mathematics. A Unified Approach, McGraw Hill, 1987.
