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	
MC006	Computational Complexity	

Semester	Hours: C+S+L	Category	Status	
8	2+2+0		optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
TRÎMBITAS Radu Tiberiu	Ph.D.	Assoc.Prof.	Numerical and Statistical Calculus	*			

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

III. Course objectives
To introduce students in basics of Computation Complexity, to allow them analize and chose algorithms and to make them aware of limits of computability.	

IV. Course contents
1. Models of computation. 
(Turing Machines, RAM, circuits, Finite-state-machines, Church Thesis)
2. Algorithmic decidability (decidabilty in logic, Recursive and recursive-enumerable languages)
3. Storage and time. (Complexity classes, class P, linear space, general theorems on spece and complexity).
4. Non-determinism (Nondeterministic Turing machines, class NP, NP-completness).
6. Randomized algorithms (Monte-Carlo and Las Vegas algorithms, random numbers, Class BPP)
7. Information complexity
(Kolmogorov complexity, randomness, random number generation).
8. Real computing and complexity (Complexity of real and complex arithmetic, complexity in numerical analysis).
9. Applications - Criptography	

V. Bibliography
1. KNUTH, D.E.: Tratat de programarea calculatoarelor. Vol.I, Algoritmi fundamentali, Ed. Tehnica, Bucuresti, 1974. Vol.II, Algoritmi seminumerici. Vol.III, Sortare si cautare, Ed. Tehnica, Bucurest, 1976.
2. WILF, H.S., Algorithmes et complexite, Mason & Prentice Hall, 1985.
3. BAASE, S.: Computer Algorithms: Introduction to Design and Analysis, Addison- Wesley, 1983.
4. CORMEN, T. - LEISERSON, T., - RIVEST, R.:  - Introduction to Algorithms, MIT Press,1990.
5. PAPADIMITRIOU C. H:  Computational Complexity, Addison Wesley, 1995.
6. GAREY, M. JOHNSON, M. J: Computer and Intractability. A guide to NP-Completness, W. H. Freeman, 1979
7. SIPSER, M.: Introduction to the Theory of Computation, PWS Publishing, 1997
8. LOVASZ, L.: Computation Complexity, Lecture Notes, 1999, [www.research.microsoft.com/users/lovasz/notes.html]	

VI. Thematic of didactic activities per weeks

VII. Didactic methods used

VIII. Assessment
Colloquim.	

IX. Additional references

	Date,							Course responsible,
								Assoc.Prof. TRÎMBITAS Radu Tiberiu, Ph.D.