Homepage
Výuka
Publikace
 

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

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

Office hours

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

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


Content of the Course

Lectures

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

  1. Exercises 01 (on sums, products, sets operations)
    DIM_ex_01.pdf
  2. Worksheet 02 (on selections and arrangements without repetition)
    DIM_ws2018_02.pdf
    Exercises 02 (on selections and arrangements without repetition)
    DIM_ex_02.pdf
  3. 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
  4. Worksheet 04 (on discrete probability )
    DIM_ws2018_04.pdf
    Exercises 04 (on discrete probability, independent events, expected values)
    DIM_ex_04_05.pdf
  5. Worksheet 05 (independent events, expected values)
    DIM_ws2018_05.pdf
    Exercises 05 (on discrete probability, independent events, expected values)
    DIM_ex_04_05.pdf
  6. Worksheet 06 (Proofs by Mathematical induction)
    DIM_ws2018_06.pdf
    Exercises 06 (On Proofs and Proofs by Mathematical Induction)
    DIM_ex_06.pdf
  7. Exercises 07 (On Relations)
    DIM_ex_07.pdf
  8. Exercises 08 (Permutations and Inclusion-Exclusion principle)
    DIM_ex_08.pdf
  9. Exercises 09 (Basic Classes of Graphs, Parity Principle, Havel-Hakimi Theorem, Subgraphs)
    DIM_ex_09.pdf
  10. Exercises 10 (Subgraphs, Isomorphisms of Graphs)
    DIM_ex_10.pdf
  11. Exercises 11 (Connectivity of Graphs, Distances in Graphs, Eulerian Graphs)
    DIM_ex_11.pdf
  12. 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.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.
Exam-sample1.pdf
Exam-sample2.pdf

Final-Exam Dates

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

#Date-dd.mm.RoomTime
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