Discrete Mathematics 1
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.
- To solve homogeneous and non-homogeneous linear recursion.
- Apply the recursive way of thinking on the appropriate combinatorial problems.
- Describe and manipulate with basic notions from graph theory.
- Describe and solve appropriate engineering problems in terms of graph theory.
- 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.
|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
- Fibonacci's sequence, Homogeneous recursive relations
- Homogeneous recursive relations
- Non-homogeneous recursive relations
- Notion of a graph; Main definitions and examples; Graph isomorphism
- Connectivity; Paths; Eulerian and hamiltonian graphs, Optimization algorithms; Shortest path problem; Chinese postman problem; Travelling salesman problem
- Different characterizations of trees
- Labelled trees; Prüfer code, Minimum spanning tree; Algorithms
- Midterm exam
- Kuratowski's theorem, Euler's formula
- Dual graphs, Planarity testing algorithms
- Vertex colourings; Brooks' theorem, Edge colourings
- Face colourings of planar graphs; Four colour theorem
- Notion of a digraph; Connectivity and strong connectivity, Critical path problem; Algorithms, Tournaments
- Marriage problem, Hall's theorem, Transversals, Application to latin squares
- Final exam
[FER3-HR] Computing - study(3. semester)
(.), 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.,
L1 English Level
6 Laboratory exercises
0 Project laboratory
70 Very Good