SUBJECT

Title

Algorithms and data structures II.

Type of instruction

lecture + practical

Level

bachelor

Faculty

Faculty of Informatics

Part of degree program

Credits

3+2

Recommended in

Semester 4

Typically offered in

Spring semester

Course description

I. Hash coding

1. Hash tables, hash functions, open addresses;

2. Sorting in linear time: Radix sort, bucket sort

II. Graph algorithms

3. Representation of graphs;

4. Breadth-first search;

5. Single source shortest paths: Dijkstra’s algorithm, Bellman-Ford algorithm;

6. Minimum spanning trees: algorithms of Prim and Kruskal;

7. All pairs shortest pairs: Warshall-Floyd algorithm;

8. Depth-first search;
9. Topological sort;

10. Strongly connected components

III. Data compression

11. Huffman-coding;

12. Lempel-Ziv-Welch (LZW) algorithm

IV. String matching

13. Knuth-Morris-Pratt algorithm;

14. Quick search;

15. Rabin-Karp algorithm

Readings