Advanced algorithms

Předmět AE4M33PAL může při kontrole studijních plánů nahradit předmět A4M33PAL

Předmět AE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět A4M33PAL (vztah je symetrický)

Předmět AE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M33PAL (vztah je symetrický)

Předmět AE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět A4M33PAL (vztah je symetrický)

Předmět AE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M33PAL (vztah je symetrický)

Garant předmětu:

Přednášející:

Cvičící:

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.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AE4M33PAL

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

Další informace:

http://cw.felk.cvut.cz/doku.php/courses/ae4m33pal/start

Pro tento předmět se rozvrh nepřipravuje

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