Discrete Mathematics I

Office hours: by appointment. I will be in Friday 6 January 10:30 - 12:30, in S125 (Malostranské nám. 25, 1st floor).

Exercises

Lectures for the course Discrete Mathematics I in the winter semester of 2016 are given by Hans Raj Tiwary.

Exercises provide practice and consolidation of lecture material and the textbooks:

Jiří Matoušek and Jaroslav Nešetřil, Invitation to Discrete Mathematics, 2nd ed.

Jiří Matoušek, Notes on Probability.

Weekly exercises are not formally graded, but students will be asked to present some of their solutions in the tutorial class the week after receiving the exercise sheet. Performance on exercises will not directly affect your grade for the main course. However, if you intend to be graded for the main course, you require a "pass" for the exercises. A pass/fail grade for the exercises will be decided based on regular attendence, participation in presentation of solutions to exercises, and satisfactory performance on the test at the end of the semester.

Exercise classes are held at 9:00 on Thursday mornings (excepting holidays) in Room S11 in the MFF building at Mala Strana (lectures are 10:40 on Mondays).

Supplementary textbooks:

Norman Biggs, Discrete Mathematics, Oxford, 1989 (also contains material on groups,rings and fields suitable for later in the Linear Algebra I course).

G. Grimmett and D. Welsh, Probability: an Introduction, 2nd ed., 2014. Chapters 1 and 2.

Exercise sheets

3/ 6 October

Solutions. In class we looked at mathematical induction, questions 1 and 3.

A basic introduction to induction (from NRICH)

Notes on mathematical induction (from UC San Diego).

10/ 13 October

Functions, surjections, injections, bijections

Selected solutions

17/ 20 October

In class looked at question 1 in detail, and 3(a), (b). Functions from n-element set to m-element set. Ordered partition of a set into m subsets. Inverse images of a function to m-element set correspond to ordered partition of domain into an m-tuple of subsets (some empty if not a surjection). Binomial coefficients and Pascal's recurrence. Equal cardinality by establishing bijection between sets.

Solutions

24 October/ 1 November (no class 27 October).

Solutions

31 October/ 3 November

Solutions

10 November

Solutions

17 November

No class (Struggle for Freedom and Democracy Day).

Solutions

24 November

Selected solutions

1 December

Solutions

8 December

Solutions

15 December

Solutions

12 January

TEST on definitions and basic examples in the following topics:

Induction, Counting and Binomial coefficients, Sets, Functions, Relations, Partial orders, Inclusion-Exclusion, Probability, Graphs, Trees. (There is an option to take this test on Monday 9 January, 2pm to 3:30pm (come to room S125 and we shall find a corridor location for you to sit the test).