Algorithms

Subject description

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.

The subject is taught in programs

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.

Teaching and learning 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.

Expected study results

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.

Basic sources and literature

T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009.
K.A.Berman, J.L. Paul: Algorithms: Sequential, Parallel, and Distributed. Thomson, 2005.
J. Kleinberg, E. Tardos: Algorithm Design. Pearson Education, 2006.