Skip to main content

Algorithms

2024/2025
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 year
Semester:
second
Kind:
mandatory
ECTS:
6
Language:
slovenian, english
Course director:

Tomaž Dobravec

Hours per week – 2. semester:
Lectures
3
Seminar
1.33
Tutorial
0.67
Lab
0
Prerequisites

Basic knowledge of algorithms and data structures.

Content (Syllabus outline)

The topics:
Computational complexity for divide and conquer algorithms.
Randomized algorithms and probabilistic analysis.
Amortized analysis of algorithms.
Searching in multidimensional spaces: k-d trees, R-trees and locality-sensitive hashing.
Sorting with assumptions: counting sort, radix sort, bucket sort.
Searching with assumptions: van Emde Boats trees.
Hash tables: hash functions, universal hashing, perfect hashing, Bloom filters.
Heuristic programming: local methods.
Metaheuristics for optimization.
Biologically inspired methods: genetic algorithms, differential evolution, swarm intelligence.
Computational geometry: line-segment properties, convex hull, closest pair of points.
Multithreaded and distributed algorithms.
Automata theory and grammars.
Students lacking a required background from the 1st degree courses will gain needed knowledge and skills through additional preparation of seminar papers and programming assignments throughout the course. The topics will be individually selected.

Readings
  1. K. A. Berman, J. L. Paul: Algorithms : sequential, parallel, and distributed, Boston : Thomson, cop. 2005.
  2. T. H. Cormen ... [et al.]: Introduction to Algorithms, 2nd ed. - Cambridge (Mass.) : MIT Press ; Boston : McGraw-Hill, cop. 2001.
  3. J. J. Kleinberg, E. Tardos: Algorithm design, Boston : Pearson/Addison-Wesley, cop. 2006.
Objectives and competences

The goal of this course is to upgrade the knowledge of the analysis of algorithms and data structures and algorithm design techniques. A level where most of the algorithms can be analysed will be reached. Students will expand their algorithm toolbox and a set of design approaches.
General competences:
ability of critical thinking,
developing skills in critical, analytical and synthetic thinking,
the ability to understand and solve professional challenges in computer and information science,
the ability to upgrade acquired knowledge.
Subject-specific competences:
use of master theorem and Akra-Bazzi method for analysis of divide-and-conquer algorithms,
randomization of algorithms,
probabilistic analysis of algorithms,
amortized analysis of algorithms,
classes of formal languages, writing regular expressions and context-free grammars,
the role of assumptions in development of efficient algorithms,
efficient search of spatial data and low-dimensional data,
use of hash tables, construction of hash functions,
preprocessing problems for optimization based on local search,
using met heuristics in local search: variable neighbour method, guided local search, tabu search,
preprocessing problems for biology inspired methods: particle swarm optimization, differential evolution, ant colony optimization
using techniques from computational geometry and efficiently finding convex hull,
analysis of multithreaded algorithms, speed-up
turning single threaded algorithms in multi-threaded algorithms,
knowing distributed algorithm development.

Intended learning outcomes

After the completion of the course a student will be able to:

  • define the difference between easy and hard problems and between good (efficient) and bad (inefficient) solutions,
  • understand the selected algorithms and implement them in a selected programming language,
  • show the algorithmic way of thinking and solving the problems,
  • independently develop algorithms for solving the selected problems,
  • research the selected problem, find an approach to solve the problem and develop an appropriate algorithm,
  • evaluate the quality of a selected algorithm.
Learning and teaching methods

Lectures and homework, assignments are assigned regularly and shall be delivered on time.
For students with low prior knowledge individual work (seminal papers and programming assignments) will be assigned.

Assessment

Continuing (homework and seminar)
Final (written and oral exam)
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

Pet najpomembnejših del/ Five most important works:
KLOBOVES, Klemen, MIHELIČ, Jurij, BULIĆ, Patricio DOBRAVEC, Tomaž. FPGA-Based SIC/XE Processor and Supporting Toolchain. International Journal of Engineering Education, 2017, vol. 33, no. 6(A), pp. 1927–1939
MIHELIČ, Jurij, DOBRAVEC, Tomaž. SicSim: a simulator of the educational SIC/XE computer for a system-software course. Computer applications in engineering education, ISSN 1061-3773, 2015, vol. 23, no. 1, pp. 137-146
ČEŠNOVAR, Rok, RISOJEVIĆ, Vladimir, BABIĆ, Zdenka, DOBRAVEC, Tomaž, BULIĆ, Patricio. A GPU implementation of a structural-similarity-based aerial-image classification. The journal of supercomputing, ISSN 0920-8542, 2013, vol. 65, no. 2, pp. 978-996
BULIĆ, Patricio, DOBRAVEC, Tomaž. An approximate method for filtering out data dependencies with a sufficiently large distance between memory references. The journal of supercomputing, ISSN 0920-8542, 2011, vol. 56, no. 2, pp. 226-244
DOBRAVEC, Tomaž, ROBIČ, Borut. Restricted shortest paths in 2-circulant graphs. Comput. commun.. [Print ed.], March 2009, vol. 32, no. 4, str. 685-690
Celotna bibliografija je dostopna na SICRISu:
http://sicris.izum.si/search/rsr.aspx?lang=slv&,id=10416.