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).
ExercisesLectures 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 sheets3/ 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).