Advanced algorithms

The course cannot be taken simultaneously with:

Advanced algorithms (A4M33PAL)
Advanced algorithms (B4M33PAL)

The course is a substitute for:

Advanced algorithms (A4M33PAL)

Lecturer:

Tutor:

Supervisor:

Department of Cybernetics

Synopsis:

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.

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. 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.

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:

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

No time-table has been prepared for this course

The course is a part of the following study plans:

• Cybernetics and Robotics - Robotics (elective course)
• Cybernetics and Robotics - Senzors and Instrumention (elective course)
• Cybernetics and Robotics - Systems and Control (elective course)
• Open Informatics - Artificial Intelligence (compulsory course in the program)
• Open Informatics - Computer Engineering (compulsory course in the program)
• Open Informatics - Computer Vision and Image Processing (compulsory course in the program)
• Open Informatics - Computer Graphics and Interaction (compulsory course in the program)
• Open Informatics - Software Engineering (compulsory course in the program)
• Communications, Multimedia and Electronics - Wireless Communication (elective course)
• Communications, Multimedia and Electronics - Multimedia Technology (elective course)
• Communications, Multimedia and Electronics - Electronics (elective course)
• Communications, Multimedia and Electronics - Networks of Electronic Communication (elective course)
• Electrical Engineering, Power Engineering and Management - Technological Systems (elective course)
• Electrical Engineering, Power Engineering and Management - Electrical Machines, Apparatus and Drives (elective course)
• Electrical Engineering, Power Engineering and Management - Electrical Power Engineering (elective course)
• Electrical Engineering, Power Engineering and Management - Economy and Management of Power Eng. (elective course)
• Electrical Engineering, Power Engineering and Management - Economy and Management of Electrical Eng. (elective course)
• Cybernetics and Robotics - Air and Space Systems (elective course)
• Communications, Multimedia and Electronics - Communication Systems (elective course)
• Open Informatics - New - Software Engineering (compulsory course in the program)