Subject description - B4M33PAL

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
B4M33PAL Advanced algorithms Extent of teaching:2P+2C
Guarantors:Průša D. Roles:P,PV Language of
teaching:
CS
Teachers:Genyk-Berezovskyj M., Průša D. Completion:Z,ZK
Responsible Department:13133 Credits:6 Semester:Z

Anotation:

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

Study targets:

Fundamental overview and skills related to the topics of the course.

Course outlines:

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.

Exercises outline:

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.

Literature:

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

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.

Webpage:

http://cw.fel.cvut.cz/wiki/courses/b4m33pal/start

Keywords:

Directed and undirected graph, graph algorithm, priority queue, pattern matching,

Subject is included into these academic programs:

Program Branch Role Recommended semester
MPBIO3_2018 Common courses PV 1
MPBIO2_2018 Common courses PV 1
MPBIO4_2018 Common courses PV 1
MPBIO1_2018 Common courses PV 1
MPOI1_2016 Human-Computer Interaction P 1
MPOI9_2016 Data Science P 1
MPOI8_2016 Bioinformatics P 1
MPOI7_2016 Artificial Intelligence P 1
MPOI6_2016 Software Engineering P 1
MPOI5_2016 Computer Vision and Image Processing P 1
MPOI4_2016 Computer Engineering P 1
MPOI3_2016 Computer Graphics P 1
MPOI2_2016 Cyber Security P 1
MPOI1_2018 Human-Computer Interaction P 1
MPOI9_2018 Data Science P 1
MPOI8_2018 Bioinformatics P 1
MPOI7_2018 Artificial Intelligence P 1
MPOI6_2018 Software Engineering P 1
MPOI5_2018 Computer Vision and Image Processing P 1
MPOI4_2018 Computer Engineering P 1
MPOI3_2018 Computer Graphics P 1
MPOI2_2018 Cyber Security P 1


Page updated 9.12.2019 17:52:19, semester: Z,L/2020-1, L/2018-9, Z,L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)