Advanced algorithms

Přednášející:

Radek Mařík

Cvičící:

Radek Mařík

Předmět zajišťuje:

katedra kybernetiky

Anotace:

The advanced course of algorithms construction and analysis is dedicated to the students which have an

interest to be able to evaluate in a experienced way effective and complex algorithms.

The aim of the course is to acquaint with advanced algorithms such as advanced search and sorting algorithms,

hash tables, tree structures used in searching, text searching, syntax analysis, Internet search

algorithms principles (page-ranking), parallel algorithms.

Požadavky:

Individual implementation of data types and algorithms

discussed in the lectures is an important part of the

exercises. Thus, capabilty of programmatic manipulation of

linked data structures in some of the prevalent languages (

C/C++/Java/...) is indispensable.^

Osnova přednášek:

1. Abstract data types, signature, axioms.

2. The methods of specification and implementations of abstract data types.

3. Optimization of the basic sorting algorithms.

4. Hash tables, implementation, complexity.

5. Advanced search trees, AVL, B, Red-Black, operations on the search trees.

6. Balancing the trees implementation and the complexity of the operations.

7. Trees for multidimensional searching.

8. Structure and implementation of a lexical analyzer.

9. LL(1) grammars and transformations to LL(1) grammar.

10. Syntax tree, syntax analysis implemented via recursive descent.

11. Text search algorithms, K-M-P, B-M, Karp-Rabin, finite automaton.

12. Algorithm Page-rank, Internet search algorithms.

13. Parallel and distributed algorithms, motivation and overview.

14. Reserve.

Osnova cvičení:

1. Signature, axioms of basic ADT: queue, stack, list, array.

2. Implementation variants of ADT queue, stack, list, array.

3. Comparison of effectivity of different enhancements of QuickSort, MergeSort, HeapSort.

4. Comparison of effectivity of open and chained hashing, different hash functions.

5. Iterative and recursive processing of the AVL, B, Red-Black trees.

6. Balancing trees - practical implementations.

7. Trees for multidimensional searching.

8. Grammar of the statements and expressions of a simple language .

9. Decomposition tables, transformations to LL(1) grammars.

10. Implementation of the recursive descent.

11. Comparison of the text search algoritms on large datasets.

12. Efectivity of the data structures used in Page-rank algorithm.

13. Parallel number addition, measures of the complexity of the parallel algorithms.

14. Reserve.

Cíle studia:

Fundamental overview and skills related to the topics of

the course.^

Studijní materiály:

Sara Baase, A. van Gelder, Computer Algoritms, Addison Wesley, 2000

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Open Informatics - Artificial Intelligence (povinný předmět programu)
• Open Informatics - Computer Engineering (povinný předmět programu)
• Open Informatics - Computer Vision and Image Processing (povinný předmět programu)
• Open Informatics - Computer Graphics and Interaction (povinný předmět programu)
• Open Informatics - Software Engineering (povinný předmět programu)