discipline

Pure Math

subject

Data structures

lecturers

Zoltán Király

credits

2

period

2

curriculum

Data structures of graphs, queue. BFS and applications. Heaps. Enumerative ordering.

Kruskal's, Prim's and Dijkstra's algorithm, PERT method. 

Convex hull. Potential and amortizing time. Fibonacci heap and application to the algorithms of  Dijkstra and Prim. 

Binary search trees. Deletion in binary trees. 2-3 trees. B-trees. Red-black  trees. AVL trees. Sleator and Tarjan's splay tree.

Hashing: hash functions, birthday paradox. Sequencial search. Universal hash. Dynamic trees.

literature

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algortihms, MIT, 1990.

Form of tuition

lectures

mode of assessment

oral exam