Algorithms

The topics:

1. Computational complexity for divide and conquer algorithms.

2. Randomized algorithms and probabilistic analysis.

3. Amortized analysis of algorithms.

4. Searching in multidimensional spaces: k-d trees, R-trees and locality-sensitive hashing.

5. Sorting with assumptions: counting sort, radix sort, bucket sort.

6. Searching with assumptions: van Emde Boats trees.

7. Hash tables: hash functions, universal hashing, perfect hashing, Bloom filters.

8. Heuristic programming: local methods.

9. Metaheuristics for optimization.

10. Biologically inspired methods: genetic algorithms, differential evolution, swarm intelligence.

11. Computational geometry: line-segment properties, convex hull, closest pair of points.

12. Multithreaded and distributed algorithms.

13. 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 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.

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.