## CS224 Advanced Algorithms: Course Overview and Van Emde Boas Trees This document provides comprehensive notes for CS224 Advanced Algorithms, focusing on the concepts discussed in the first lecture. ### Course Logistics * **Grading:** The course grade is composed of three parts: * **Scribing (10%):** Students take turns creating lecture notes in LaTeX, using a provided template. Notes are due by 9:00 AM the following day. Sign up early to secure your preferred dates. * **Problem Sets (Psets) (60%):** Written assignments with page limits to encourage concise solutions. Submitted via email in LaTeX. Brief, well-explained solutions are appreciated. * **Final Project (30%):** A written project with a proposal due October 30th and the final submission on the last day of reading period. * **Grading Participation:** Students will participate in grading psets, typically once per semester, in teams with a teaching fellow (TF). This is a required component. Scribing and grading opportunities are first-come, first-served. The course is recorded, allowing students to review lectures. ### Course Goals The primary goals are to enhance students' abilities to: * Analyze the efficiency of algorithms using various models and measures beyond those covered in CS124. * Design and create new algorithms using the techniques and models learned in the course. Many students assume that sorting cannot be faster than n log n. This is only true for *comparison-based* sorting algorithms. ### The Static Predecessor Problem and the Word RAM Model The lecture introduces the static predecessor problem: given a set *S* of items, find the maximum element in *S* that is less than a given query element *Z*. Efficient solutions require low space usage and fast query times. The course uses the **Word RAM model**, where: * Items are integers in the range [0, 2^W-1], where *W* is the word size. * The universe size *U* is 2^W. * Pointers fit in a word, implying *W* ≥ log *n*, where *n* is the number of items. In a 64-bit machine, W = 64, and U = 2⁶⁴. This model allows operations beyond simple comparisons, such as bitwise operations and integer arithmetic, all in constant time. ### Data Structures for the Predecessor Problem Two data structures are presented that achieve sub-logarithmic time complexity: 1. **Van Emde Boas (vEB) Trees:** A dynamic data structure supporting both updates and queries in *O*(log *W*) time. However, it initially uses *O*(U) space, which is improved to *O*(n) using randomization and a hash table. 2. **Fusion Trees:** A static data structure (can be made dynamic) supporting queries in *O*(log_W *n*) time and linear space. This is faster than vEB trees when *W* is large. The choice between vEB trees and Fusion trees depends on the word size *W*. The optimal time complexity is min(log *W*, log_W *n*), which is at most √log *n*. #### Van Emde Boas Trees: Detailed Explanation vEB trees are defined recursively. A vEB tree on a universe of size *U* contains: * An array of √U vEB trees, each on a universe of size √U (called *clusters*). * A vEB tree of size √U (called *summary*), which tracks which clusters are non-empty. * `min` and `max` fields storing the minimum and maximum elements. **Query (Predecessor):** 1. Extract the high-order bits (*c*) and low-order bits (*i*) of the query element *x*. 2. If *x* > `max`, return `max`. 3. If cluster *c* is non-empty and its minimum is less than *x*, recursively find the predecessor of *i* in cluster *c*. 4. Otherwise, find the predecessor *c'* of *c* in the summary. Return the maximum element in cluster *c'*. **Insertion:** 1. If the tree is empty, set `min` to *x* and return. 2. If *x* < `min`, swap *x* and `min`. 3. Extract *c* and *i*. 4. If cluster *c* is empty, insert *c* into the summary and then insert *i* into cluster *c*. 5. Otherwise, insert *i* into cluster *c*. **Analysis:** * **Query Time:** *O*(log log *U*) = *O*(log *W*) * **Insertion Time:** *O*(log log *U*) = *O*(log *W*) * **Space:** Initially *O*(U), improved to *O*(n) using a hash table to store only non-empty clusters. Each cluster's minimum element is charged to its parent in the recursive structure. The initial *O*(U) space complexity arises from storing all clusters, even empty ones. Using a hash table to store only non-empty clusters reduces space to linear. #### Y-fast Tries Y-fast tries offer an alternative approach to achieve the same bounds as vEB trees, using a bit array and a perfect binary tree. The key idea is to use a hash table to store only the '1' bits at each level of the tree, reducing space to linear. Indirection is used to efficiently access ancestors in the tree during binary search. ### Further Considerations The lecture briefly touches upon faster sorting algorithms in the Word RAM model, including *O*(n log log n) deterministic and *O*(n √log log n) randomized algorithms. The possibility of a linear-time sorting algorithm remains an open question.