Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIG0001	Algorithms of Graph Theory	

Semester	Hours: C+S+L	Category	Status	
3	2+1+1	speciality	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
LUPSA Radu	Ph.D.	Lect.	Computer Systems	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
To learn to use the graphs as a modeling tool for problems, and to know the main graph theory problems and their solutions (algorithms). Also, to develop algorithmical thinking.	

IV. Course contents
•	basic graph theory definitions (graph, multigraph, directed graph/multigraph, walk, trail, path), representations;
•	path-related problems: connected and strongly-connected graphs, connected components, shortest path, Moore, Bellman-Kalaba, Dijkstra, Floyd-Warshal algorithms; Eulerian path and Hamiltonian path;
•	partial ordering, critical path; topological sorting and PERT method;
•	trees and forests; Kruskal and Prim algorithms; graph traversal and applications;
•	internal and external stability problems; coloring problem; planar graphs;
•	transport networks and flows; maximum flow problems; matching problems.	

V. Bibliography
1.	Toadere T., Grafe. Teorie, Algoritmi si Aplicatii, Ed. Albastra, Cluj-Napoca, 2002;
2.	Th. Cormen, R. Rivest, Ch. Leiserson. Introduction to Algorithms. Massachusetts Institute of Technology, 1990
3.	Livovschi L., Georgescu H. Algoritmi si grafe.
4.	TOMESCU I., Probleme de combinatorica si teoria grafurilor. Ed. Did. si Pedag. Bucuresti 1981.
5.	Th. Cormen, R. Rivest, Ch. Leiserson. Introducere in algoritmi. trad. Computer Libris Agora, 2000	

VI. Thematic of didactic activities per weeks
•	basic graph theory definitions (graph, multigraph, directed graph/multigraph, walk, trail, path), representations; week 1-2.
•	path-related problems: connected and strongly-connected graphs, connected components, shortest path, Moore, Bellman-Kalaba, Dijkstra, Floyd-Warshal algorithms; week 3-4.
•	partial ordering, critical path; topological sorting and PERT method; week 5-6.
•	trees and forests; Kruskal and Prim algorithms; graph traversal and applications; week 7-8.
•	transport networks and flows; maximum flow problems; matching problems; week 9-11
•	Eulerian path and Hamiltonian path; week 12.
•	internal and external stability problems; coloring problem; planar graphs; week 13-14	

VII. Didactic methods used
Expuneri orale, cu exemple; discutii (interactive) in timpul orelor de curs (in masura posibilitatilor) si de seminar si laborator; exercitii individuale, teoretice si practice, in timpul orelor de seminar si laborator.	

VIII. Assessment
Practical work + exam
1/3 practical work
2/3 written exam	

IX. Additional references
1. BERGE C., Graphes et hypergraphes, Dunod, Paris 1970.
2. BERGE C., Teoria grafurilor si aplicatiile ei, Ed. Tehnica, 1972 
3. KÁSA ZOLTÁN: Combinatiroca cu aplicatii, Presa Universitara Clujeana, 2003.
4. ROSU A.: Teoria grafelor, algoritmi, aplicatii. Ed. Milit.1974 
5. KÁSA Z., TARTIA C., TAMBULEA L.: Culegere de probleme de teoria grafelor, Lito. Univ.   Cluj-Napoca 1979. 
6. CATARANCIUC S., IACOB M.E., TOADERE T., Probleme de teoria grafelor, Lito. Univ.   Cluj-Napoca, 1994. 
7. L. LOVÁSZ : Combinatorial problems and exercises, Akadémiai Kiadó, Budapest, 1980.	

	Date,							Course responsible,
		30 aprilie 2007						Lect. LUPSA Radu, Ph.D.