le

Discrete mathematics MAA 103 (2018-2019)

Instructor: Igor Kortchemski.

Tutorial Assistants:
Luca Calatroni, Mathieu Kohli, Benoit Tran.

Discrete Mathematics MAA 103 (Year 1) has two main objectives: (i) teach fundamental concepts in discrete mathematics, which are the building blocks of many different areas of science and of advanced mathematics (ii) teach how to write proofs. The course starts with elementary logic (e.g. quantifiers, different methods of proof), sets, and functions. The second part of the course introduces students to combinatorics and probability (on finite sets).

The lectures will closely follow the textbook Mathematics: A Discrete Introduction (3rd Edition) by Scheinerman. For a different presentation and broader applications concerning computer science, one may have a look at Discrete Mathematics with Applications by Epp.

Each tutorial sheet contains homework assignments, which have to be handed the next week to your TA (tutorial assistant). You **ARE** are allowed and encouraged to discuss the homework problems with other students. However, all written solutions must be individually submitted and must not be copied from somewhere else. A solution that is blatantly copied from another source will receive zero credit.

The goal of the homework assignments is to train you to write proofs on your own. The corrections of your TA are there to show you how you can improve, and the marks are there to help you see to what extent your work meets the requirement of the course.

- Tutorial sheet 1 (September 24)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises
- Tutorial sheet 2 (October 1)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises
- Tutorial sheet 3 (October 8)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises
- Tutorial sheet 4 (October 15)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 5 (October 22)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 6 (November 5)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 7 (November 12)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 8 (November 19)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 9 (November 26)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 10 (December 3)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises
- Proof of the multiplicativity property of the signature

- Midterm Exam (December 4)

- Tutorial sheet 11 (December 10)
- Solutions of the important exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 12 (December 17)
- Solutions of the exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 13 (January 7)
- Solutions of the exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 14 (January 14)
- Solutions of the exercises which have not been solved in some group.
- Solutions of the optional exercises

- Tutorial sheet 15 (January 21)
- Solutions of the exercises which have not been solved in some group.
- Solutions of the optional exercises

Do not hesitate to send me an email if you spot an error somewhere.

Midterm exam 2017-2018: exercises - solutions.

Final exam 2017-2018: exercises - solutions.

Past weeks (the numbering refers to sections in the textbook Mathematics: A Discrete Introduction by Scheinerman):

- Week 1 (September 20): Sets. (Section "To the student", Section 10: Sets I, Section 12: Sets II)
- Slides of the first part (PDF format without animations)
- Proof template 1.

- Week 2 (September 25): Functions, logical symbols, truth tables. (Section 7: Boolean algebra, Section 5: Proof).
- Truth tables (for the proof of the Very Important Theorem).

- Week 3 (October 2): Quantifiers and examples. (Section 11: Quantifiers).
- Week 4 (October 9): Functions: injectivity, surjectivity. (Section 24: Functions)
- Week 5 (October 16): Functions (images and pre-images). (Section 24: Functions)
- Week 6 (October 23): Induction. (Section 22: Induction)
*Holidays*- Week 7 (November 6): no course.
- Week 8 (November 13): Cardinality and bijective combinatorics. (Several parts of Section 12: Sets II)
- Week 9 (November 20): Binomial coefficients. (Section 17: Binomial Coefficients)
- Week 10 (November 27): Permutations (Section 27: Permutations)
- Week 11 (December 4): Midterm exam (8am-10am, Amphi Faurre)
- Week 12 (December 11): Modeling (graphs, trees). (Small excerpts of Chapter 9: graphs)
- Week 13 (December 18): Introduction to finite probability spaces. (Sections 30, 31)
*Holidays*- Week 14 (January 8): Independence and conditional probabilities. (Section 32)
- Week 15 (January 15): Random variables. (Section 33)
- Week 16 (January 22): Structure in randomness.
- Slides (warning: 107 Mo !)

- Week 17 (week of January 28): Final exam (Friday, February 1st, Amphi Arago 14:00-16:00 pm)

- Lectures on Tuesday 8:30-10 am (Amphi Cauchy) (but first lecture on
**Thursdsay**, September 20 8:30-10 am) - Tutorials on Monday 10:15-11:45 or 12:45-14:15.

Grading:

- Homework assignments: 50 % (your lowest two homework scores will be dropped)
- Exam grade: 50 %. If M is your grade on the midterm exam and F is your grade on the final exam, your exam grade will be max(F,(F+M)/2).

*No books, notes, calculators or collaboration are permitted at any exam.*

N.B. In the exam grade is greater than 20, the surplus is added to the homework assignment grade.