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

LectureMonday10:45 - 12:15EB126
DiscussionMonday12:30 - 14:00EB126

Office hours

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

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

Content of the Course


  1. Introductory lecture (course organization).
    Lecture on: Sets and set operations, cartesian product, power set, sequences, their sums and products.
  2. Arrangements and selections: Lecture is on simple arrangements and selections as permutations, k-permutations and k-combinations. Further arrangements and selections with repetitions are defined: 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.
  3. Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events, conditional probability, random variable, expected values.
  4. Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
  5. Lecture on relations: definition of the term relation, properties of relations, equivalence relation, partial ordering relation, mappings, permutations.
  6. Inclusion exclusion principle.
  7. Algorithms for discrete structures.
  8. First lecture on graph theory, graphs, parity principle, Havel-Hakimi theorem, graph isomorphisms, implementation of graphs.
  9. Connectivity of graphs, searching through a graph, higher degrees of connectivity.
  10. Eulerian and hamiltonian graphs.
  11. Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
  12. Basic properties of trees, rooted trees, isomorphism of trees.
  13. Graph colorings, drawing a graph in a plane (planar graphs).
  14. Flow in a network.


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

  1. Exercises 01 (on sums, products, sets operations)
  2. Worksheet 02 (on selections and arrangements without repetition)
    Exercises 02 (on selections and arrangements without repetition)
  3. Worksheet 03 (on selections and arrangements with repetition and on compound arrangements and selections)
    Exercises 03 (on selections and arrangements with repetition and on compound arrangements and selections)
  4. Worksheet 04 (on discrete probability )
    Exercises 04 (on discrete probability, independent events, expected values)
  5. Worksheet 05 (independent events, expected values)
    Exercises 05 (on discrete probability, independent events, expected values)
  6. Worksheet 06 (Proofs by Mathematical induction)
    Exercises 06 (On Proofs and Proofs by Mathematical Induction)
  7. Exercises 07 (On Relations)
  8. Exercises 08 (Permutations and Inclusion-Exclusion principle)
  9. Exercises 09 (Basic Classes of Graphs, Parity Principle, Havel-Hakimi Theorem, Subgraphs)
  10. Exercises 10 (Subgraphs, Isomorphisms of Graphs)
  11. Exercises 11 (Connectivity of Graphs, Distances in Graphs, Eulerian Graphs)
  12. Exercises 12 (Binary Codes of Rooted Trees)

Time Line of the Course for Winter Term 2019

Lectures and Discussions - organized in 14 weeks of the semester

#Date: dd.mm.ContentNotes
1.17.09.LectureIntroductory lecture
Discussionsums, products, sets operations
2.24.09.Lectureselections and arrangements without and with repetition
Discussionselections and arrangements without repetition
3.01.10.LectureDiscrete Probability
DiscussionArrangements and selections with repetition
4.08.10.LectureProbability - Expected values, Proofs - basics of math logic
DiscussionSelections with repetition + Probability computationsFirst test - 3pts
Selections, arrangements without repetition
5.15.10.LectureProofs - Mathematical induction, Dirichlet's principle
DiscussionProbability computations,
Expected values
Second test - 2pts
Selections, arrangements with repetition
6.22.10.LectureRelations + glimpse to Permutations
DiscussionProofs - Mathematical induction, by computationThird test - 3pts
Probability computations, Expected values, Independent events
7.29.10.LecturePermutations and Inclusion-Exclusion principle Examples on Permutations and Inclusion-Exclusion principle,
DiscussionRelations and their propertiesFourth test - 2pts
on proofs by Math. Induction
8.05.11.LectureIntroduction to Graph theory
DiscussionInclusion-Exclusion and Dirichlets principls + GraphsFifth test - 3pts
on properties of relations and mappings
9.12.11.LectureGraph isomorphism, Implementation of graphs, Connectivity
DiscussionParity principle,degree sequences, Havel-Hakimi theorem, subgraphsSixth test - 2pts
on permutations
10.19.11.LectureSearching in graphs, Higher degrees of connectivity, Eulerian and Hamiltonian graphs
DiscussionGraph isomorphism, Connectivity of graphsSevnth test - 3pts
on Parity Principle and Havel-Hakimi theorem
11.26.11.LectureHamiltonian Graphs, Measuring Distances in Graphs,
Algorithms to Find Distances in Unweighted Graphs
DiscussionConnectivity of GraphsEight test - 2pts
on Graph Isomorphisms
12.03.12.LectureDijkstra's Algorithm, Trees, Spanning Tree Algorithms
DiscussionDijkstra's Algorithm and Binary TreesNinth test - 3pts
on Connectivity and Higher Degrees of Connectivity of Graphs
th. q. on Eulerian or Hamiltonian Graphs
13.10.12.LectureGraph Colorings and Planar Graphs The deadline to hand worked-out projects.
DiscussionSpanning Tree Algorithms, Coloring of graphs and Planar GraphsTenth test - 2pts
on Binary Trees
14.17.12.LectureFlow in a NetworkExams Information
DiscussionFlow in a Networkpossibility of substituting tests

Sample exams

You may check two versions of a final exam test from the last year.

Final-Exam Dates

You need to sign up in IS EDISON for the opened exam term.

Early examFriday 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, 7-th Edition by Kenneth H. Rosen
  • Applied Combinatorics, 6-th Edition by Alan Tucker
  • Introduction to Graph Theory, 2-nd Edition by Douglas B. West

Grading scales

grading-scales.pdf (according to overall course score)

  Upraveno: 09.02.2019