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. Your statements should be rigorous and justified, but not necessarily formal.

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 the (a,b)-tree. Describe operations Find, Insert, and Delete. Analyze their complexity in the worst case.
• Formulate cache-aware and cache-oblivious algorithms for transposition of a square matrix. Analyze their time complexity and I/O complexity.
• Define c-universal and k-independent systems of hash functions. State and prove the theorem on the expected chain length in hashing with chains. Show examples of c-universal and k-independent systems for hashing of integers.
• Describe and analyze hashing with linear probing.
• Define multi-dimensional range trees. Analyze time and space complexity of construction and range queries.
• Define suffix arrays and LCP arrays. Describe and analyze algorithms for their construction.

Minor questions

• Describe a flexible array with growing and shrinking. Analyze its amortized complexity.
• Define binary search trees with lazy balancing. Analyze their amortized complexity.
• Design operations Find, Insert, and Delete on a Splay tree. Analyze their amortized complexity.
• State and prove the theorem on amortized complexity on Insert and Delete on (a,2a-1)-trees and (a,2a)-trees.
• 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.
• Describe a system of linear hash functions. Prove that it is a 2-independent system from Z_p to [m].
• 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.
• 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.
• Show how to perform 1-dimensional range queries on binary search trees.
• Define k-d trees and show that they require Ω(sqrt(n)) time per 2-d range query.
• Show how to make multi-dimensional range trees dynamic (Insert suffices).
• Show how to use suffix array and LCP array for finding the longest common substring of two strings.
• Show how to parallelize an (a,b)-tree.
• Design and analyze a lock-free implementation of a stack.