Discrete Mathematics and Graphs

Content:

Lectures:

  1. Foundation of Propositional logic, Boolean calculus.
  2. Foundation of Predicate logic, quantifiers, interpretation.
  3. Sets, cardinality of sets, countable and uncountable sets.
  4. Binary relations on a set, equivalence relation, partial order.
  5. Integers, Euclid (extended) algorithms.
  6. Relation modulo n, congruence classes Zn and operations on Zn.
  7. Algebraic operations, semigroups, groups.
  8. Sets together with two binary operations, Boolean algebras.
  9. Rings of congruence classes Zn, fields Zp.
  10. Undirected graphs, trees and spanning trees.
  11. Directed graphs, strong connectivity and acyclic graphs.
  12. Euler graphs and Hamiltonian graphs, coloring.
  13. Combinatorics.
  14. Reserve.

Tutorials:

  1. Foundation of Propositional logic, Boolean calculus.
  2. Foundation of Predicate logic, quantifiers, interpretation.
  3. Sets, cardinality of sets, countable and uncountable sets.
  4. Binary relations on a set, equivalence relation, partial order.
  5. Integers, Euclid (extended) algorithms.
  6. Relation modulo n, congruence classes Zn and operations on Zn.
  7. Algebraic operations, semigroups, groups.
  8. Sets together with two binary operations, Boolean algebras.
  9. Rings of congruence classes Zn, fields Zp.
  10. Undirected graphs, trees and spanning trees.
  11. Directed graphs, strong connectivity and acyclic graphs.
  12. Euler graphs and Hamiltonian graphs, coloring.
  13. Combinatorics.
  14. Reserve.

References:

Assesment (zapocet):

Requirements: Active participation in labs and scoring at least 8 points from midterm.

Midterm: Midterm will be written during the labs in 9th week of semester. Midterm test consists of three parts: 1. logic - propositional and predicate logic (gain max. 6 points); 2. binary relations (gain max. 6 points); and 3. solving an equation in rezidue classes (gain max. 8 points). You can obtain max. 20 points, obligatory for assesment is 8 points.

Final exam:

A necessary condition is to obtain assesment (zapocet).

Final exam contains two parts - a written part (obligatory) and an oral part (not obligatory). Written test will consist of 6 problems, max. gain 80 points, with 105 minutes allowed for solving them.

Written test:

Problem 1: Negation of a sentence of predicate logic.

Problem 2: Binary relations on a set; properties of a binary relation (reflexivity, symmetry, antisymmetry, transitivity, equivalence relation, partial order), or a composition of relations.

Problem 3: Binary operations: For a given binary operation o on a set A decide whether (A,o) is a semigroup, a monoid, or a group. Furhter questions can be put: An equality which does not have a solution, a subsemigroup (a submonoid, a subgroup).

Problem 4: Structures Zn and their subgroup of invertible elements. Order of some/all of its elements. Solving a parametric linear equation in Zn.

Problem 5: Graphs: It is necessary to understand basic notions, be able to give small examples with prescribed properties, and use some of the facts/procedures that were shown at the lecture.

Problem 6: Combinatorics: A word problem concerning enumerative combinatorics.

Oral part:

The oral part will look at theory and can bring max. 20 points; can be taken by those who gained at least 40 points in the written part.

Grading:

The resulting grade is based on three inputs. S is the number of points brought from midterm calculated as follows: if the gain M from midterm taken for the first time is at least 10, then S = M - 10 (from re-taken midterm the points are not calculated); P is the number of points from the written part; and U is the number of points from the oral part.

1) If a student gained less than 40 points from the written test, the student failed the exam.

2) If a student gained 40 or more points from the written test, then the student can take an oral exam. The grade is then determined by the total P + S + U and the following key:

sum grade
50-59E (sufficient)
60-69D (satisfactory)
70-79C (good)
80-89B (very good)
> 89A (excellent)