Combinatorics and Graphs
Faculty
Sergey Nikolenko
Chief Research Officer, Neuromation Head of AI Lab, PDMI RAS
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
Combinatorics and graph theory lay at the heart of discrete mathematics and computer science. In the course, we begin with a brief review of the fundamentals of combinatorics---counting, permutations, binomial coefficients, and the pigeonhole principle---and then devote most of the course to the fundamentals of graph theory. We cover the most common definitions and ideas of graph theory, proving important theorems and introducing important algorithms, but mostly aiming to simply establish the common language of discrete mathematics and computer science.
Learning highlights
- Understand the basic tools of combinatorics for counting
- Know and understand the basic notions of graph theory
- Be able to prove the basic theorems of graph theory taught in the course
- Know and be able to apply basic algorithms of graph theory taught in the course
Course outline
4 classes
Counting
The four principles of counting: addition, multiplication, subtraction, and division. Examples.
Permutations and combinations
Permutations, number of different permutations. Subsets, number of different subsets. Binomial coefficients. Sum of binomial coefficients.
The pigeonhole principle
The pigeonhole principle. Sample applications. The Chinese remainder theorem.
Graphs: the basics
Definitions: graph, vertex, edge, loop, degree, path, cycle, directed and undirected graphs, connected and disconnected graphs, adjacency matrices.
Prerequisites
This course is one of three in a wholistic series.
Students that have already taken MSL-111 and those with prior experience with HTML, CSS, and Javascript building simple web pages will be good candidates for this module.
Sergey Nikolenko is a computer scientist with vast experience in machine learning and data analysis, algorithms design and analysis, theoretical computer science, and algebra. He graduated from St. Petersburg State University in 2005, majoring in algebra (Chevalley groups), and earned his Ph.D at the Steklov Mathematical Institute at St. Petersburg in 2009 in theoretical computer science (circuit complexity and theoretical cryptography). Since then, Sergey has been interested in machine learning and probabilistic modeling, producing theoretical results and working on practical projects for the industry.
Sergey Nikolenko is currently serving as the Chief Research Officer at Neuromation, leading the Artificial Intelligence Lab at the Steklov Mathematical Institute at St. Petersburg, and teaching at the St. Petersburg State University and Higher School of Economics. Dr. Nikolenko has published more than 170 research papers on machine learning (ICML, CVPR, ACL, SIGIR, WSDM...), analysis of algorithms (SIGCOMM, INFOCOM, ICNP…), and other fields, several books, including a bestselling “Deep Learning” book (in Russian), lecture courses in ML, DL, other fields of computer science (St. Petersburg State University, NRU Higher School of Economics...) and much more. He has extensive experience in managing research and industrial AI/ML projects.
See full profileApply for this course
Combinatorics and Graphs
by Sergey Nikolenko
Total hours
45 Hours
Dates
Jan 08 - Jan 26, 2018
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.