Math108BKK
Combinatorics & Graphs
Faculty
Galina Kaleeva
Data Scientist at Yandex & HSE Lecturer
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
The course “Combinatorics and Graphs'' will provide students with a comprehensive understanding of graph theory, as well as necessary combinatorics. The course covers basic concepts of combinatorics, theoretical fundamentals of graph theory, and algorithms on graphs. Students will gain practical skills and knowledge that can be applied in advanced algorithms and data structure courses.
Learning highlights
- Understand and apply methods of combinatorics to solve problems, graph theory among them.
- Learn the basic concepts of graph theory.
- Be able to prove basic graph theory theorems and solve theoretical problems on graphs.
- Understand basic algorithms on graphs.
- Prepare for studying applications of graph theory in algorithms and data structures.
Course outline
15 classes
Session 1
Proofs recap. Proofs by contradiction and proofs by induction. Pigeonhole principle.
Session 2
Number of permutations, combinations, and partial permutations. Binomial coefficients. Binomial theorem.
Session 3
Recurrence relations. Linear recurrence with constant coefficients.
Session 4
Generating function. Computations using generating functions.
Session 5
Practice session. Review.
Session 6
Combinatorics midterm.
Session 7
Introduction to graph theory: basic notions and graph representations.
Session 8
Euler trails. Euler and semi-euler graphs. Wells and houses. Seven Bridges of Königsberg. Fleury's algorithm for constructing a Eulerian trail.
Session 9
Hamiltonian and semi-hamiltonian graphs. Ore’s theorem.
Session 10
Trees: equivalent definitions. Spanning tree. Finding a minimal spanning tree.
Session 11
Graph isomorphisms. Number of non-isomorphic trees.
Session 12
Planar graphs. Non-planar graphs: wells and houses, K_5. Kuratowski–Pontryagin theorem. Euler’s formula. Graphs on different surfaces.
Session 13
Ramsey’s theorem.
Session 14
Practice session. Review.
Session 15
Final exam
Course materials
Books
Prerequisites
Mathematical Foundations of Computing, Calculus, and Python.
Methodology
The typical 3-hour session consists of a lecture that will provide the necessary theory to later work on the practical part. In-depth understanding of the course is achieved through problem solving, both in class and at home. Homeworks provides students with more practical problems for better understanding of the course.
Grading
Galina Kaleeva obtained her degree from Lomonosov Moscow State University, where she majored in Mathematics and Mechanics.
Currently, Galina works as a Data Scientist at Yandex, where she puts her analytical skills to create a platform for school students interested in STEM: enables hypothesis generation and validation based on data, extracts insights from big data, and supports management in making decisions related to the EdTech business.
See full profileApply for this course
Combinatorics & Graphs
by Galina Kaleeva
Total hours
45 Hours
Dates
Jan 29 - Feb 16, 2024
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.