This masters level algorithms course aims to refine the algorithmic thinking of a student, moving her/him from an algorithm consumer to an algorithm designer. The project-oriented course structure is tailored to facilitate the transition. The first part of the course focuses on the analysis of algorithm complexity and correctness, amortised and probabilistic analysis, while we later discuss advanced data structures, approximation algorithms, heuristic methods and biologically-inspired computing. The course also introduces computational geometry and parallel algorithms.
This course is held in English language and is oriented towards a practical course project. You will need to know the basic algorithms and data structures, and be ready to program a lot!
The course mark is composed of the coursework (the course project and homework) 50%, and the final exam 50%. To take the exam you need to score at least half of the coursework points. In addition, to pass the course, you need at least half of the final exam points.
At the course we will recognize principles and guidelines for designing
User Interfaces (UI), and communication between brains and computer via
movement imagery, i.e., non-invasive Brain-Computer Interface (BCI). The
topics are following: human capabilities (memory and learning,
perception, cognition), types of UI communications (input models, models
and metaphors), UI design principles (Norman's hints, Mandel's
principles, Nielsen's principles), UI design guidelines (selection and
arranging graphic controllers for interaction, graphic design, feedback
and interactions, selection and design of icons), electroencephalogram
(EEG) and brain-computer communication, international reference database
for designing BCI (EEGMMI DS - EEG Motor Movement/Imagery DataSet),
designing non-invasive BCI, spectral analysis of EEG signals (power
spectrum, autoregressive method, time-frequency representations,
parametric modeling), feature extraction in time and frequency domain,
feature selection, classification of imagined movements, BCI with
machine learning, BCI applications (cursor moving, spelling,
communication for handicapped). The environments used will be NetBeans
- nosilec: Franc Jager
Computational complexity of decision and optimization problems
NP-complete and NP-hard problems
Heuristic algorithms, quality of suboptimal solutions, (non)existence of a guarantee of quality
• Approximate solving of NP-hard problems
Quality of approximate solutions
The class APX
The classes PTAS and FPTAS
Limits of approximate solving
• The design of approximation algorithms
Focusing on subproblems
• Randomized solving of NP-hard problems
Las Vegas and Monte Carlo algorithms
The classes RP, co-RP, ZPP, PP, BPP
• The design of randomized algorithm
Establishing abundance of witnesses
- nosilec: Borut Robič
Every programmer should gather insight into programming techniques that are different from the well-known procedural and object-oriented approaches. Lately, the functional programming paradigm is gaining popularity and allows decomposition of programs into independent functions, that can be executed in parallel.
In the Programming course we will study functional programming in programming languages ML and Racket. We will talk about: language typing, lexical and dynamic scopes, function closures, and also develop an interpreter for a custom programming language. Our goal will be to gain deeper understanding of programming languages' and mastery of programming.
Prerequisites for taking this course are basic programming skills in procedural programming languages (such as Java, C++, Python) and understanding of recursion.
Coursework consists of weekly homework assignments, two seminars (the first one to be submitted in the middle of semester, the second one until the end of the semester) and a final exam.
- nosilec: Zoran Bosnić