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).
for the course Discrete Mathematics I in the winter semester of 2016
are given by Hans
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
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).
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 sheets3/ 6 October
. 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
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.
24 October/ 1 November
(no class 27 October).
31 October/ 3 November
No class (Struggle for Freedom and Democracy Day).
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).