Advanced Algorithms and Data Structures

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

Lecturers

Asst. Prof.
Mario Brčić

Exercises

Mihael Kovač
mag. ing.

Laboratory exercises

Mihael Kovač
mag. ing.

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

University graduate
[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

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
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

For students

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

Grading System

90 Excellent
80 Very Good
65 Good
50 Sufficient

Similar Courses