Algorithms and Data Structures
- Class 60
- Practice 6
- Independent work 114
Algorithms and Data Structures
Lecturers and associates
- Associate Professor PhD Ivica Botički
- Associate Professor PhD Mirjana Domazet-Lošo
- Full Professor PhD Vedran Mornar
- Full Professor PhD Mile Šikić
The concept and properties of algorithms; Differences among best, expected, and worst case behaviors of an algorithm; Big O notation: formal definition and use; Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor; Records/structs (heterogeneous aggregates); References and aliasing.
Asymptotic analysis of upper and expected complexity bounds; Constant, logarithmic, linear, quadratic, and exponential complexity classes; Empirical measurements of performance; Time and space trade-offs in algorithms; Little o, big omega and big theta notation; Sequential and binary search algorithms; Strategies for choosing the appropriate data structure.
Recurrence relations; Analysis of iterative and recursive algorithms; Reduction: transform-and-conquer.
Divide-and-conquer; Recursive backtracking; Dynamic programming.
Worst case quadratic sorting algorithms (selection, insertion); Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort).
Linear data structures: arrays and lists; Linked lists.
Abstract data types and their implementation (stacks, queues, priority queues, sets, maps).
Hash tables, including strategies for avoiding and resolving collisions.
Advanced data structures: multi-way trees and graphs; Representations of graphs (e.g., adjacency list, adjacency matrix) and Depth- and breadth-first traversals.
Brute-force algorithms; Greedy algorithms; Branch-and-bound; Shortest-path algorithms (Dijkstra's and Floyd's algorithms); Minimum spanning tree (Prim's and Kruskal's algorithms).
Binary search trees and common operations on binary search trees such as select min, max, insert, delete, iterate over tree.
Strings and string processing; Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms).
- Artificial Intelligence
- Interactive Computer Graphics
- Software Design Project
- Multimedia Technologies
- Scripting Languages
- Object-oriented programming
(.), Predavanja iz predmeta,
(.), Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 3rd ed. MIT Press, 2009.,
(.), Sedgewick and Wayne. Algorithms (4th Edition). Addison-Wesley Professional; 4th edition (2011).,
Online education during epidemiological measures
- Study program duration
- 6 semesters (3 years)
- Semester duration
- 15 weeks of active teaching + 5 examination weeks
- Total number of ECTS points
- Bacc.ing.comp (Bachelor of Science in Computing)
Minimal learning outcomes
- Describe the use of various data structures
- Describe a number of standard algoritms
- Apply appropriate data structures and algorithms to solve specific problems
- Develop programs using appropriate data structures and algorithms
- Evaluate the complexity of algorithms and programs
- Identify appropriate data structures and algorithms to solve specific problems