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
|Lecture||Monday||10:45 - 12:15||EB126
|Discussion||Monday||12:30 - 14:00||EB126
|Tuesday||9:00 - 10:30||EA 533
| -- || -- || --
Also at different times, after previous per-email agreement.
Content of the Course
- Introductory lecture (course organization).
Lecture on: Sets and set operations, cartesian product, power set, sequences, their sums and products.
- 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.
- Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events,
conditional probability, random variable, expected values.
- Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
- Lecture on relations: definition of the term relation, properties of relations, equivalence relation, partial ordering relation, mappings, permutations.
- Inclusion exclusion principle.
- Algorithms for discrete structures.
- First lecture on graph theory, graphs, parity principle, Havel-Hakimi theorem, graph isomorphisms, implementation of graphs.
- Connectivity of graphs, searching through a graph, higher degrees of connectivity.
- Eulerian and hamiltonian graphs.
- Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
- Basic properties of trees, rooted trees, isomorphism of trees.
- Graph colorings, drawing a graph in a plane (planar graphs).
- 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).
- Exercises 01 (on sums, products, sets operations)
- Worksheet 02 (on selections and arrangements without repetition)
Exercises 02 (on selections and arrangements without repetition)
- 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)
- Worksheet 04 (on discrete probability )
Exercises 04 (on discrete probability, independent events, expected values)
- Worksheet 05 (independent events, expected values)
Exercises 05 (on discrete probability, independent events, expected values)
- Worksheet 06 (Proofs by Mathematical induction)
Exercises 06 (On Proofs and Proofs by Mathematical Induction)
- Exercises 07 (On Relations)
- Exercises 08 (Permutations and Inclusion-Exclusion principle)
- Exercises 09 (Basic Classes of Graphs, Parity Principle, Havel-Hakimi Theorem, Subgraphs)
- Exercises 10 (Subgraphs, Isomorphisms of Graphs)
- Exercises 11 (Connectivity of Graphs, Distances in Graphs, Eulerian Graphs)
- 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
|Discussion||sums, products, sets operations||
|2.||24.09.||Lecture||selections and arrangements without and with repetition||
|Discussion||selections and arrangements without repetition||
|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, |
|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 Inclusion-Exclusion principle
||Examples on Permutations and Inclusion-Exclusion principle,
|Discussion||Relations and their properties||Fourth test - 2pts
on proofs by Math. Induction
|8.||05.11.||Lecture||Introduction to Graph theory||
|Discussion||Inclusion-Exclusion 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, Havel-Hakimi theorem, subgraphs||Sixth test - 2pts
|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 Havel-Hakimi 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 worked-out 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
You may check two versions of a final exam test from the last year.
You need to sign up in IS EDISON for the opened exam term.
|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
- 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.pdf (according to overall course score)