Subject description - AE4M33PAL

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
AE4M33PAL Advanced algorithms Extent of teaching:2+2c
Guarantors:  Roles:P,V Language of
teaching:
EN
Teachers:  Completion:Z,ZK
Responsible Department:13133 Credits:6 Semester:Z

Anotation:

Basic graph algorithms and graph representation. Application of formal languages theory in computer science - syntax analysis and pattern matching. Selected topics of floating-point arithmetic.

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. Graph searching applications: Shortest path algorithms: weighted, unweighted, directed, undirected.
3. Directed graphs: Acyclic, topologically ordered, rooted trees. Algorithms and implementation.
4. Text searching and pattern matching. Algorithms KMP, BM, Karp-Rabin and their variants.
5. Pattern matching automata. Factor, prefix and suffix automata.
6. Text compression, Huffman coding, LZW algorithm.
7. Design and implementation of lexical analyzer.
8. LL and LL(1) grammars, parsing tables.
9. Syntax analysis algorithm., top-down parsing.
10. Floating-point representation of numbers, formats, operations, NaN, infinity. Propagation of rounding errors.
11. (Pseudo)random number generators, periodicity, distribution.
12. Estimation of rounding errors in numerical algorithms. Roots of functions, matrix inversion, system of linear equations
13. (Reserve) Exact calculation of mathematical function values, compatibility across architectures, languages and compilers.

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.felk.cvut.cz/doku.php/courses/ae4m33pal/start

Keywords:

Directed and undirected graph, graph algorithm, syntax analysis, pattern matching, floating-point arithmetic.

Subject is included into these academic programs:

Program Branch Role Recommended semester
MEKME1 Wireless Communication V 1
MEKME5 Systems of Communication V 1
MEKME4 Networks of Electronic Communication V 1
MEKME3 Electronics V 1
MEKME2 Multimedia Technology V 1
MEOI1 Artificial Intelligence P 1
MEOI5NEW Software Engineering P 1
MEOI5 Software Engineering P 1
MEOI4 Computer Graphics and Interaction P 1
MEOI3 Computer Vision and Image Processing P 1
MEOI2 Computer Engineering P 1
MEEEM1 Technological Systems V 1
MEEEM5 Economy and Management of Electrical Engineering V 1
MEEEM4 Economy and Management of Power Engineering V 1
MEEEM3 Electrical Power Engineering V 1
MEEEM2 Electrical Machines, Apparatus and Drives V 1
MEKYR4 Aerospace Systems V 1
MEKYR1 Robotics V 1
MEKYR3 Systems and Control V 1
MEKYR2 Sensors and Instrumentation V 1


Page updated 27.6.2019 07:52:39, 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)