

Discrete Mathematics (4702301/02)
Winter Term 2018/2019
Detailed information about this course in Czech language is available on the web page of subject guarantor
doc. Mgr. Petr Kovář, Ph.D.,
Hours of Instruction
 Day  Time  Room 
Lecture  Monday  10:45  12:15  EB126 
Discussion  Monday  12:30  14:00  EB126 
      
Office hours
Day  Time  Room 
Tuesday  9:00  10:30  EA 533 
     
Also at different times, after previous peremail agreement.
tereza.kovarova<at>vsb.cz 
Content of the Course
Lectures
 Introductory lecture (course organization).
Lecture on: Sets and set operations, cartesian product, power set, sequences, their sums and products.
dim_lecture01.pdf
 Arrangements and selections: Lecture is on simple arrangements and selections as permutations, kpermutations and kcombinations.
Further arrangements and selections with repetitions are defined: permutations with repetitions, combinations with repetitions and kpermutations with repetitions.
We state two basic counting principles  the addition principle and the multiplication principle. ALso we mention the method of double counting,
all complemented with simple examples.
dim_lecture02.pdf
 Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events,
conditional probability, random variable, expected values.
dim_lecture03.pdf
 Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
dim_lecture04.pdf
 Lecture on relations: definition of the term relation, properties of relations, equivalence relation, partial ordering relation, mappings, permutations.
dim_lecture05.pdf
 Inclusion exclusion principle.
dim_lecture06.pdf
 Algorithms for discrete structures.
dim_lecture07.pdf
 First lecture on graph theory, graphs, parity principle, HavelHakimi theorem, graph isomorphisms, implementation of graphs.
dim_lecture08.pdf
 Connectivity of graphs, searching through a graph, higher degrees of connectivity.
dim_lecture09.pdf
 Eulerian and hamiltonian graphs.
dim_lecture10.pdf
 Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
dim_lecture11.pdf
 Basic properties of trees, rooted trees, isomorphism of trees.
dim_lecture12.pdf
 Graph colorings, drawing a graph in a plane (planar graphs).
dim_lecture13.pdf
 Flow in a network.
dim_lecture14.pdf
Discussions
Writing of materials in English language is in process.
If you find mistakes in text or results of exercises I would appreciate if you let me know (preferably per email).
 Exercises 01 (on sums, products, sets operations)
DIM_ex_01.pdf
 Worksheet 02 (on selections and arrangements without repetition)
DIM_ws2018_02.pdf
Exercises 02 (on selections and arrangements without repetition)
DIM_ex_02.pdf
 Worksheet 03 (on selections and arrangements with repetition and on compound arrangements and selections)
DIM_ws2018_03.pdf
Exercises 03 (on selections and arrangements with repetition and on compound arrangements and selections)
DIM_ex_03.pdf
 Worksheet 04 (on discrete probability )
DIM_ws2018_04.pdf
Exercises 04 (on discrete probability, independent events, expected values)
DIM_ex_04_05.pdf
 Worksheet 05 (independent events, expected values)
DIM_ws2018_05.pdf
Exercises 05 (on discrete probability, independent events, expected values)
DIM_ex_04_05.pdf
 Worksheet 06 (Proofs by Mathematical induction)
DIM_ws2018_06.pdf
Exercises 06 (on proofs and proofs by Mathematical Induction)
DIM_ex_06.pdf
 Worksheet 07 (on relations)
DIM_ws2018_07.pdf
Exercises 07 (on relations)
DIM_ex_07.pdf
 Worksheet 08 (Permutations and InclusionEexclusion principle)
DIM_ws2018_08.pdf
Exercises 07 (on relations)
DIM_ex_08.pdf








Time Line of the Course for Winter Term 2019
Lectures and Discussions  organized in 14 weeks of the semester
#  Date: dd.mm.  Content  Notes 
1.  17.09.  Lecture  Introductory lecture  
Discussion  sums, products, sets operations  
2.  24.09.  Lecture  selections and arrangements without and with repetition  
Discussion  selections and arrangements without repetition  
3.  01.10.  Lecture  Discrete Probability  
Discussion  Arrangements and selections with repetition  
4.  08.10.  Lecture  Probability  Expected values, Proofs  basics of math logic  
Discussion  Selections with repetition + Probability computations  First test  3pts
Selections, arrangements without repetition 
5.  15.10.  Lecture  Proofs  Mathematical induction, Dirichlet's principle  
Discussion  Probability computations,
Expected values  Second test  2pts
Selections, arrangements with repetition 
6.  22.10.  Lecture  Relations + glimpse to Permutations  
Discussion  Proofs  Mathematical induction, by computation  Third test  3pts
Probability computations, Expected values, Independent events 
7.  29.10.  Lecture  Permutations and InclusionExclusion principle
 Examples on Permutations and InclusionExclusion principle, 
Discussion  Relations and their properties  Fourth test  2pts
on proofs by Math. Induction 
8.  05.11.  Lecture  Introduction to Graph theory  
Discussion  InclusionExclusion and Dirichlets principls + Graphs  Fifth test  3pts
on properties of relations and mappings 
9.  12.11.  Lecture   
Discussion   Sixth test 
10.  19.11.  Lecture   
Discussion   Sevnth test 
11.  26.11.  Lecture   
Discussion   Eight test 
12.  03.12.  Lecture   
Discussion   Ninth test 
13.  10.12.  Lecture   
Discussion   Tenth test 
14.  17.12.  Lecture   
Discussion   
Sample exams
Recommended texts
 Discrete Mathematics and Its Applications, 7th Edition by Kenneth H. Rosen
 Applied Combinatorics, 6th Edition by Alan Tucker
 Introduction to Graph Theory, 2nd Edition by Douglas B. West
Grading scales
gradingscales.pdf (according to overall course score)

