Faculty of
Computer Science

ro | site map |

home | Profile | Degree Programs | People | Research | Students

A. I. Cuza University of Iaşi

In this section

Overview Undergraduate Master Studies Doctoral School Distance Learning

Quick Links

Degree Programs > Graph Algorithms

Graph Algorithms

Course name

Graph Algorithms

Code

CS2104

Class	Computer Science, 2007 - 2010
Level	Undergraduate	Year	2	Semester	1	Status	Compulsory

Hours per week				Total hours per semester	Total hours of individual work	Credits	Evaluation type	Teaching language
C	S	L	Pr
2	2	0	0	56	94	5	M	ro

Taught by	Academic and scientific title, name
	Professor, PhD, Cornelius Croitoru

Required courses

Objectives	The students will be familiarised with the basic notions and results of the Algorithmic Graph Theory, which will be applied in the design of efficient algorithms for various combinatorial optimization problems.
General thematics	Graph Theory vocabulary, Path problems (graph traversal, shortest paths, connectivity), Minimum spanning trees (union-find, amortized complexity), Matchings, Flows, Polinomial reductions for decision problems on graphs, Approaches for NP-hard problems on graphs, Planar Graphs.
Seminary / Laboratory thematics	Each seminar debates 4 problems (some of them, very difficult) in order to deepen the subjects introduced in the course. All problems are posted at the begining of the semester such that interested students could try to find original solutions or to search similar questions in the related bibliography .
Teaching methods	Video presentations of the slides (containing the course notes) available in pdf format at the begining of the semester.

Bibliography

CROITORU C., Tehnici de baza in optimizarea combinatorie, Editura Univ. Al. I. Cuza Iasi, Iasi,1992.
CROITORU C., Introducere in proiectarea algoritmilor paraleli, Editura Matrix Rom, Bucuresti, 2002.
TOMESCU I., Probleme de combinatorica si teoria grafurilor, Editura did. si ped., Bucuresti,1981.
DIESTEL R., Graph Theory, Electronic Edition.
CORMEN T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, MIT Press 2001.

Evaluation	conditions
	criterias	A student will be considered to have passed the exam if (s)he obtains at least 40 points.
	modes	Seminary activity (attendance, work quality): 0-18 points. Homeworks (3 homeworks, in weeks 4, 8,12) each giving maximum 14 points: 0-42 points. Written Final test: 0-60 points.
	formula	The final grade (if the total number of points is at least 40) is given by applying the ECTS rules.

© 2006-2008 FII | about | intranet