"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science

Analysis and complexity of algorithms
Code
Semes-
ter
Hours: C+S+L
Credits
Type
Section
MI019
6
2+1+0
5
optional
Informatică
Teaching Staff in Charge
Prof. KASA Zoltan, Ph.D., kasa@cs.ubbcluj.ro
Aims
The aim of this course is to introduce the students in the problems of analysing and complexity of the algorithms. Several methods of computing the complexity are presented. Polynomial and NP-complete problems are treated.

Content
1. Analysis of algorithms, principles, axamples.
2. Complexity of internal sorting algorithms: bubblesort, quicksort, heapsort, shellsort, bucket sort, binary merge.
3. Complexity of external sorting algorithms.
4. Complexity of algorithms in graph theory: minimal spanning algorithm, shortest paths, macthing problems.
5. Complexity of algorithms in pattern recognition.
6. Complexity of algorithms in matrix algebra: multiply of matrices(Winograd, Strassen), discret Fourier transform.
7. Complexity of Boole algorithms (relations, Boole matrices, Warshall)
8. NP-completeness.
9. Approximation algorithms: knapsack problems, binpacking, graph coloring.
References
1. S. Baase: Computer Algorithms. Introduction to design and analysis, Addison-Wesley, 1983 (Second ed. 1988)
2. M.R. Garey, D.S. Johnson: Computers and intractability. A guide to the theory od NP-completeness, Freeman, 1979.
4. Lovasz L., Algoritmusok bonyolultsaga, ELTE, Budapest, 1992.
5. M. Sipser, Introduction to the theory of computation, PWS Publ. Co. 1997
6. Papadimitriu, C. H., Computational Complexity, Addison-Wesley, 1994.
7. Cormen, T. H.–Leiserson, C. E.–Rivest, R. L., Algoritmusok, Műszaki Kiadó, Budapest, 1997.
8. Wagner, K.–Wechsung, G., Computational Complexity, D. Reidel P. Co., 1986
Assessment
Written exam.