SylabUZ
Course name | Graphs and networks in computer science |
Course ID | 11.9-WE-INFD-GaNiCS-Er |
Faculty | Faculty of Computer Science, Electrical Engineering and Automatics |
Field of study | Computer Science |
Education profile | academic |
Level of studies | Second-cycle Erasmus programme |
Beginning semester | winter term 2021/2022 |
Semester | 1 |
ECTS credits to win | 5 |
Course type | obligatory |
Teaching language | english |
Author of syllabus |
|
The class form | Hours per semester (full-time) | Hours per week (full-time) | Hours per semester (part-time) | Hours per week (part-time) | Form of assignment |
Lecture | 30 | 2 | - | - | Credit with grade |
Laboratory | 30 | 2 | - | - | Credit with grade |
Introduction to the graph theory. History of the area. Applications of the graph theory in computer science and software.
Directed and undirected graphs. Examples, definitions of the main notions of the graph theory. Important classes of graphs.
Ways of representing of the graphs in data structures - matrices and lists.
The main graph search algorithms: BFS, DFS. Selected applications of the graph search algorithms (topological sorting, finding the strongly connected components).
Eulerian paths, conditions of existence, methods of finding. Hamiltonian paths, conditions of existence. Applications.
Program evaluation and review technique, critical path method.
Minimal spanning trees, application, algorithms of constructing.
Shortest paths in the graphs (Dijkstra's, Bellman-Ford, Floyd-Warshall algorithms).
Maksimum flow in the flow networks, Ford–Fulkerson algorithm.
Graph coloring and its applications. Greedy algorithms of graph coloring.
Computational complexity of the graph algorithms. NP-hard graph problems, travelling salesman problem as an example. Heuristic and approximation algorithms for the NP-hard problems.
Binary decision diagrams: BDD, ROBDD, other modifications. BDD as an effcient way of representing the Boolean functions.
Elements of the Petri net theory: main notions, behavioral properties, methods of analysis, main applications.
Lecture: conventional lecture, discussions, presenting of the selected algorithms by the students
Laboratory: computer laboratory exercises
Outcome description | Outcome symbols | Methods of verification | The class form |
Lecture – the passing condition is to obtain a positive mark from the final test.
Laboratory – the passing condition is to obtain positive marks from all laboratory exercises to be planned during the semester.
Calculation of the final grade: lecture 60% + laboratory 40%
Modified by dr inż. Grzegorz Łabiak (last modification: 12-09-2021 21:32)