

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
 Exercises 07 (On Relations)
DIM_ex_07.pdf
 Exercises 08 (Permutations and InclusionExclusion principle)
DIM_ex_08.pdf
 Exercises 09 (Basic Classes of Graphs, Parity Principle, HavelHakimi Theorem, Subgraphs)
DIM_ex_09.pdf
 Exercises 10 (Subgraphs, Isomorphisms of Graphs)
DIM_ex_10.pdf
 Exercises 11 (Connectivity of Graphs, Distances in Graphs, Eulerian Graphs)
DIM_ex_11.pdf
 Exercises 12 (Binary Codes of Rooted Trees)
DIM_ex_12.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  Graph isomorphism, Implementation of graphs, Connectivity  
Discussion  Parity principle,degree sequences, HavelHakimi theorem, subgraphs  Sixth test  2pts
on permutations 
10.  19.11.  Lecture  Searching in graphs, Higher degrees of connectivity, Eulerian and Hamiltonian graphs  
Discussion  Graph isomorphism, Connectivity of graphs  Sevnth test  3pts
on Parity Principle and HavelHakimi theorem 
11.  26.11.  Lecture  Hamiltonian Graphs, Measuring Distances in Graphs,
Algorithms to Find Distances in Unweighted Graphs  
Discussion  Connectivity of Graphs  Eight test  2pts
on Graph Isomorphisms 
12.  03.12.  Lecture  Dijkstra's Algorithm, Trees, Spanning Tree Algorithms  
Discussion  Dijkstra's Algorithm and Binary Trees  Ninth test  3pts
on Connectivity and Higher Degrees of Connectivity of Graphs
th. q. on Eulerian or Hamiltonian Graphs 
13.  10.12.  Lecture  Graph Colorings and Planar Graphs  The deadline to hand workedout projects. 
Discussion  Spanning Tree Algorithms, Coloring of graphs and Planar Graphs  Tenth test  2pts
on Binary Trees 
14.  17.12.  Lecture  Flow in a Network  Exams Information 
Discussion  Flow in a Network  possibility of substituting tests 
Sample exams
You may check two versions of a final exam test from the last year.
Examsample1.pdf
Examsample2.pdf
FinalExam Dates
You need to sign up in IS EDISON for the opened exam term.
#  Datedd.mm.  Room  Time 
Early exam  Friday 21.12.  EB126  9:30 AM 
1.  Tuesday 8.1.  EC1  9:00 
2.  Tuesday 15.1.  EC2  9:00 
3.  Wednesday 23.1.  EC2  9:00 
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)

