Lectures and discussions:
Part I - Introduction to discrete mathematics.
The scope and goals of Discrete mathematics. Counting selections and arrangements, related problems. Pidgeon-hole principle.
Geometric and arithmetic progressions. Inclusion-exclusion principle, binomial theorem and its applications.
Discrete probability: tossing coins, random choice, shuffling cards. Probability space and random event.
Integers and mathematical induction, the concept of proofs. Proving the formulas for numbers of subsets, k-combinations, k-permutations.
Recurrence relations, their applications and examples.
Modular arithmetics.
Algorithmic aspects: practical implementation of sets and relations. Obtaining a full list of all possible subsets k-combinations, and k-permutations.
Part II - Introduction to graph theory
Graphs and relations. Subgraphs, isomorphism, degrees, implementation. Directed graphs.
Graph connectivity, algorithms for searching. Higher degrees of connectivity, edge-connectivity. Eulerian graphs and their applications.
Distance in graphs, Dijkstra's algorithm, graph metric and its enumeration.
Trees and their characterizations, rooted trees, tree isomorphism.
Spanning trees, MST problem. Basic algorithms for MST.
Planar embeddings of graphs, Euler's formula and its applications.
Graph coloring, bipartite graphs, recognition.
Network flows: formulation and application to real life problems. Ford-Fulkerson's algorithm for maximum flow. Further applications to matching and system of representatives.
Part I - Introduction to discrete mathematics.
The scope and goals of Discrete mathematics. Counting selections and arrangements, related problems. Pidgeon-hole principle.
Geometric and arithmetic progressions. Inclusion-exclusion principle, binomial theorem and its applications.
Discrete probability: tossing coins, random choice, shuffling cards. Probability space and random event.
Integers and mathematical induction, the concept of proofs. Proving the formulas for numbers of subsets, k-combinations, k-permutations.
Recurrence relations, their applications and examples.
Modular arithmetics.
Algorithmic aspects: practical implementation of sets and relations. Obtaining a full list of all possible subsets k-combinations, and k-permutations.
Part II - Introduction to graph theory
Graphs and relations. Subgraphs, isomorphism, degrees, implementation. Directed graphs.
Graph connectivity, algorithms for searching. Higher degrees of connectivity, edge-connectivity. Eulerian graphs and their applications.
Distance in graphs, Dijkstra's algorithm, graph metric and its enumeration.
Trees and their characterizations, rooted trees, tree isomorphism.
Spanning trees, MST problem. Basic algorithms for MST.
Planar embeddings of graphs, Euler's formula and its applications.
Graph coloring, bipartite graphs, recognition.
Network flows: formulation and application to real life problems. Ford-Fulkerson's algorithm for maximum flow. Further applications to matching and system of representatives.