Discrete Mathematics 1
Learning Outcomes
- 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
Lectures
4 hours of lectures a week. The lecturer is going to follow the lecture materials.
Independent assignmentsDuring 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
- 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.
Study Programmes
University undergraduate
Computing (study)
(3. semester)
Literature
(.), 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.,
Laboratory exercises
For students
General
ID 183396
Winter semester
6 ECTS
L1 English Level
L1 e-Learning
60 Lectures
0 Exercises
6 Laboratory exercises
0 Project laboratory
Grading System
85 Excellent
70 Very Good
55 Good
45 Acceptable