Daniel Gromada

Discrete Mathematics and Graphs

Content

This subject covers a variety of different topics
  • Logic,
  • Set theory,
  • Number theory,
  • Abstract algebra
  • Combinatorics,
  • Graph theory.
But most importantly, it should be taken just as an Introduction to mathematics. More detailed outline of the lectures is going to be updated below.

Outline

  1. [19. 9.] Introduction, Propositional logic
    Reading: [DP] §2.1, 2.2, [De] §1
  2. [21. 9.] Exercises, Quantifiers
    Reading: [DP] §2.3, [De] §2, Exercise sheet, Homework solution
  3. [26. 9.] Exercises, Sets
    Reading: [DP] §4.1--4.3, Exercise sheet, Homework solution
  4. [28. 9.] Holiday 🥳
    Saint Wenceslas, do not let us or our descendants perish.
  5. [3. 10.] Euclidean algorithm
    Reading: [DP] §3.2, [De] §4.1
  6. [5. 10.] Exercises, Proof by induction
    Reading: [DP] §5.2, Exercise sheet, Homework solution
  7. [10. 10.] Congruence
    Reading: [De] §4.2
  8. [12. 10.] Exercises
    Exercise sheet, Homework solution
  9. [17. 10.] Positional number systems, primes
    Reading: PNS: notes, primes: [De] §4.1, §4.2
  10. [19. 10.] Exercises, RSA algorithm
    Reading: notes, Exercise sheet, Homework solution
  11. [24. 10.] Relations
    Reading: [DP] §7.1, 7.3, 7.4 [De] §3.3
  12. [26. 10.] Exercises, Relations
    Exercise sheet, Homework solution
  13. [31. 10.] Inroduction to abstract algebra
    Reading: [De] §5.1, § 5.2
  14. [2. 11.] Exercises, Zn×
    Exercise sheet, Homework solution
  15. [7. 11.] Subgroups
    Reading: [De] §5.3
  16. [9. 11.] Exercises
    Exercise sheet, Homework solution
  17. [14. 11.] Structures with two operations
    Reading: [De] §6
  18. [16. 11. online!] Exercises This lecture will take place online via MS Teams!
    Exercise sheet: Sample midterm test
    Exercise session: video, blackboard
    There is no homework. You should learn for the test.
  19. [21. 11.] Cominatorics
    Reading: [De] §8
  20. [23. 11.] Midterm test
    Homework solution
  21. [28. 11.] Cancelled
  22. [30. 11.] Exercises
    Exercise sheet, Homework solution
  23. [5. 12.] Graphs, connectivity
    Reading: [De] §7.1
  24. [7. 12.] Trees, exercises
    Reading: [De] §7.2
    Exercise sheet, Homework solution
  25. [12. 12.] Spanning trees, rooted trees, directed acyclic graphs
    Reading: [De] §7.3, §7.4, §7.5
  26. [14. 12.] Strong connectivity, exercises
    Reading: [De] §7.6
    Exercise sheet, Homework solution
  27. [9. 1.] Euler graphs, overview of graph theory
    Reading: [De] §7.7
  28. [11. 1.] Exercises, recap before exam
    Exercise sheet, also please prepare any questions you would like to ask before the exam (problems you cannot solve etc.)

References

[DP] N. Donaldson, A. Pantano An Introduction to Abstract Mathematics Lecture notes available online

[De] M. Demlová Discrete Mathematics and Graphs Lecture notes for an earlier version of this course. 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13,

[C] L. N. Childs: A Concrete Introduction to Higher Algebra

[J] R. Johnsonbaugh: Discrete Mathematics

Requirements

Assessment (Zápočet)

  • Solving homeworks: There will be a compulsory homework every week. You are allowed not to hand in maximally 3 homeworks. Correctness is not evaluated.
  • Passing a midterm test: see below

Midterm test

The midterm test will take place on 23 November on our lecture. The time limit is 50 minutes. Maximal gain 20 points, limit to pass 10 points. A sample test with a description of its structure avalaible here.

The retake of the midterm test will take place on 13 January at 9:15 in the room 337 (parallel to the first exam). The equirements are identical to the original test. Apart from the sample test, you can also learn from the last regular test here.

Bonus

Every time you present a problem on a blackboard, you get an extra point to your midterm and hence also to your exam. Check the exercise sheets before every exercise section if you want to present something on a blackboard. A priority will be given to those that did not present anything yet.

Exam (Zkouška)

You are allowed to sign in for an exam only if you already obtained your assessment (zápočet). The exam consists of a mandatory written part and optional oral part. The written part will be a test with maximal gain of 80 points, time limit 120 minutes. The gain from your midterm minus 10 points is then added to the gain from your exam.

Here is a sample exam (Update: I included some correct answers.)

The registration for the exam is possible via KOS.

You are allowed to take the optional oral part of the exam only if you scored at least 45 points (points from exam + what you took from the midterm). You can gain at most 15 points from the oral exam.

Finally, your grade is determined according to the following table

Points Grade
≥90 A
80--89 B
70--79 C
60--69 D
50--59 E
0--49 F
Responsible person: doc. RNDr. Martin Bohata, Ph.D.