1. komponenta

Lecture type	Total
Lectures	45

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES: Design of efficient algorithms and precise analysis of their theoretical and practical complexity. Intractable problems and efficient approximate algorithms.

COURSE DESCRIPTION AND SYLLABUS:
1. Introduction. Notion of complexity. Asymptotic behavior of functions. Order of growth. Notation of complexity.
2. Recursive algorithms. Recurrence relations. Examples of recursive algorithms and their complexity.
3. Sorting. Simple sorting by comparison. More complex algorithms: Quicksort, Heapsort, Mergesort. Practical complexity analysis of these algorithms. Lower bound for complexity of sorting by comparisons. Average complexity of Quicksort.
4. Design of efficient algorithms. Shortest path, spanning trees and connected components problems. Efficient realization by disjoint set structure. Fast Fourier transform and applications.
5. Intractable problems. Intuitive notion of classes P and NP. Some NP-complete i NP-hard problems. Integer knapsack and traveling salesperson problems. Design of exact and approximate algorithms for solution of these problems.

Mandatory course - Regular study - Computer Science and Mathematics