Efficient Algorithms
Code  Completion  Credits  Range  Language 

BIKEFA  Z,ZK  5  13KP+4KC  Czech 
 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 treelike 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 highlevel 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, RBtrees.
6. Binomial and Fibonnaci heaps.
 Syllabus of tutorials:

1. Recap of discrete and asymptotic mathematics. [2] Implementation, stabilization, and indepth 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 wellknown 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 14 (3rd Edition)''. AddisonWesley Professional, 2002. ISBN 0201361205.
 Note:
 Further information:
 https://courses.fit.cvut.cz/BIEFA/
 No timetable has been prepared for this course
 The course is a part of the following study plans:

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