Efficient Algorithms

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Department of Theoretical Computer Science

Synopsis:

Students get a solid overview of efficient algorithms for solving classical algorithmic problems: selecting, searching, sorting, and other basic forms of reshaping and processing tree-like data structures. Students are able to design and implement such algorithms, to analyse their complexity, and to develop an optimised efficient algorithm under specific requirements or constraints. They are able to recognise a proper algorithm variant for any specific usage.

Requirements:

We assume an ability to actively solve basic algorithmic problems, to express the algorithmic solution in a high-level programming language (Java, C++) and knowledge of basic notions from a calculus and combinatorics.

Syllabus of lectures:

1. Mathematical foundation for the theory of algorithmic complexity. Sorting in n.log n, advanced analysis of QuickSort.

2. Heap, HeapSort, priority queue. Sorting in linear time, sorting in external memory.

3. Recursion, complexity of recursive algorithms. Search problem, 1D address search, mapping function.

4. Hash tables, open and chained addressing, hash functions. Associative search, binary search trees, string matching in a text.

5. Multidimensional search, multidimensional search trees. Balancing of search trees, RB-trees.

6. Binomial and Fibonnaci heaps.

Syllabus of tutorials:

1. Recap of discrete and asymptotic mathematics. [2] Implementation, stabilization, and in-depth complexity analysis of sorting algorithms. Implementation and complexity analysis of sorting in external memory. Comparison of recursive and iterative algorithm design, mutual transformations. Recurrent equations solving techniques. Address search, design of mapping functions.

2. Hash table usage, open and chained addressing. Search, binary search trees, string matching. Multidimensional search trees, closest neighbor. Balanced search trees. Advanced heaps, operations, applications.

Study Objective:

The goal of the course is to equip the student with a set of well-known standard algorithms and to help him/her recognize a proper algorithm variant for any specific usage. At the same time, the student will learn basic methods of algorithm analysis to be used as a main efficiency criterium.

Study materials:

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L. ''Introduction to Algorithms''. The MIT Press, 2001. ISBN 0262032937.

2. Sedgewick, R. ''Algorithms in Java, Parts 1-4 (3rd Edition)''. Addison-Wesley Professional, 2002. ISBN 0201361205.

Note:

Further information:

https://courses.fit.cvut.cz/BI-EFA/

No time-table has been prepared for this course

The course is a part of the following study plans:

• Bachelor program Informatics, unspecified branch, in Czech, part-time, 2015 – 2021 (VO)
• Bachelor branch Security and Information Technology, in Czech, part-time, 2015 - 2019 (elective course)
• Bachelor branch Web and Software Engineering, spec. Software Engin., in Czech, part-time, 2015–2020 (elective course)
• Bachelor branch Security and Information Technology, part-time, in Czech, 2020 (elective course)