Discrete Mathematics DSBA 2023/2024

Instructors

The lecturer

My name is Evgeny Dashkov. Feel free to contact me via email: edashkov@gmail.com, Telegram, or VK.

My Assistant (the person responsible for the tables etc.): Elizaveta Levshina.

Seminar instructors

Group	231	232	233	234	235
Teachers	Evgeny Dashkov	Boris Danilov		Diego Buitrago
Teaching Assistants	Zhou Jinyu	Alexander Ukhanov	Marat Galyavov	Oleg Bozhenov	Nikita Kozlovtsev

Current performance

The Table.

Homework

The homework includes a few problem sets, one in a fortnight or so (the deadlines are announced on giving each set). Every problem set consists of about 10 – 15 problems, some of which are labeled as ‘bonus’ while all the remaining are considered ‘ordinary’. One can get either 0, ½, or 1 point for each problem. For the entire homework, two values are computed:

HW = (the sum of points given for ordinary problems) / #(ordinary problems);

HW* = (the sum of points given for bonus problems) / #(bonus problems).

The value HW1 is similar to HW but restricted to the problem sets given in Module 1.

A student may be required to explain orally his written solution to any problem. His grade for the problem may be decreased if he fails to do so properly.

Exam 1

A written examination is held past Module 1. Students may not consult any sources during the exam. Some problems of the exam are labeled as ‘bonus’; the others are ‘ordinary’. Each problem solution is graded with either 0, ¼, ½, ¾, or 1 point, and the entire exam with two values:

Exam1 = (the sum of points given for ordinary problems) / #(ordinary problems);

Exam1* = (the sum of points given for bonus problems) / #(bonus problems)

Colloquium

An oral colloquium is held at the beginning of Module 3. Each student is given two questions concerning statements and definitions as well as one question requiring a proof. After no less than 45 minutes of preparation (when using any literature is allowed), the student is required to answer ‘from scratch’, that is, with no recourse to any materials. The examiner may pose additional questions as he sees fit. The student may get from 0 to 10 integer points for his answer; the value Colloq is just this score.

Please find the question list and rules here.

Exam 2

A written examination is held at the end of the Course. Students may not consult any sources during the exam. The examination takes about 120 minutes. Some problems of the exam are labeled as ‘bonus’; the others are ‘ordinary’. Each problem solution is graded with either 0, ¼, ½, ¾, or 1 point; finally, two values are computed:

Exam2 = (the sum of points given for ordinary problems) / #(ordinary problems);

Exam2* = (the sum of points given for bonus problems) / #(bonus problems).

Bonus activities

The students may be graded for a variety of ‘bonus activities’ (like quizzes, etc.) with an overall integer value Bonus from 0 to 25.

Exam retaking

Examinations 1 and 2 are subject to be retaken if Module 1 grade or Final grade (see below), respectively, is unsatisfactory. Retaking the exam is similar to the regular examination. The resulting grade is substituted for that of the latter. The last try Commission retaking is held for those whose final grade is still unsatisfactory after the retaking. A designated Commission carefully examines the student’s performance and gives him a final mark not better than ‘satisfactory’; at that the Commission is not bound by the grading formulas herein.

Course materials

Course chat.

Lecture notes

Original English version

A Russian translation by volunteering students (you are welcome to join their ranks)

Other resources

• The Course's Google Directory

• Past years' videos

• We have a dedicated server to hold an online meeting if we need one.

Problem sets

Class problems

• Problem Set 1

• Problem Set 2

• Problem Set 3

• Problem Set 4

• Problem Set 5

• Problem Set 6

• Problem Set 7

• Problem Set 8

Assignment deadlines

Home problem set	Deadline
	231	232	233	234	235
HW1a	09/29	10/10	10/10	09/29	09/29
HW1b	10/09	10/10		10/09	10/09
HW2a	Oct 24	Oct 24	Oct 24	Oct 24	Oct 24
HW2b	Nov 16	Dec 7	Dec 7	Nov. 19	Nov. 19
HW2c	Dec 18	Dec 14	Dec 19	Dec 20	Dec 20
HW3a	Jan 29	Feb 8	Feb 8
HW3b	Feb 19	Feb 29	Feb 29
HW4a	Mar 4	Mar 7	Mar 7
HW4b	Mar 11

Each deadline is set by the respective group's instructor.

Grading system

For the final grading, we compute the following values:

Module 1 grade = round ((50*HW1 + 50*Exam1)/100);

basic = (21*Exam1 + 21*Colloq + 28*HW + 30*Exam2)/100;

adv = (30*Exam1* + Bonus + 35*HW* + 35*Exam2*)/100;

Final grade = round(min(10, 8 * basic + 2 * adv)).

The final grade is rounded half up to an integer. All the other values are reported with the greatest precision available.

Recommended reading

Please notice that The Book for our Course does not exist. The latter is based on many sources.

1. Anderson J. A., Discrete Mathematics With Combinatorics. Prentice Hall, 2003.
2. Biggs N. L., Discrete mathematics. 2nd ed., New York; Oxford: Oxford University Press, 2004.
3. Gavrilov G. P., Sapozhenko A. A. Problems and Exercises in Discrete Mathematics. Kluwer Texts in the Mathematical Sciences 14. Springer, 1996.
4. Lehman E., Thomson Leighton F., Meyer A. R. Mathematics for Computer Science, 2017.
5. Lovasz L., Vesztergombi K. Discrete Mathematics. Lecture Notes; Yale University, 1999.
6. Melnikov O., Sarvanov V., Tyshkevich R., Yemelichev V., Zverovich I. Exercises in Graph Theory. Kluwer Texts in the Mathematical Sciences 19. Springer, 1998.
7. Rosen K. H. Discrete Mathematics and Its Applications. McGraw-Hill, 1999.
8. Stein C., Drysdale R. L., Bogart K. Discrete mathematics for computer scientists. Addison-Wesley, 2010.
9. Vinogradov I. M. Elements of number theory. Dover, 1954.

In Russian

If you understand Russian (by any chance), you will probably benefit from reading the following books.

1. Виноградов И. М. Основы теории чисел. 9-е изд., М.: Наука, 1981.
2. Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. Лекции по дискретной математике.
3. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., М.: ФИЗМАТЛИТ, 2004.
4. Дашков Е. В. Введение в математическую логику. Множества и отношения. М.: МФТИ, 2019.
5. Зубков А. М., Севастьянов Б. А., Чистяков В. П. Сборник задач по теории вероятностей. 2-е изд., М.: Наука, 1989.
6. Мельников О. И. Теория графов в занимательных задачах. 5-е изд., М.: Книжный дом "ЛИБРОКОМ", 2013.
7. Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016.