Description
The purpose of the the course “Discrete Mathematics” is to provide the students with the essential knowledge, skills and techniques of discrete mathematics, which play a crucial role in the analysis of a wide range of problems occurring in the field of computer science.
Content
The outline of the course is as follows:
Elementary Set Theory: Introduction, Definition of Sets, Set Operations, Powersets, Countable – Uncountable sets, Cardinality, Pigeonhole principle.
Relations and Functions: Binary relations, Equivalence Relations, Partial Orders, Functions.
Propositional Logic: Variables – Formulas – Syntax, Truth Tables, Logical Operators Properties, Tautologies – Contradictions, Logical Equivalence.
Induction: Mathematical Induction and Applications, Strong form of mathematical induction.
Combinatorics: Sum – Product Rules, Permutations – Combinations, With or without repetitions, Balls into Bins
Generating Functions: Ordinary Generating Functions, Properties, Exponential Generating Functions, Applications in Combinatorial Problems.
Recursive Relations: Recursive Sequences, Linear recursive equations, Homogeneous – non-homogeneous relations, Solution of linear recursive equations using generating functions
Elements of Graph Theory Basic definitions, Directed and undirected graphs, Vertex Degrees, Paths, Connectivity, Subgraphs, Chromatic Number, Euler Cycles, Hamilton Cycles, Shortest path Problem – Dijkstra’s Algorithm. Trees, Spanning trees, BFS, DFS, Minimum Spanning Trees, Kruskal’s Algorithm, Prim’s Algorithm.
Structure
The course is structured as follows:
Teaching: 5hrs/week theory
Total workload per semester (13 weeks):
Lectures: 5 x 13 = 65 hrs
Homework: 18 x 6 = 108 hrs
Collaboration/Communication: 7 hrs
Total: 180 hrs
Evaluation
The final exam of the course is comprised of 7-8 problems involving the following topics:
Propositional Calculus
Binary Relations and their properties
Pigeonhole principle
Mathematical Induction
Combinatorics
Recursive relations
Generating functions
Graphs and Trees
The above evaluation scheme is announced to the students (a) through the course’s homepage, (b) during the first lectures in the class.
Oral Exams
The purpose of the the course “Discrete Mathematics” is to provide the students with the essential knowledge, skills and techniques of discrete mathematics, which play a crucial role in the analysis of a wide range of problems occurring in the field of computer science. With the completion of the course the student should be able to:
Understand the basic notions of naive set theory and apply set operations.
Understand the concept of set cardinality, to distinguish and describe, enumerable and non-enumerable sets, finite and infinite sets.
Apply the (generalized) pigeonhole principle to the solution of real life problems.
Understand the concept of binary relation and recognize partial orders and equivalence relations. Apply the corresponding theory to computer science problems.
Understand the syntax of propositional logic as a formal language and compose formulas corresponding to natural language statements.
Extract logical conclusions using the semantics of propositional logic and understand the notions of tautology and contradiction.
Understand mathematical induction and be able to apply for the proof of validity of propositions depending on a natural number.
Know the basic principles and models of combinatorial analysis and be able to calculate the number of cases in wide range of combinatorial problems. Furthermore, the student will be able to compose models for the solution of more complex problems.
Understand the relation between sequences and generating functions and explain the difference between ordinary and exponential generating functions.
Compose appropriate generating functions for the solution of particular combinatorial problems and compute the coefficients corresponding to the result.
Recognize the particular form of recursive relation and compute the closed formula solution using generating functions where applicable.
Understand the basic concepts and terminology of graph theory and particularly of trees. Evaluate and recognize the role of graphs as a theoretical model for a wide variety of problems in computer science.
Identify the presence of particular features in given graphs, such as Euler and Hamilton cycles or bipartiteness. Apply well established algorithms (Dijkstra, BFS, DFS, Prim, Kruskal) and understand their application in practical problems.
EPP, SUSANNA S.: Discrete Mathematics with Applications, Wadsworth, 1990, ISBN 0495391328
GRAHAM, R., KNUTH, D., PATASHNIK, O.: Concrete Mathematics, Addison Wesley, 1994.
ROSEN K.H., Discrete mathematics and its applications. New York: McGraw-Hill, 2012.
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.
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.
WITALA, S, A.: Discrete Mathematics. A Unified Approach, McGraw Hill, 1987.
