Advanced Algorithms and Data Structures

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 % 20 % 0 % 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), Project
  4. Geometric algorithms (e.g., points, line segments, polygons, finding convex hull, spatial decomposition, collision detection, geometric search and proximity), Project
  5. Linear programming (e.g., duality, simplex method, interior point algorithms), Project
  6. Dynamic programming, Project
  7. Greedy algorithms, Project, Lossless and lossy compression algorithms
  8. Midterm exam
  9. Differentiable programming, Project
  10. Randomized algorithms, Stochastic algorithms, Project
  11. Graphs (e.g., topological sort, finding strongly connected components, matching), Bloom filters, Project
  12. Graphs (e.g., topological sort, finding strongly connected components, matching), Project
  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, Project
  14. Reduction: transform-and-conquer, Approximation algorithms, Project
  15. Final exam

Study Programmes

University graduate
Audio Technologies and Electroacoustics (profile)
Free Elective Courses (1. semester) (3. semester)
Communication and Space Technologies (profile)
Free Elective Courses (1. semester) (3. semester)
Computational Modelling in Engineering (profile)
(1. semester)
Computer Engineering (profile)
(1. semester)
Computer Science (profile)
(1. semester)
Control Systems and Robotics (profile)
Free Elective Courses (1. semester) (3. semester)
Data Science (profile)
(3. semester)
Electrical Power Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electric Machines, Drives and Automation (profile)
Free Elective Courses (1. semester) (3. semester)
Electronic and Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electronics (profile)
Free Elective Courses (1. semester) (3. semester)
Information and Communication Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Network Science (profile)
(1. semester)
Software Engineering and Information Systems (profile)
(1. 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

For students

General

ID 222496
  Winter semester
5 ECTS
L3 English Level
L2 e-Learning
45 Lectures
6 Exercises
15 Laboratory exercises

Grading System

90 Excellent
80 Very Good
65 Good
50 Acceptable