Analysis and complexity of algorithms 
ter 

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 NPcomplete 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. NPcompleteness. 9. Approximation algorithms: knapsack problems, binpacking, graph coloring. 
References 
1. S. Baase: Computer Algorithms. Introduction to design and analysis, AddisonWesley, 1983 (Second ed. 1988)
2. M.R. Garey, D.S. Johnson: Computers and intractability. A guide to the theory od NPcompleteness, 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, AddisonWesley, 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. 