Here is a short list of goals for the test (and also my part of the exam):
Balanced Binary Search Trees
- Knowing what AVL tree and Red-Black trees are, their invariants, why they are efficient and basic understanding of their operations (insert, remove and search).
Self-Adjusting Data Structures
- Knowing what self-organizing lists are, some possible strategies
(MTF, TR and FC), and their r-competitiveness
- Knowing what a splay tree is, what splaying a node means
(including the zig, zig-zig and zig-zag operations) and why they are
efficient (intuition and basic understanding of its amortized analysis)
Probabilistic Data-Structures
- Knowing what randomized treaps and skip lists are, their efficiency (intuition and basics of its probabilistic analysis) and basic understanding of their operations (insert, remove and search).
- Knowing what bloom filters are, what they are best suited for, their efficiency (intuition) and basic understanding of its operations (insert and search).
Spatial Data-Structures
- Knowing what a quadtree is, its variations
(ex: point-region, matrix, point) and
basic understanding of its operations (find, insert, delete)
- Knowing what a kd-tree is, its variations (ex:
point-region) and basic understanding of its operations (find,
insert, delete, nearest neighbour, range search)
- Knowning what range trees are and understanding the concept of
fractional cascading
1D Data Structures
- Knowing the RMQ problem, its relation with LCA and
main algorithms given for it (sqrt buckets, sparse table and general
linear solution)
- Knowing the binary indexed tree (fenwick tree) data
structure, its operations (read and update) and how to apply it
- Knowing the segment tree data structure, its applicability
to several problems (ex: summing a range) and the concept of lazy propagation
String Matching
- Knowing what the string matching problem is about and understanding the naive, Knuth-Morris-Pratt (inclunding the π table) and Rabin-Karp algorithms.
- Knowing the concepts of tries (prefix trees), suffix trees, suffix arrays and LCP arrays, their complexity and the kind of problems they can solve.