Discrete Mathematics (470-2301/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

LectureThuersday12:30 - 14:00EB226
DiscussionThuersday14:15 - 15:45EB230

Office hours

Tuesday9:00 - 10:30EA 533
-- -- --

Also at different times, after previous per-email agreement.

Content and the Time Line of the Course


  1. (21.09.)
    Introductory lecture (First chapter): course information, set operations, cartesian product, power set, sequences, their sums and products,
  2. (28.09)
    Holiday - classes are canceled
  3. (5.10.)
    Second chapter is on simple arrangements and selections as permutations, k-permutations and combinations. Also we define arrangements and selections with repetitions as permutations with repetitions, combinations with repetitions and k-permutations 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.
  4. (12.10.)
    Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events, conditional probability, random variable, expected values.
  5. (19.10.)
    Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
  6. (26.10.)
    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)
  7. (2.11.)
    Completion of the lecture on relations + Inclusion exclusion principle
    For reading the chapter on algorithms for discrete structures is available here. dim_lecture07.pdf
    First lecture on graph theory, graphs, parity principle, Havel-Hakimi theorem, graph isomorphisms, implementation of graphs.
  8. (9.11.)
    Connectivity of graphs, searching through a graph, higher degrees of connectivity.
  9. (16.11.) lectures and discussions are canceled by the university president(rector) due to official ceremony event (vědecká rada)
  10. (23.11.)
    Eulerian and hamiltonian graphs.
    Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
  11. (30.11.)
    Distances in a weighted graph, Dijkstra's algorithm.
    Basic properties of trees.
  12. (7.12.)
    Rooted trees, isomorphism of trees.
    Graph colorings.
  13. (14.12.)
    Drawing a graph in a plane (planar graphs).
    Flow in a network.
  14. (21.12.)
    Finishing previous topics and review.


  1. (21.09.)
    Set operations, Cartesian product, Power set, Sequences - their sums and products, Ceiling function and Floor function.
    Worksheet 01 (DIM_ws_01.pdf )

  2. (28.09.)
    Holiday - classes are canceled

  3. (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 )

  4. (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)

  5. (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)

  6. ( 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)

  7. (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)

  8. (9.11.)
    Test 5 + 6
    Exercises for the 7-th test (2pts) on "relations"
    dim_zapoctova_pisemka06.pdf (in Czech), dim_exercises_test06_en.pdf (in English)
    No next worksheets are available.

  9. (16.11.)
    lectures and discussions are canceled by the university president(rector) due to official ceremony event (vědecká rada)

  10. (23.11.)
    Test 7
    Exercises for the 8th test 2pts) on "Parity principle, degree sequence of a graph, Havel-Hakimi theorem"
    dim_zapoctova_pisemka07.pdf (in Czech), dim_exercises_test07+08_en.pdf (in English)

  11. (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)

  12. (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)

  13. (14.12.)
    Test 10
    Exercises for an extra 11-th 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.

  14. (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.

Grading scales according to overall course score.

  Upraveno: 22.01.2018