Daniel Gromada

Discrete Mathematics and Graphs

News

Midterm retake will take place on 16 January at 9:15 in room 51 (parallel to the first exam).

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.

 

I will try to write down the script for the lecture that will be available here.

Outline

  1. [25. 9.] Introduction, Propositional logic
    Reading: [DP] §2.1, 2.2, [De] §1, Homework A
  2. [27. 9.] Exercises, Sets
    Reading: [DP] §4.1--4.3, Exercise sheet, Homework B solution
  3. [2. 10.] Quantifiers, Proof by induction
    Reading: [DP] §2.3, 5.2, [De] §2, Homework A
  4. [4. 10.] Exercises, Introduction to number theory
    Exercise sheet, Homework B solution
  5. [online!] Euclidean algorithm
    Video lecture Reading: [DP] §3.2, [De] §4.1, Homework A
  6. [11. 10.] Exercises, Positional number systems
    Exercise sheet, Homework B solution
  7. [16. 10.] Congruence
    Reading: [De] §4.2, Homework A
  8. [18. 10.] Exercises
    Exercise sheet, Homework B solution
  9. [23. 10.] Primes, RSA algorithm
    [De] §4.1, §4.2, Homework A
  10. [25. 10.] Exercises, Relations
    Exercise sheet, Homework B solution
  11. [30. 10.] Relations
    Reading: [DP] §7.1, 7.3, 7.4 [De] §3.3, Homework A
  12. [1. 11.] Exercises
    Exercise sheet, Homework B solution
  13. [6. 11.] Inroduction to abstract algebra
    Reading: [De] §5.1, § 5.2, Homework A
  14. [8. 11.] Exercises, Zn×
    Exercise sheet, Homework B solution
  15. [13. 11.] Subgroups
    Reading: [De] §5.3, Homework A
  16. [15. 11.] Exercises
    Exercise sheet, Homework B solution
  17. [20. 11.] Dean's day
  18. [22. 11.] Exercises -- recap before midterm
    Sample midterm test
  19. [27. 11.] Structures with two operations
    Reading: [De] §6, Homework A
  20. [29. 11.] Midterm test
  21. [4. 12.] Cominatorics
    Reading: [De] §8, Homework A
  22. [6. 12.] Exercises
    Exercise sheet, Homework B solution
  23. [11. 12.] Graphs, connectivity
    Reading: [De] §7.1, Homework A
  24. [13. 12.] Trees, exercises
    Reading: [De] §7.2
    Exercise sheet, Homework B solution
  25. [18. 12.] Spanning trees, rooted trees, directed acyclic graphs, strong connectivity
    Reading: [De] §7.3, §7.4, §7.5, §7.6, Homework A
  26. [20. 12.] Exercises
    Reading:
    Exercise sheet, Homework B solution
  27. [8. 1.] Euler graphs, overview of graph theory
    Reading: [De] §7.7
  28. [10. 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

Homework

Every week, there will be two kinds of homework assigned.
  • On Monday, I will assign voluntary homework A. This will be some theoretical question based on the lecture. The homework will be due to Wednesday (i.e. 2 days). Correct answers are awarded extra points to the exam. You should try to solve it on your own and be able to present the solution at the blackboard if asked.
  • On Wednesday, I will assign compulsory homerwork B. You have to do this homework to get the assessment/zápočet. The homework will be due to next Wednesday (i.e. 1 week). Correctness is not evaluated, everything is allowed, this is only to check that you are making some effort.

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
  • Attendance is not required

Midterm test

The midterm test will take place around the ninth week of semester (will be specified later). The time limit is 50 minutes. Maximal gain 20 points, limit to pass 10 points. Check the sample test.

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. A bonus of (gain from the midterm) PLUS ( The gain from homework A) MINUS (10 points needed for the zápočet) is added to the gain of the written exam.

Here is a sample exam

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 + midterm + bonus). You can gain at most 15 points from the oral exam. The oral part will always take place on the same day afternoon.

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.