Discrete Mathematics 1 DSBA 2025/2026 — различия между версиями

Текущая версия на 06:45, 2 декабря 2025

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.): Maria Krotova.

Seminar Instructors and Teaching Assistants

Whom should I ask?

If you have a question or comment concerning the mathematical content of our course, it is best to post it to our student chat. Alternatively, you may address your question to your Teaching Assistant, Seminar Instructor or the Lecturer (say, if your question discloses an important idea for a HW problem). It is much better to ask and get to know than not to ask and remain ignorant. Please do not hesitate to ask your mathematical questions!

If you need a more detailed consultation concerning the course's mathematics, please be informed that our Teaching Assistants usually hold periodic consultations while the Seminar Instructors and Lecturer have some designated time for counseling students. Still, the best thing to do is to arrange a consultation in advance via a personal communication.

Homework-grading related questions should be directed to your teaching assistant first; then to your seminar instructor and to the lecturer just in case of any disagreement.

Organizational, administrative, legal or paperwork questions must be addressed to the Student Service Center, Study Office or other relevant offices first and foremost. If you have been redirected to us with such a question nevertheless, please contact the Lecturer's Assistant first.

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. These sets may be subdivided further for students’ convenience.

We expect you to try solving every homework problem. Nevertheless, in Modules 2 and 3 we are going to grade the solutions of about one quarter of all problems. The problems chosen to be graded will be the same for all students and our choice will be revealed past the deadline for each respective problem set.

Still, we suggest you try solving every homework problem. In particular, some of these problems will be given as special 'homework tests' to be held in class. The tests are scheduled to Modules 2 and 3 late weeks.

A student may be required to 'defend' (i.e., 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. The examination takes about 120 minutes. An integer weight is assigned to every problem.

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.

Please find the question list and rules [here].

Exam 2

A written examination is held past Module 3. Students may not consult any sources during the exam. The examination takes about 120 minutes. An integer weight is assigned to every problem.

Bonus activities

Throughout the course, the students may be graded for a variety of ‘bonus activities’ (like quizzes, etc.) either offline or online.

Course materials

Course chat. This is our primary outlet for course announcements, questions, and discussions. Please join it!

Lecture notes

Original English version

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

Classes recordings

Lecture video archive

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

Assignment deadlines

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

Assessment and Grading

Homework

The homework is graded in three batches: one (HW_A) includes everything to be submitted in Module1, another (HW_B) includes all the problems submitted in other modules that we will choose to be graded (see Homework section for an explanation). The last batch (HW_Test_B) consists of two in-class tests; each test takes about 80 minutes and contains 6 -- 8 problems from the homework problem sets or very similar to those. For each problem, the student is given a score from 0 to 1 point (in fractional values) according to the progress he made.

The homework graded are computed the following way (before rounding):

HW_A = 10 * (the sum of points given for the problems) / #(problems); all the problems are to be graded.

Grade HW_B is computed similarly but for its respective period of Modules 2 and 3:

HW_B = 10 * (the sum of points given for the problems) / #(problems subject to be graded); a few chosen problems are to be graded.

HW_Test_B = 10 * (the sum of points given for the problems in both the tests) / #(problems in both the tests).

Exam1 and the Interim Assessment

Each problem solution is graded with a fractional score from 0 to 1 point, and the entire exam with the value (before rounding)

Exam1 = 10 * (p1 * w1 + ... + pn * wn) / (w1 + ... + wn), where pi is the score and wi is the weight for the i-th problem.

The Interim grade 1 is computed past Module 1 and equals:

Interim1 = round(Interim1'), where

Interim1' = 0.5 * HW_A + 0.5 * Exam1.

(Here and everywhere, rounding is according to the usual arithmetic rules.)

Colloquium

For each of the 'definition' two questions, the student is given a score from 0 to 2 points, and from 0 to 4 points for the ‘proof’ question (all in fractional values). The Colloq grade is computed the following way (before rounding):

Colloq = 10 * (the sum of points given) / 8.

Bonuses

Each student is given a score according to his progress in bonus activities, which results in the grade

Bonus = 10 * #(points given) / #(points possible).

The number of possible points varies but it is between 1 and 25 usually.

Exam2, the Second Interim, and the Final Assessment

Each problem solution is graded with a fractional score from 0 to 1 point, and the entire exam with the value (before rounding)

Exam2 = 10 * (p1 * w1 + ... + pn * wn) / (w1 + ... + wn),

where pi is the score and wi is the weight for the i-th problem.

The Interim grade 2 is computed past Module 3 and equals:

Interim2 = round(Interim2'), where

Interim2' = 0.085 * HW_B + 0.210 * HW_Test_B + 0.295 * Colloq + 0.06 * Bonus + 0.35 * Exam2.

The final grade for the course is

Final = round(0.3 * Interim1' + 0.7 * Interim 2')

Generally, nobody is exempt from the examinations.

Plagiarism regulations

Plagiarism, that is, all forms of cheating with doing your academic assignments, including any unauthorized help of AI or another person, will not be tolerated. In this course, using AI is not generally authorized. Clearly, we may not have a definitive proof that somebody is cheating (notice, however, that AI-generated solutions to mathematical problems are quite conspicuous if they have not been edited heavily). Therefore, we will reserve the right to ask a suspect student to 'defend' his any written work, that is, to explain it orally and in person. So our regulations stipulate:

If plagiarism is detected (including material generated with the help of generative AI without prior approval from the teacher), the assessment element will be assigned a score of "0". If there is a suspicion that the task was not completed independently, the teacher has the right to initiate an additional verification or a defense of this particular assessment element. The final grade for the element will be based on the results of such verification or defense. The teacher also has the right to randomly invite any student to defend any assessment element, regardless of plagiarism or suspicion. If the student refuses or fails to defend the work, the grade for this element will be annulled and recorded as "0".

A final word of advice. Using AI regularly (and this is addictive!) instead of your natural intelligence will make you stupid and intellectually impotent in no time---at the price of a slight grade advantage (assuming your cheating goes unpunished). Do you really want it in this competitive world?

Exam retaking

Examinations 1 and 2 are subject to be retaken if either the Interim1 or Final grade, respectively, is unsatisfactory (i.e., < 4). Retaking an exam is similar to the regular examination. The resulting grade is substituted for that of the latter (that is, retake grade is assigned to the variable Exami in the respective formula, whose value is then reevaluated). Those whose Interim or Final grade is still unsatisfactory after the first retake will have a (tough) choice to make.

Please take into account the following regulation according to the ПОПАТКУС:

On the first and second retakes, the cumulative course grade is taken into consideration. In case of receiving an unsatisfactory final grade after the first retake, the student may refuse to participate in the second retake and instead repeat the course according to the individual curriculum. The cumulative grade is formed again as a result of repeated courses. After completing the repeated course, the student is given a second retake only, which the student previously refused.

The 'cumulative grade' here means all the variables in the grading formulas except Exami, which are the only ones to be retaken. The 'second retake' is similar to the first one and it is evaluated according to the same formula with the same values of 'cumulative' variables. This poses an obvious risk for anyone whose 'cumulatives' are low!

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.