Bachelor 2021/2022

Discrete Mathematics 2

Type: Compulsory course

Area of studies: Applied Mathematics and Information Science

Delivered by: Big Data and Information Retrieval School

Where: Faculty of Computer Science

When: 2 year, 1, 2 module

Mode of studies: offline

Open to: students of one campus

Instructors: Boris Radislavovich Danilov, Anastasia Trofimova

Language: English

ECTS credits: 4

Contact hours: 60

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

• Shape basic knowledge about the fundamental notions, models and methods in graph theory, Boolean algebra, discrete optimization, complexity theory.
• Familiarize students with theoretical knowledge required to build proper models for applied algorithms, analyze and assess them
• Provide the theoretical foundation for courses in programming, algorithms and data structures, data analysis, discrete optimization.

Expected Learning Outcomes

• Be able to prove NP-completeness of problems on practice
• Be able to provide recognition problems counterparts to search problems and vice versa
• Obtain practical skills of construction of various unambigous DNFs: Blake canonical form, core DNF, Quine's DNF, DNF the sum of irreducible DNFs
• Understand the problem of minimization of DNF and various complexity measures for DNFs
• Understand the problem P versus NP and associated notions
• Be able to apply Prim's algorithm to find shortest spanning tree of a graph.
• Be able to test graphs for planarity.
• Be able to encode plane tree and draw plane tree from an encoding.
• Be able to apply Ford-Fulkerson's algorithm to find maximal flow in a graph.
• Be able to establish equivalence of Boolean formulas.
• Be able to establish completeness of sets of Boolean functions.
• Will master the Quine-McCluskey method of DNF minimization.

Course Contents

• Induction and recursion on abstract sets with examples from the theory of formal languages
• Cybernetic functions, formulas and their transformations with examples from Boolean algebra
• The problem of DNF minimization and associated algorithmic obstacles
• Circuits, their complexity and methods of synthesis
• Introduction to computability theory. Decidable, semidecidable and undecidable computational problems
• The theory of complexity and P versus NP problem

Assessment Elements

• Homework assignments
  Homework problems are assigned starting from the first seminar once a week at each seminar excluding the last seminar of the course. Each student is expected to solve problems individually. Solutions must be performed in hand-written form on a piece of paper and contain the full name of the student, his group number, and the list of solved problems written in clear and recognizable manner. Each problem in the homework must contain it's respective number in the assignment, the solution and the answer explicitly given after the written word "answer". When several answers are given for a task the inspector may choose any of the specified answers to score the task. When problem is not supposed to have an answer (exercises to prove facts) then the complete proof should be provided. Each step in the solution of a task must be supported by a mathematical argument, unfounded statements may lead to lowering the score up to "0" (zero) points for the task. Only statements and theorems provided on lectures or seminars can be used without a proof. The correct answer for the task without provided solution is scored with "0" (zero) points. These rules also apply for the other written tests (midterm written test and final written test).
• Midterm written test
  The planned form of conducting the midterm written test is the offline written test at the start of the second module. In the case of aggravating of epidemiologic state the midterm written test may be carried out online, in which case the rules and the form of the test are announced separately and may or may not match the rules announced for the offline form of the test. Rules for submitted solutions follow the rules described in the comment for the homework assignments.
• Final written test
  The planned form of conducting the final written test is the offline written exam. In the case of aggravating of epidemiologic state the final written test may be carried out online, in which case the rules and the form of the test are announced separately and may or may not match the rules announced for the offline form of the test. Rules for submitted solutions follow the rules described in the comment section for the homework assignments.

Interim Assessment

• 2021/2022 2nd module
  0.37 * Midterm written test + 0.26 * Homework assignments + 0.37 * Final written test

Bibliography

Recommended Core Bibliography

• Computational complexity : a modern approach, Arora, S., 2010
• Computational complexity, Papadimitriou, C. H., 1994
• Discrete mathematics, Biggs, N. L., 2004
• Introduction to the theory of computation, Sipser, M., 2006
• Introduction to the theory of computation, Sipser, M., 2013
• Introduction to the theory of computation, Sipser, M., 2016