### Advanced Algorithms and Data Structures

Data is displayed for academic year: 2023./2024.

#### 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.

#### Study Programmes

[FER3-EN] Data Science - profile
(3. semester)

#### 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

#### 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 222951
Winter semester
5 ECTS
L3 English Level
L2 e-Learning
45 Lectures
0 Seminar
6 Exercises
15 Laboratory exercises
0 Project laboratory
0 Physical education excercises