Bachelor
2026/2027
Discrete Mathematics 2
ID 1125404
Type:
Compulsory course (Data Science and Business Analytics)
Delivered by:
Big Data and Information Retrieval School
Where:
Faculty of Computer Science
When:
2 year, 1, 2 module
Open to:
students of one campus
Language:
English
ECTS credits:
4
Contact hours:
56
Course Syllabus
Abstract
The course is a natural follow up of the course Discrete Mathematics. This course covers topics that are not covered in traditional courses of calculus, algebra and linear algebra, but are part of the basic mathematic culture. The course provides theoretical foundations for courses of a more applied nature: programming, algorithms and data structures, data analysis, discrete optimization.
Learning Objectives
- After finishing this course students will be prepared to read more specialized literature on graphs and Boolean functions.
- Students will learn and analyze several important algorithms on graphs and Boolean functions.
- Students will be able to recognize hard computational problems and justify the use of heuristic and brute force algorithms for such problems.
Expected Learning Outcomes
- Will master the Quine-McCluskey method of DNF minimization.
- Will know basic algorithms of searching shortest spanning trees.
- Will know the Ford-Fulkerson’s algorithm of finding the maximum flow.
- Will be able to establish equivalence of Boolean formulas.
- Will be able to establish completeness of sets of Boolean functions.
- Will be able to prove for some problems that they are computationally hard in some sense (NP-complete, NP-hard, etc.)
- Able to establish equivalence of Boolean formulas.
- Able to establish completeness of sets of Boolean functions.
- Master the Quine-McCluskey method of DNF minimization.
- Able to prove for some problems that they are computationally hard in some sense (NP-complete, NP-hard, etc.)
Course Contents
- Introduction to Graph theory
- Boolean algebra
- DNF minimization problem
- Computational complexity and hard algorithmic problems, the problem P = NP
Assessment Elements
- Homework assignments <HW>
- Quizzes <QZ>
- Colloquium <CO>
- Examination control work <EX>
Interim Assessment
- 2026/2027 2nd module
= MIN(X, round(0.16 * + 0.2 * + 0.29 * + 0.35 * )), where X=9 if student have defended from 3 to 5 bonus tasks from homework assignments to any seminarian of our course (not necessarily a seminarian of the student's group), X=10 if student have defended at least 6 bonus tasks from homework assignments to any seminarian of our course (not necessarily a seminarian of the student's group).
Bibliography
Recommended Core Bibliography
- Boolean Functions, monography, 687 p., Crama, Y., Hammer, P. L., 2011
- Function algebras on finite sets : a basic course on many-valued logic and clone theory, Lau, D., 2006
- Graph theory, Bondy, J. A., 2008
Recommended Additional Bibliography
- Комбинаторная оптимизация : теория и алгоритмы, Корте, Б., 2015
- Лекции по дискретной математике : учебник, , 2021
- Лекции по теории графов : учеб. пособие, Емеличев, В. А., 2009