Description:

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

Contents:

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.

Seminar contents:

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.

Recommended 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

Keywords:

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

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar