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 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. |