### Advanced Algorithms and Data Structures

#### Course Description

Balanced trees, multiway trees, B-trees. Selected algorithms over graphs. Selected string-based data structures and algorithms. Selected geometric algorithms. Greedy algorithms, dynamic programming, and reductions. Network flows. Linear programming and simplex method. Stochastic, approximation, and randomized algorithms. Differentiable programming. Bloom filters. Selected compression algorithms.

#### Learning Outcomes

1. recognize and analyze problem to be solved using the computer
2. relate problem instance to known, already solved, problem classes
3. select the best algorithm for already solved (known) problem
4. design custom algorithm for unknown problem type
5. evaluate the validity of custom solution with respect to convergence and computational complexity
6. compare custom algorithmic idea to other potential ideas
7. select algorithm for unknown problem based on the comparison between the proposed solutions

#### Forms of Teaching

Lectures

Materials and presentations are on course web page.

Laboratory

complex laboratory assignments which includes algorithms from the lectures

Continuous Assessment Exam
Laboratory Exercises 30 % 30 % 15 % 10 %
Mid Term Exam: Written 30 % 30 % 0 %
Final Exam: Written 30 % 40 %
Exam: Written 50 % 50 %
Exam: Oral 40 %
##### Comment:

short examinations are added above the basic 100%

#### Week by Week Schedule

1. Balanced trees (e.g., AVL trees, red-black trees, splay trees, treaps)
2. Advanced data structures (e.g., B-trees, Fibonacci heaps)
3. String-based data structures and algorithms (e.g., suffix arrays, suffix trees, tries)
4. Geometric algorithms (e.g., points, line segments, polygons, finding convex hull, spatial decomposition, collision detection, geometric search and proximity)
5. Linear programming (e.g., duality, simplex method, interior point algorithms)
6. Dynamic programming
7. Greedy algorithms, Project, Lossless and lossy compression algorithms
8. Midterm exam
9. Midterm exam
10. Randomized algorithms, Stochastic algorithms
11. Graphs (e.g., topological sort, finding strongly connected components, matching), Bloom filters
12. Graphs (e.g., topological sort, finding strongly connected components, matching)
13. Graphs (e.g., topological sort, finding strongly connected components, matching), Network flows (e.g., max flow Ford-Fulkerson algorithm, max flow min cut, maximum bipartite matching), Approximation algorithms
14. Reduction: transform-and-conquer, Approximation algorithms
15. Final exam

#### Study Programmes

[FER3-HR] Audio Technologies and Electroacoustics - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Communication and Space Technologies - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Computational Modelling in Engineering - profile
(1. semester)
[FER3-HR] Computer Engineering - profile
(1. semester)
[FER3-HR] Computer Science - profile
(1. semester)
[FER3-HR] Control Systems and Robotics - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Data Science - profile
(3. semester)
[FER3-HR] Electrical Power Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electric Machines, Drives and Automation - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electronic and Computer Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electronics - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Information and Communication Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Network Science - profile
(1. semester)
[FER3-HR] Software Engineering and Information Systems - profile
(1. semester)
[FER2-HR] Computer Engineering - profile
Theoretical Course (1. semester)
[FER2-HR] Computer Science - profile
Theoretical Course (1. semester)
[FER2-HR] Information Processing - profile
Theoretical Course (1. semester)
[FER2-HR] Software Engineering and Information Systems - profile
Theoretical Course (1. semester)
[FER2-HR] Telecommunication and Informatics - profile
Specialization Course (1. semester) (3. semester)

#### Literature

Thomas H. Cormen (2009.), Introduction to Algorithms, MIT Press
Adam Drozdek (2012.), Data Structures and Algorithms in C++, Thomson Course Technology
Steven S. Skiena (2008.), The Algorithm Design Manual, Springer-Verlag New York Incorporated
R. Sedgewick, K. Wayne (2011.), Algorithms 4th ed., Addison-Wesley
D. Kalpić, V. Mornar (1996.), Operacijska istraživanja, Zeus
J. Matousek, B.Gartner (2006.), Understanding and Using Linear Programming, Springer
Vijay V. Vazirani (2002.), Approximation Algorithms, Springer Science & Business Media
R. Motwani, P. Raghavan (1995.), Randomized Algorithms, Cambridge University Press
I. Goodfellow, Y. Bengio and A. Courville (2015.), Deep Learning, MIT press

#### General

ID 222496
Winter semester
5 ECTS
L1 English Level
L2 e-Learning
45 Lectures
0 Seminar
6 Exercises
15 Laboratory exercises
0 Project laboratory