Math112BKK
Combinatorics & Graphs
Faculty
Ondrej Kuzelka
Assistant Professor at Czech Technical University in Prague
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
This course covers basic topics from discrete mathematics. It starts by introducing several parts of combinatorics which are not covered in the previous courses. However, the main focus of the course is on graph theory and its applications. The topics covered include classical problems on graphs, such as finding shortest paths, minimum spanning trees, maximum flows in networks, etc.
Learning highlights
- Solve algorithmic problems on graphs, such as those related to shortest paths, Euler paths, minimum spanning trees, flows and matchings.
- Model real-life problems using the language of graph theory
- Use trees and know how to apply them
- Prove simple discrete math propositions
Course outline
15 classes
Types of Proofs in Discrete Mathematics:
Direct proof, proof by induction, proof by contradiction. We will need these for the rest of the course. Concrete examples.
Permutations and Combinations Revisited:
Different representations of permutations, properties of factorials and combination numbers. (Here, we will use some of the proof methods from Session 1.)
Ordinary Generating Functions:
Combinatorial counting with generating functions (e.g. the money-changing problem), operations with generating functions.
Sampling and Enumeration:
Enumerating and sampling permutations, combinations and tuples
Combinatorics Recap
Combinatorics Exam
Combinatorics Exam
Introduction to Graphs:
Basic Notions: Directed and undirected graphs, graph representations (adjacency matrix, adjacency list, incidence matrix), paths, cycles, connectedness. Degree sequence. When are two graphs equivalent? Examples of graphs in the real world.
Euler Paths and Euler Cycles
Euler paths and cycles. Euler paths vs Hamiltonian paths. Applications (De Bruijn sequences).
Planar Graphs
Drawing a graph. Euler’s formula. Example: Wells and houses. Drawing on surfaces other than the plane.
Trees
Trees, rooted trees, ordered trees. Applications.
Minimum Spanning Trees
Spanning trees, minimum spanning trees.
Shortest Paths
Shortest paths in graphs with non-negative weights, shortest paths in graphs with general weights.
Flows in Graphs I
Flows in graphs, max-flow min-cut theorem
Flows in Graphs II
Applications (e.g. matching in bipartite graphs)
Graphs Recap
Graphs Recap
Graphs Exam
Graphs Exam
Methodology
Sessions will consist of a lecture part and a practice session. In the practice sessions, students will be solving pen-and-paper exercises as well as simple programming exercises. Practice sessions will help students digest the material from the lectures. In addition to that, students will be solving home works which will constitute 40% of the final grade.
Grading
Ondrej received his PhD in Artificial Intelligence and Biocybernetics from Czech Technical University in Prague in 2013. After that he did postdocs at KU Leuven in Belgium and at Cardiff University in UK. He returned to Prague in 2019 where he is now an assistant professor. His research interests lie at the intersection of artificial intelligence and combinatorics. He is currently leading a project on generative relational models. He is also an associate editor of AI Communications and an editorial board member of Machine Learning Journal.
See full profileApply for this course
Combinatorics & Graphs
by Ondrej Kuzelka
Total hours
45 Hours
Dates
May 09 - May 27, 2022
Fee for single course
€1500
Fee for degree students
€750
How to secure your spot
Complete the form below to kickstart your application
Schedule your Harbour.Space interview
If successful, get ready to join us on campus
FAQ
Will I receive a certificate after completion?
Yes. Upon completion of the course, you will receive a certificate signed by the director of the program your course belonged to.
Do I need a visa?
This depends on your case. Please check with the Spanish or Thai consulate in your country of residence about visa requirements. We will do our part to provide you with the necessary documents, such as the Certificate of Enrollment.
Can I get a discount?
Yes. The easiest way to enroll in a course at a discounted price is to register for multiple courses. Registering for multiple courses will reduce the cost per individual course. Please ask the Admissions Office for more information about the other kinds of discounts we offer and what you can do to receive one.