Discrete Mathematics 1

Data is displayed for academic year: 2023./2024.

Laboratory exercises

Course Description

Homogeneous linear recursive relations. Non-homogeneous recursive relations. Basic notions from graph theory. Connectivity. Optimization algorithms on graphs. Trees. Planarity. Graph colourings. Directed graphs. Graph matchings.

Study Programmes

University undergraduate
[FER3-EN] Computing - study
(3. semester)

Learning Outcomes

  1. To solve homogeneous and non-homogeneous linear recursion.
  2. Apply the recursive way of thinking on the appropriate combinatorial problems.
  3. Describe and manipulate with basic notions from graph theory.
  4. Describe and solve appropriate engineering problems in terms of graph theory.
  5. Solve problems algorithmically using computers.

Forms of Teaching


4 hours of lectures a week. The lecturer is going to follow the lecture materials.

Independent assignments

During the semester 3 software excercises will be given to be solved by the students individually and to be shown in the framework of laboratory excercises.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Laboratory Exercises 0 % 15 % 0 % 15 %
Homeworks 0 % 5 % 0 % 5 %
Mid Term Exam: Written 0 % 40 % 0 %
Final Exam: Written 0 % 40 %
Exam: Written 0 % 80 %

Week by Week Schedule

  1. Fibonacci's sequence, Homogeneous recursive relations
  2. Homogeneous recursive relations
  3. Non-homogeneous recursive relations
  4. Notion of a graph; Main definitions and examples; Graph isomorphism
  5. Connectivity; Paths; Eulerian and hamiltonian graphs, Optimization algorithms; Shortest path problem; Chinese postman problem; Travelling salesman problem
  6. Different characterizations of trees
  7. Labelled trees; Prüfer code, Minimum spanning tree; Algorithms
  8. Midterm exam
  9. Kuratowski's theorem, Euler's formula
  10. Dual graphs, Planarity testing algorithms
  11. Vertex colourings; Brooks' theorem, Edge colourings
  12. Face colourings of planar graphs; Four colour theorem
  13. Notion of a digraph; Connectivity and strong connectivity, Critical path problem; Algorithms, Tournaments
  14. Marriage problem, Hall's theorem, Transversals, Application to latin squares
  15. Final exam


(.), D. Kovačević, D. Žubrinić, Uvod u diskretnu matematiku, Element, Zagreb, 2014.,
(.), A. Nakić, M.-O. Pavčević, Uvod u teoriju grafova, Element, Zagreb, 2014.,
(.), J.M. Aldous, R.J. Wilson, Graphs and Applications - An Introductory Approach, Springer, 2004.,
(.), G. Chartrand, L. Lesniak, Graphs and Digraphs, CRC Press, 2005.,

For students


ID 209648
  Winter semester
L1 English Level
L1 e-Learning
60 Lectures
0 Seminar
0 Exercises
6 Laboratory exercises
0 Project laboratory

Grading System

85 Excellent
70 Very Good
55 Good
45 Sufficient