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

Advanced algorithms

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
BE4M33PAL Z,ZK 6 2p+2c
Corequisite:
Safety in Electrical Engineering for a master´s degree (BEEZM)
The course cannot be taken simultaneously with:
Advanced algorithms (A4M33PAL)
Advanced algorithms (B4M33PAL)
The course is a substitute for:
Advanced algorithms (A4M33PAL)
Advanced algorithms (B4M33PAL)
Lecturer:
Daniel Průša (guarantor), Marko Genyk-Berezovskyj
Tutor:
Daniel Průša (guarantor), Marko Genyk-Berezovskyj, Lama Saeeda
Supervisor:
Department of Cybernetics
Synopsis:

Basic graph algorithms and graph representation. Combinatorial algorithms. Application of formal languages theory in computer science - pattern matching.

Requirements:

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.

Syllabus of lectures:

Formal and informal analysis of the memory and time complexity of all data sructures and algorithms taught is an integral part of the course, it is not expicitely listed under particular topics.

1. Asymptotic complexity of algorithms. Graphs, their properties and memory representation.

2. Minimum spanning tree. Union-Find problem.

3. Euler paths. Directed graphs: connectivity, acyclic graphs.

4. Heaps. Fibonacci heap. Heaps performance comparison.

5. Dynamic data structures. Garbage collector.

6. Generating, enumeration aand isomorphism of data structures and combinatorial objects. Permutations, combinations, variations, trees.

7. Generating other combinatorial structures: k-element subsets, Gray code, non-isomorphic graphs.

8. Search in sequences - linear and quadratic interpolation. Median search.

9. Finite automata, implementation, automaton reduction.

10. Regular expressions and text search using regular expressions.

11. Approximate text search using finite automata, dictionary automata.

12. Search in higher dimensions, K-D trees, Quadtree.

13. Search trees: B a B+; 2-3-4 a R-B trees.

14. Search trees: Trie, suffix tree, splay tree.

Syllabus of tutorials:

Exercises and related homeworks are devoted mostly to implementation of lecture topics. Consequently, the themes of each exercise formally correspond to those of respective lecture.

Study Objective:
Study materials:

R. Sedgewick: Algoritmy v C, SoftPress 2003,

T. H. Cormen, C. E. Leiserson, R. L. Rievest, C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001

B. Melichar: Jazyky a překlady, Praha , ČVUT 1996

J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001

Note:
Further information:
http://cw.fel.cvut.cz/wiki/courses/be4m33pal/start
Time-table for winter semester 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Fri
roomKN:E-112
Genyk-Berezovskyj M.
Průša D.

11:00–12:30
(lecture parallel1)
Karlovo nám.
Cvičebna Vyčichlova
roomKN:E-127
Saeeda L.
12:45–14:15
(lecture parallel1
parallel nr.101)

Karlovo nám.
Kotkova cvičebna K4
Thu
Fri
Time-table for summer semester 2018/2019:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2019-03-24
For updated information see http://bilakniha.cvut.cz/en/predmet4685106.html