Algorithms for Engineering Informatics

Lecturer:

Josef Kokeš (gar.)

Tutor:

Josef Kokeš (gar.)

Synopsis:

Advanced level. Big-O notation. Algorithms with numbers - Cryptography, Universal hashing, Divide-and-conquer algorithms, Recurrence relations, Mergesort, The fast Fourier transform. Depth-fit search in undirected graph, Depth-fit search in directed graphs, Strongly connected components. Paths in graphs - Distances, Breadth-first search, Lengths on edges, Dijkstra's algorithm, Priority queue implementations, Shortest paths in the presence of negative edges, Shortest paths in dags. Greedy algorithms - Minimum spanning trees, Huffman encoding, Horn formulas.

Can be subscribed together with E371014.

Requirements:

Syllabus of lectures:

Big-O notation.

Algorithms with numbers - Cryptography, Universal hashing, Divide-and-conquer algorithms, Recurrence relations, Mergesort, The fast Fourier transform.

Depth-fit search in undirected graph, Depth-fit search in directed graphs, Strongly connected components.

Paths in graphs - Distances, Breadth-first search, Lengths on edges, Dijkstra's algorithm, Priority queue implementations, Shortest paths in the presence of negative edges, Shortest paths in dags.

Greedy algorithms - Minimum spanning trees, Huffman encoding, Horn formulas.

Syllabus of tutorials:

Study Objective:

Study materials:

S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani:Algorithm. Available on the department, ask lecturer (josef.kokes@fs.cvut.cz).

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans: