

Discrete Mathematics (4702301/02)
Winter Term 2017/2018
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  Thuersday  12:30  14:00  EB226 
Discussion  Thuersday  14:15  15:45  EB230 
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 and the Time Line of the Course
Lectures
 (21.09.)
dim_lecture01.pdf
Introductory lecture (First chapter): course information, set operations, cartesian product, power set, sequences, their sums and products,
 (28.09)
Holiday  classes are canceled
 (5.10.)
dim_lecture02.pdf
Second chapter is on simple arrangements and selections as permutations, kpermutations and combinations. Also we define arrangements and selections with repetitions as 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.
 (12.10.)
dim_lecture03.pdf
Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events, conditional probability, random variable, expected values.
 (19.10.)
dim_lecture04.pdf
Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
 (26.10.)
dim_lecture05.pdf
Lecture on relations: definition of the term relation, properties of relations, equivalence relation, partial ordering relation, mappings, permutations
Also we will finish the topic of proofs including exercises.
Worksheet 06  Proofs by Mathematical Induction, by counting (DIM_ws_06.pdf)
 (2.11.)
dim_lecture06.pdf
Completion of the lecture on relations + Inclusion exclusion principle
For reading the chapter on algorithms for discrete structures is available here. dim_lecture07.pdf
dim_lecture08.pdf
First lecture on graph theory, graphs, parity principle, HavelHakimi theorem, graph isomorphisms, implementation of graphs.
 (9.11.)
dim_lecture09.pdf
Connectivity of graphs, searching through a graph, higher degrees of connectivity.
 (16.11.) lectures and discussions are canceled by the university president(rector) due to official ceremony event (vědecká rada)
 (23.11.)
dim_lecture10.pdf
Eulerian and hamiltonian graphs.
dim_lecture11.pdf
Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
 (30.11.)
dim_lecture11.pdf
Distances in a weighted graph, Dijkstra's algorithm.
dim_lecture12.pdf
Basic properties of trees.
 (7.12.)
dim_lecture12.pdf
Rooted trees, isomorphism of trees.
dim_lecture13.pdf
Graph colorings.
 (14.12.)
dim_lecture13.pdf
Drawing a graph in a plane (planar graphs).
dim_lecture14.pdf
Flow in a network.
 (21.12.)
Finishing previous topics and review.
Discussions
 (21.09.)
Set operations, Cartesian product, Power set, Sequences  their sums and products, Ceiling function and Floor function.
Worksheet 01 (DIM_ws_01.pdf )
 (28.09.)
Holiday  classes are canceled
 (5.10)
Exercises for the first test on chapter 01 (2pts),
dim_zapoctova_pisemka01.pdf (in Czech),
dim_exercises_test01_en.pdf (in English)
Simple and also complex arrangements and selections without repetitions.
Worksheet 02 (DIM_ws_02.pdf )
 (12.10.)
Exercises for the second test on chapter 02  selections and arrangements without repetition + theoretical question on lecture03  probability (3pts)
dim_zapoctova_pisemka02.pdf (in Czech),
dim_exercises_test02_en.pdf (in English)
Worksheet 03 (DIM_ws_03.pdf)
 (19.10.)
Exercises for the third test on chapter 02  selections and arrangements with repetition (2pts)
dim_zapoctova_pisemka03.pdf (in Czech),
dim_exercises_test03_en.pdf (in English)
Worksheet 04 (DIM_ws_04.pdf)
 ( 26.10.)
Test 3
Exercises for the fourth test on chapter 03  uniform probability + theoretical question on the lecture04  proofs (3pts)
dim_zapoctova_pisemka04.pdf (in Czech),
dim_exercises_test04_en.pdf (in English)
Worksheet 05  independent events, expected values (DIM_ws_05.pdf)
Worksheet 06  Proofs by Mathematical Induction, by counting (DIM_ws_06.pdf)
 (2.11.)
Test 4
Exercises for the fifth and sixth test + theoretical question on the lecture05  relations (5pts)
dim_zapoctova_pisemka05.pdf (in Czech),
dim_exercises_test05_en.pdf (in English), proofs by Mathematical induction
dim_zapoctova_pisemka06.pdf (in Czech), na test č.6 stačí pouze příklady na permutace,
dim_exercises_test07+08_en.pdf (in English), only problem on permutations will be on the 6th test
Worksheet 07  Relations, Permutations (DIM_ws_07.pdf)
 (9.11.)
Test 5 + 6
Exercises for the 7th test (2pts) on "relations"
dim_zapoctova_pisemka06.pdf (in Czech),
dim_exercises_test06_en.pdf (in English)
No next worksheets are available.
 (16.11.)
lectures and discussions are canceled by the university president(rector) due to official ceremony event (vědecká rada)
 (23.11.)
Test 7
Exercises for the 8th test 2pts) on "Parity principle, degree sequence of a graph, HavelHakimi theorem"
dim_zapoctova_pisemka07.pdf (in Czech),
dim_exercises_test07+08_en.pdf (in English)
 (30.11.)
Test 8
Exercises for the 9th test (3pts) on "isomorphisms of graphs" + theoretical question (Eulerian and Hamiltonian graphs).
dim_zapoctova_pisemka08.pdf (in Czech),
dim_exercises_test09_en.pdf (in English)
 (7.12.)
Test 9
Exercises for the 10th test (3pts) on "connectivity of graphs" + theoretical question on "distances in graphs".
dim_zapoctova_pisemka09.pdf (in Czech),
dim_exercises_test10_en.pdf (in English)
 (14.12.)
Test 10
Exercises for an extra 11th test are so far available only in Czech language.
dim_zapoctova_pisemka_tema_13_dijkstra_kostry.pdf (in Czech),
dim_zapoctova_pisemka_tema_14_stromy.df (in Czech)
Discussion topics: Dijkstra's algorithm, Rooted trees, Minimum spanning tree algorithms.
 (21.12.)
Test 11
Discussion topics: Planar graphs and coloring of graphs
Sample exam
You may check one version of the final exam assignments from previous years.
sampleexamen.pdf.
Grading scales according to overall course score.
gradingscales.pdf.

