Course information

Sets and set operations. Countable and uncountable sets, the diagonalization principle, uncomputability, Russell's Paradox. Relations and functions. Binary relations, properties of binary relations, equivalence relations, partial and total orders, closures. Elements of propositional and predicate logic. Proof techniques, mathematical induction, the pigeonhole principle. Elements of Graph Theory. Types of graphs, vertex degree, subgraphs, graph isomorphism, cliques and independent sets, chromatic number. Walks, trails, paths, distances, shortest paths, Euler circuits and trails, characterization of Eulerian graphs, Hamilton cycles and paths, Dirac's Theorem. Trees, characterization of trees, spanning trees and properties, applications. Planar graphs, Euler's formula, Kuratowski's Theorem. Graph connectivity, bridges and cut-sets, cut-points and separators, Menger's Theorem, networks and flows. The Principle of Inclusion-Exclusion. Combinatorial enumeration. Product and sum rules, applications of the Inclusion-Exclusion Principle, permutations and arrangements, combinations, binomial coefficients, Pascal's Triangle, distribution of distinct and non-distinct objects into containers, construction of permutations and combinations, elements of discrete probability, elements of information theory. Generating Functions. Basic properties, application in computing sums, application in solving combinatorial problems, exponential generating functions. Solving linear recurrence relations with constant coefficients. Characteristic equation, homogeneous solution, particular solution, solution using the generating functions method. Elements of Number Theory. Divisibility and prime numbers, Euclidean algorithm, modulo arithmetic, linear congruences, the Chinese Remainder Theorem. Asymptotic notation and asymptotic estimation.