GRAPHS ALGORITHMS

Type of course:	Compulsory
Language of instruction:	Romanian
Erasmus Language of instruction:	English
Name of lecturer:	Pax Dorin Wainberg-Drăghiciu
Seminar tutor:	Pax Dorin Wainberg-Drăghiciu
Form of education	Full-time

Form of instruction:	Class
Number of teaching hours per semester:	56
Number of teaching hours per week:	4
Semester:	Summer
Form of receiving a credit for a course:	Grade
Number of ECTS credits allocated	7

Course aims:

Our aims in this course are twofold. First, to discuss some of the major results of graph theory, and to provide an introduction to the language, methods and terminology of the subject
Second, to emphasize various approaches (algorithmic, probabilistic, etc.) that have proved fruitful in modern graph theory: these modes of thinking about the subject have also proved successful in areas of informatics.
-..

Course Entry Requirements:

Linear Algebra

Course contents:

1. Preliminaries. General notions. 2. Basic concepts in Graph Theory. Cyclomatic number 3. Graph traversal. Breadth First Traversal. Depth First Traversal 4. Minimum distances in graphs 5. Connected components 6. Bipartite graphs. Maximum matching problem in a bipartite graph 7. Hamiltonian paths and circuits . Chen algorithm. Foulkes algorithm. Kaufmann algorithm 8. Flow networks. Bellman-Kalaba algorithm. Ford algorithm. Dijkstra algorithm 9. Maximum flow in transport networks 10. Trees. Deffinitions and theorems. 11. Traversal of a dirrected tree 12. Trees of minimum values. Kruskal algorithm. Sollin algorithm 13. Binary trees 14. Structural trees

Teaching methods:

Lecture, conversation, exemplification.

Learning outcomes:

Modelling and solving some medium complexity level problems, using the mathematical and computer sciences knoweledges.

Learning outcomes verification and assessment criteria:

Written paper 50%; mid-term test 30%; seminar activities 20%.