Basic knowledge of algorithms and data structures.

# Algorithms

Tomaž Dobravec

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.

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

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.

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.

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.

Continuing (homework and seminar)

Final (written and oral exam)

grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

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.