Poll

No polls currently selected on this page!

Repository

Repository is empty

Design and analysis of algorithms

Code: 93036
ECTS: 5.0
Lecturers in charge: doc. dr. sc. Matej Mihelčić
English level:

1,0,0

All teaching activities will be held in Croatian. However, foreign students in mixed groups will have the opportunity to attend additional office hours with the lecturer and teaching assistants in English to help master the course materials. Additionally, the lecturer will refer foreign students to the corresponding literature in English, as well as give them the possibility of taking the associated exams in English.
Load:

1. komponenta

Lecture typeTotal
Lectures 45
* Load is given in academic hour (1 academic hour = 45 minutes)
Description:
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.
Literature:
3. semester
Izborni računarski predmet 1, 2 - Regular study - Mathematics and Computer Science Education

4. semester Not active
Izborni računarski predmet 1, 2 - Regular study - Mathematics and Computer Science Education
Consultations schedule: