Advanced Algorithms
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| BE4M33PAL | Z,ZK | 6 | 2P+2C | English |
- Vztahy:
- It is not possible to register for the course BE4M33PAL if the student is concurrently registered for or has already completed the course B4M33PAL (mutually exclusive courses).
- During a review of study plans, the course B4M33PAL can be substituted for the course BE4M33PAL.
- During a review of study plans, the course A4M33PAL can be substituted for the course BE4M33PAL.
- It is not possible to register for the course BE4M33PAL if the student is concurrently registered for or has already completed the course A4M33PAL (mutually exclusive courses).
- In order to register for the course BE4M33PAL, the student must have registered for the required number of courses in the group BEZBM no later than in the same semester.
- It is not possible to register for the course BE4M33PAL if the student is concurrently registered for or has previously completed the course A4M33PAL (mutually exclusive courses).
- It is not possible to register for the course BE4M33PAL if the student is concurrently registered for or has previously completed the course B4M33PAL (mutually exclusive courses).
- Garant předmětu:
- Daniel Průša
- Lecturer:
- Marko Genyk-Berezovskyj, Daniel Průša
- Tutor:
- Marko Genyk-Berezovskyj, Max Hollmann, Daniel Průša
- 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:
-
Fundamental overview and skills related to the topics of the course.
- 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:
- https://cw.fel.cvut.cz/wiki/courses/BE4M33PAL
- Time-table for winter semester 2024/2025:
-
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 Wed Thu Fri - Time-table for summer semester 2024/2025:
- Time-table is not available yet
- The course is a part of the following study plans:
-
- Open Informatics - Artificial Intelligence (compulsory course in the program)
- Open Informatics - Computer Vision and Image Processing (compulsory course in the program)
- Open Informatics - Software Engineering (compulsory course in the program)
- Open Informatics - Human-Computer Interaction (compulsory course in the program)
- Open Informatics - Cyber Security (compulsory course in the program)
- Open Informatics - Computer Graphics (compulsory course in the program)
- Open Informatics - Computer Engineering (compulsory course in the program)
- Open Informatics - Bioinformatics (compulsory course in the program)
- Open Informatics - Data Science (compulsory course in the program)
- Medical Electronics and Bioinformatics - Specialization Image Processing (PS)
- Medical Electronics and Bioinformatics - Specialization Signal Processing (compulsory elective course)
- Medical Electronics and Bioinformatics - Specialization Bioinformatics (PS)
- Medical Electronics and Bioinformatics - Specialization Medical Instrumentation (compulsory elective course)