Exams in Data Structures I

You should know all theory presented at the lecture: definitions of data structures and operations on them, all theorems and proofs thereof.

The exam is oral with written preparation. You will get one major and one minor question from the following list.

Major questions

Define the Splay tree. State and prove the theorem on amortized complexity of the Splay operation.
Define an (a,b)-tree. Describe operations Find, Insert, and Delete. Analyze their complexity in the worst case.
Define the Fibonacci heap. Describe operations on it and analyze their amortized time complexity.
Formulate a cache-oblivious algorithm for transposition of a square matrix. Analyze its time complexity and I/O complexity.
Compare different representations of static sets in cache-aware and cache-oblivious model: sorted array with binary search, (a,b)-tree, binary search tree in van Emde-Boas representation.
Describe and analyze FKS static perfect hashing.
Describe and analyze hashing with linear probing.
Describe and analyze Cuckoo hashing.
Define k-d trees. Analyze time and space complexity of construction and of range queries.
Define multi-dimensional range trees. Analyze time and space complexity of construction and range queries (including speedup by fractional cascading). Extend the structure by dynamic insertion of points.

Describe a dynamic array with growing and shrinking. Analyze its amortized complexity.
Define BB[α]-trees with lazy insertion. Analyze their amortized complexity.
Design operations Find, Insert, and Delete on a Splay tree. Analyze their amortized complexity.
State and prove the theorem on static optimality of Splay trees.
State and prove the theorem on amortized complexity on Insert and Delete on (a,2a-1)-trees and (a,2a)-trees.
Describe and analyze the A-sort algorithm.
Define the d-regular heap with Insert, ExtractMin, Decrease, and Build operations. Analyze its complexity with respect to the number of elements and the parameter d. Discuss choice of parameters for Dijkstra's algorithm.
Analyze k-way Mergesort in the cache-aware model. Which is the optimum value of k?
State and prove the Sleator-Tarjan theorem on competivity of LRU.
Define c-unversal and k-independent systems of hash functions. State and prove the theorem on the expected chain length in hashing with chains.
Describe a system of hash functions based on scalar products. Prove that it is a 1-universal system from Z_p^k to Z_p.
Describe a system of linear hash functions. Prove that it is a 2-independent system from Z_p to [m].
Construct a k-independent system of hash functions from Z_p to [m].
Construct a 2-independent system of hash functions for hashing of strings of length at most L over an alphabet [a] to a set of buckets [m].
Describe and analyze the Bloom filter.