Discrete Mathematics II
Weekly Hours: 5
ECTS Credits: 6
Course Homepage: http://www.cse.uoi.gr/~kontog/courses/Discrete-Math-2/
Description: Elements of number theory: Divisibility. Primality. Sieve of Eratosthenes. b-ary representations of numbers. Divisibility and primality criteria. Greatest common divisor and minimum common multiplier. Euclid’s algorithm. Chinese remainder theorem.
Graph theory: Degree, subgraph, handshaking lemma, special graphs, morphisms. Representation of graphs. Cut sets and separators, edge/vertex connectivity, Menger’s theorem. Trees, properties and characterization, counting, special trees (e.g., m-ary trees), pre-/in/post-order traversals. Breadth/Depth first search of a grap, minimum spanning trees. Lengths and distances in graphs, shortest paths, cycles of negative length. Euler circuits and trails. Hamilton cycles and paths. Planarity, Euler’s formula, Kuratowski’s theorem.
Recursive relations and recursively defined discrete structures: Sequences. Introduction to sums, computing techniques of sums. Recursions. Homogeneous / non-homogeneous linear recursive equations. «Divide and Conquer» algorithm and recurrence relations.
Generating functions: Ordinary and exponential generating functions of sequences. Generalized binomial theorem. Usage of generating functions as counting tools, for solving recurrence relationsand for proving identities.
First-order Logic: Laws of first-order logic. Usage of quantifiers. Tarski’s truth. Limitations of first-order logic.
Finite automata: Recognition of a language by an automaton, automaton simplification, deterministic / non-deterministic finite automata and their equivalence.