COMBINATORICSAND GRAPHS

**SERGEY
NIKOLENKO**

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.

Sergey Nikolenko is a computer scientist with wide experience in machine learning and data analysis, algorithms design and analysis, theoretical computer science, and algebra. He graduated from the 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, Dr. Nikolenko has been interested in machine learning and probabilistic modeling, producing theoretical results and working on practical projects for the industry. He is currently employed at the Steklov Mathematical Institute at St. Petersburg and Higher School of Economics at St. Petersburg. Dr. Nikolenko has more than 100 publications, including top computer science journals and conferences and several books.

• Machine learning: probabilistic graphical models, recommender systems, topic modeling

• Algorithms for networking: competitive analysis, FIB optimization

• Bioinformatics: processing mass-spectrometry data, genome assembly

• Proof theory, automated reasoning, computational complexity, circuit complexity

• Algebra (Chevalley groups), algebraic geometry (motives)

**•** 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

**SKILLS:**

- Machine learning

- Algorithms for networking

- Bioinformatics

- Mathematical Modeling

- Python

ABOUT SERGEY

**HARBOUR.SPACE **

WHAT YOUWILL LEARN

**DATE:** 8 - 26 Jan, 2018

**DURATION: **3 Weeks

**LECTURES: **3 Hours per day

**LANGUAGE: **English

**LOCATION: **__Barcelona, Harbour.Space Campus__

**COURSE TYPE: **Offline

HARBOUR.SPACEUNIVERSITY

__@snikolenko__

**DATE: **8** **- 26 Jan, 2018

**DURATION: **3 Weeks

**LECTURES: **3 Hours per day

**LANGUAGE: **English

**LOCATION: **__B____arcelona, Harbour.Space Campus__

**COURSE TYPE: **Offline

All rights reserved. 2018

COURSE OUTLINE

**Session 1**

**Counting**

The four principles of counting: addition, multiplication, subtraction, and division. Examples.

**Session 4**

**Graphs: the basics**

Definitions: graph, vertex, edge, loop, degree, path, cycle, directed and undirected graphs, connected and disconnected graphs, adjacency matrices.

**Session 3**

**The pigeonhole principle**

The pigeonhole principle. Sample applications. The Chinese remainder theorem.

**Session 2**

**Permutations and combinations**

Permutations, number of different permutations. Subsets, number of different subsets. Binomial coefficients. Sum of binomial coefficients.

BIBLIOGRAPHY

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.

Fix the following errors: