### Algorithms and Data Structures

#### Learning Outcomes

1. Describe the use of various data structures
2. Describe a number of standard algoritms
3. Apply appropriate data structures and algorithms to solve specific problems
4. Develop programs using appropriate data structures and algorithms
5. Evaluate the complexity of algorithms and programs
6. Identify appropriate data structures and algorithms to solve specific problems

#### Forms of Teaching

Lectures

Semester is organized in two cycles in totally 15 weeks, which accounts for two weeks for intermediate exams. There are four hours of lectures per week, divided in two terms of two hours (2+2).

Independent assignments

Lecturers assign tasks to students for individual study.

Laboratory

Two to three cycles of laboratory exercises.

#### Week by Week Schedule

1. 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.
2. 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.
3. Recurrence relations; Analysis of iterative and recursive algorithms; Reduction: transform-and-conquer.
4. Divide-and-conquer; Recursive backtracking; Dynamic programming.
5. Worst case quadratic sorting algorithms (selection, insertion); Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort).
6. Linear data structures: arrays and lists; Linked lists.
7. Abstract data types and their implementation (stacks, queues, priority queues, sets, maps).
8. Midterm exam.
9. Hash tables, including strategies for avoiding and resolving collisions.
11. 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).
12. Binary search trees and common operations on binary search trees such as select min, max, insert, delete, iterate over tree.
13. Heaps.
14. Strings and string processing; Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms).
15. Final exam.

#### Study Programmes

Computing (study)
(3. semester)

#### Literature

(.), 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).,

#### General

ID 183381
Winter semester
6 ECTS
L3 English Level
L1 e-Learning
60 Lectures
0 Exercises
6 Laboratory exercises
0 Project laboratory