Introduction to Combinatorics and Graphs

2023/2024

Academic Year

ENG

Instruction in English

3

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Compulsory course

When:

4 year, 1, 2 module

Instructor

Хрыстик Михаил Андреевич

Course Syllabus

Abstract

We will start with a brief introduction to combinatorics, the branch of mathematics that studies how to count. Basics of this topic are critical for anyone working in Data Analysis or Computer Science. We will illustrate new knowledge, for example, by counting the number of features in data or by estimating the time required for a Python program to run. Next, we will apply our knowledge in combinatorics to study basic Probability Theory. Probability is everywhere in Data Analysis and we will study it in much more details later. Our goals for probability section in this course will be to give initial flavor of this field. Finally, we will study the combinatorial structure that is the most relevant for Data Analysis, namely graphs. Graphs can be found everywhere around us and we will provide you with numerous examples. We will mainly concentrate in this course on the graphs of social networks. We will provide you with relevant notions from the graph theory, illustrate them on the graphs of social networks and will study their basic properties. In the end of the course we will have a project related to social network graphs.

Learning Objectives

• • Use methods of Combinatorics to count objects • Calculate probabilities of events using definition and properties of probabilities • Analyze the structure of graphs using parameters • Apply knowledge in Discrete Mathematics for social network analysis

Expected Learning Outcomes

• Analyze the structure of graphs using parameters: clustering coefficients, diameter etc.
• Apply basic combinatorial methods in programming
• Apply standard operations on sets
• Calculate probabilities of events using definition and properties of probabilities
• Categorize basic combinatorial problems into standard settings
• Categorize combinatorial problems into standard settings
• Combine several combinatorial settings to solve counting problems
• Compare social network graphs (from datasets) with random graphs, and see how the parameters change.
• Develop graph analysis software in Python using NetworkX
• Discover properties and types of graphs, given by geometric (pictorial) representation
• Give examples of graph parameters and their usage in network analysis
• Give examples of graphs used in various application areas
• Give examples of random experiments, outcomes and events
• Use basic properties of binomial coefficients
• Use graph parameters for establishing non-isomorphism of graphs
• Use methods of combinatorics to count objects
• Use standard algorithms for traversing graphs
• Practice in using Network for social network analysis
• Recognize operation an events (union, intersection, complement event)
• Use basic methods of combinatories to count obiects

Course Contents

• Basic Combinatorics
• Advanced Combinatorics
• Discrete Probability
• Introduction to Graphs
• Basic Graph Parameters
• Graphs of Social Networks

Assessment Elements

• Тесты на онлайн-платформе
• Проект на онлайн-платформе
• Контрольная работа в течение модуля
• Экзамен

Interim Assessment

• 2023/2024 2nd module
  0.25 * Контрольная работа в течение модуля + 0.15 * Проект на онлайн-платформе + 0.2 * Тесты на онлайн-платформе + 0.4 * Экзамен

Bibliography

Recommended Core Bibliography

• Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108

Recommended Additional Bibliography

• Conradie, W., & Goranko, V. (2015). Logic and Discrete Mathematics : A Concise Introduction, Solutions Manual. Chichester, West Sussex: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=987020