Discrete Mathematics 1
- 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
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.,