## Discrete Mathematics

### 授業情報

• 講師： シモセラ エドガー
• 日程： 2021年10月〜2022年01月
• 曜日時限： 木曜日　4時限（14:45〜16:15）
• 教室： Online and 53-303
• メール： ess@waseda.jp
The class is planned to be held dominantly online with on-demand. Some classes will be taught optionally offline. There will be no requirement to come to campus and no final exam!
Depending on the evolution of the corona virus, details are subject to change.

### Overview

This course covers elementary discrete mathematics for computer science and engineering. An emphasis is given on mathematical definitions and proof with topics covering proof methods, induction, graph theory, counting and discrete probability. The course will be given in English.

The course will be evaluated fundamentally with a midterm examination on the 8th week and a final examination on the 15th week. In the case that the midterm evaluation goes poorly, it will not be used in the evaluation, which will then be based on fundamentally the final examination. Small in-class quizzes and attendance will also be considered in the final grade.

### Objectives

1. Learn to think logical and analytically
2. Be able to do simple proofs
3. Ability to understand and manipulate graphs
4. Notions of discrete probability

### Schedule

1. Introduction and Proofs 資料 MCS Chapters 1+2 DM Chapter 1
2. Induction I 資料 MCS Chapter 2+5 DM Chapter 5
3. Induction II 資料 MCS Chapter 5 DM Chapter 5
4. Number Theory I 資料 MCS Chapter 9 DM Chapter 4
5. Number Theory II 資料 MCS Chapter 9 DM Chapter 4
6. Graph Theory I 資料 MCS Chapter 10+11 DM Chapter 10
7. Graph Theory II 資料 MCS Chapter 12+13 DM Chapter 10
8. Graph Theory III 資料 MCS Chapter 13 DM Chapter 10
9. Probability 資料 MCS Chapter 17 DM Chapter 7
10. Conditional Probability 資料 MCS Chapter 18
11. Independence 資料 MCS Chapter 18
12. Expectation I 資料 MCS Chapter 19
13. Expectation II 資料 MCS Chapter 20
14. Recurrences and Random Walks 資料 MCS Chapter 21

### Textbook

• MCS Main Textbook Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, 2017. PDF
• DM Kenneth Rosen, Discrete Mathematics and Its Applications, McGraw-Hill Education, 2018.