Lectures:
Part I - Introduction to discrete mathematics.
The scope and goals of Discrete mathematics. Sets, elements, k-combinations, k-permutations, related formulas.
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.
Formal foundations of dicscrete math: relations, mappings, equivalence relations, partial orders.
Algorithmic aspects: practical implementation of sets and relations.
Generating 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.
Exercises:
Following the course content.
Project:
Each student will prepare one project which contains a part concerning Discrete mathematics and a part concernig Graph Theory.
Part I - Introduction to discrete mathematics.
The scope and goals of Discrete mathematics. Sets, elements, k-combinations, k-permutations, related formulas.
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.
Formal foundations of dicscrete math: relations, mappings, equivalence relations, partial orders.
Algorithmic aspects: practical implementation of sets and relations.
Generating 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.
Exercises:
Following the course content.
Project:
Each student will prepare one project which contains a part concerning Discrete mathematics and a part concernig Graph Theory.