Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2019/2020

Efficient Algorithms

The course is not on the list Without time-table
Code Completion Credits Range Language
BIK-EFA Z,ZK 5 13KP+4KC Czech
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:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2019-10-14
For updated information see http://bilakniha.cvut.cz/en/predmet1445006.html