Professional study programme

Back   Schedule   Hrvatski

Graph Algorithms SIR401-17

ECTS 5 | P 30 | A 15 | L 15 | K 0 | ISVU 175204 | Academic year: 2019./2020.

Course groups

Prikaži sve grupe na predmetu

Course lecturers

BAUMGARTNER ALFONZO, Lecturer

Goals

Students will be introduced to the definition of a graph as a data structure, its efficient representation in the computer, and various special types of graphs. Through well-known problems with graphs and algorithms for their solution, students will become familiar, at the conceptual level, with and also practically implement some of the algorithms and thus learn how to use a graph data structure to model the actual physical problems.

Conditions for enrollment

The necessary requirements to enrol in the second year of the studies.

Course description

Introduction and basic terms. A mathematical definition of the graph and examples. Types of graphs. An efficient way to store graphs in the computer. Rarely filled graphs. The problem of graph traversal. BFS and DFS algorithms. The problem of node connectivity in a graph. An algorithm for finding strongly connected components in a graph. The problem of the Euler cycle. The smallest spanning tree problem. The shortest path problem. The Bellman-Ford and the Dijkstra algorithm. NP-complex graph problems. The graph colouring problem. The travelling salesman problem. Network definition. The maximum flow problem in the network.

Student requirements

Defined by the Student evaluation criteria of the Faculty of Electrical Engineering, Computer Science and Information Technology Osijek and paragraph 1.9

Monitoring of students

Defined by the Student evaluation criteria of the Faculty of Electrical Engineering, Computer Science and Information Technology Osijek and paragraph 1.9

Obligatory literature

1. 1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introduction to Algorithms (3rd ed.) MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (2009) [1990]


Pretraži literaturu na:

Recommended additional literature

1. 1 R. Sedgewick Algorithms in C++ Part 5: Graph Algorithms (3rd Edition) Addison-Wesley Professional, 2002.

2. 2 Shimon Even Graph Algorithms Cambridge University Press, 2011, ISBN: 1139504150, 9781139504157

Course assessment

Conducting university questionnaires on teachers (student-teacher relationship, transparency of assessment criteria, motivation for teaching, teaching clarity, etc.). Conducting Faculty surveys on courses (upon passing the exam, student self-assessment of the adopted learning outcomes and student workload in relation to the number of ECTS credits allocated to activities and courses as a whole).

Overview of course assesment

Learning outcomes
Upon successful completion of the course, students will be able to:

1. describe a graph data structure and some known graph problems and graph algorithms

2. identify the graph structure in modelling many known problems and use it to solve these problems

3. perform complexity analysis for known graph algorithms

4. implement and use different algorithms for problems such as the shortest path, an Euler cycle, and the like

5. apply the acquired knowledge in designing software support where it is necesary to use graphs



Aktivnosti studenta: Vidi tablicu aktivnosti

Student's activity Workload ECTS (Workload/30) Learning outcomes
Upon successful completion of the course, students will be able to:
Teaching
method
Assessment method Points
Pohađanje Predavanja (PR), Auditorne vježbe (AV), Laboratorijske vježbe (LV)6021,2,3,4,5Predavanja (PR), Auditorne vježbe (AV), Laboratorijske vježbe (LV)Evidentiranje nazočnosti. Minimum potreban za potpis iznosi: 70%. 710
Rješavanje zadataka3012,3,4Kontrolne zadaće (pismeni ispit)Provjera riješenih zadataka2040
Pisanje priprema za LV, analiza rezultata, te pisanje izvještaja3014,5Laboratorijske vježbe (LV)Provjera pripreme za LV, nadzor provođenja LV-a, provjera napisanih izvještaja1020
Priprema za usmeni ispit i usmeno odgovaranje na pitanja3011,2,3Usmeni ispitProvjera danih odgovora1530