Algorithms

To survive in the brave new digital world students have to get acquainted with the programming toolbox and make at least a byte shovel. The word is about algorithms and data structures, which in computer science are basic tools to transfer ideas and dreams into reality.

 

If one does not want to reinvent the wheel, it is wise to know at least the frequently used algorithms and some well tested and successful methods for development of new algorithms. In general, it seems that standing on the shoulders of giants is the best strategy for a quick progress. In high altitude one sees farther, so one should know about spatial data structures and climb the k-d, R, and van Emde-Boats trees. The course will drop comparison sort and make some assumptions to sort in linear time. Standard toolbox includes algorithms from computational geometry and use of linear programming and hash functions. When exact methods do not work, local search, heuristic problem solving and biologically inspired methods can be a solution. Knowing what tool (algorithm) to use in which circumstances is also essential, so one has to compare different algorithms. Will my new algorithm run a few seconds, a few minutes, or a few millennia? The course will offer a way to answer these questions through the analysis of computational complexity, in particular with probabilistic and amortized analysis. Luckily, nowadays processors have more and more cores, so knowledge of parallel and distributed algorithms comes handy.

 

The students who haven’t learnt enough of algorithms in their first degree study will be offered additional contents as a self-study at the beginning of the semester.

Practical part is in the form of programming assignments, solving problems, and web quizzes. Assistant is available for consultations. The grade of practical work is a joint grade of three assignments, which have to be finished on time and graded with at least 50% of points. The precondition for passing practical work is achieving at least 50% of points in web quizzes.

The final course grade consists of practical work grade (50%) and written exam (50%), in both parts one has to achieve at least 50% of points. Oral exam is optional.

 

Approximation and randomized algorithms

The course will offer the following themes:

•    Introduction
    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
    Approximation algorithms
    Quality of approximate solutions
    The class APX
    Gap technique
    Approximation schemes
    The classes PTAS and FPTAS
    Limits of approximate solving
•    The design of  approximation algorithms
    Greedy method
    Focusing on subproblems
    Iterative partitioning
    Dynamic programming
•    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
    Random sampling
    Establishing abundance of witnesses
    Random reordering
    Hashing
    Load balancing

Functional programming

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.

Human-Computer Interaction

Professors:

assist. prof. dr. Ciril Bohak

assist. prof. dr. Luka Čehovin Zajc

Short content:

This course provides a comprehensive introduction to the field, exploring the design and evaluation of interactive systems. Students will learn foundational concepts like usability, user-centered design, and interaction design alongside critical techniques like prototyping, usability testing, and information architecture. The course delves into user research, design thinking, and accessibility, emphasizing the importance of designing inclusive and efficient interfaces. Advanced topics include data-driven design, A/B testing, and emerging technologies like AR/VR, brain-computer interfaces, and human-robot interaction. Through case studies and real-world applications, students will develop skills to create user-friendly and innovative solutions.