Advanced Algorithms (COMPSCI 224), Lecture 1

Key Takeaways

• Course Logistics: The CS224 Advanced Algorithms course is graded on scribing (10%), problem sets (60%), and a final project (30%), with P-sets and the final project requiring written submissions in LaTeX. 1:49
• Course Focus: Unlike CS124, CS224 is more theory-focused with no programming assignments for p-sets, concentrating on advanced models and measures of algorithmic efficiency beyond just running time and memory. 7:25
• Breaking N Log N Sorting: While comparison-based sorting has an O(N log N) lower bound, the Word RAM model allows for faster sorting by leveraging operations beyond simple comparisons, especially with integer data fitting in machine words. 9:47
• Word RAM Model: This model assumes data items are integers within a W-bit word (Universe size U = 2^W), and operations like integer arithmetic, bitwise operations (XOR, OR, AND, negation), and bit shifting are executable in constant time. 17:20
• Predecessor Problem: The core problem discussed is finding the maximum element in a set S less than a given query value Z; it can be static (set doesn't change) or dynamic (supports insertions/deletions). 11:12
• Van Emde Boaz (vEB) Trees: These recursive data structures parameterize by universe size U, using a summary and clusters (each on a sqrt(U) universe). They achieve O(log W) time for dynamic updates and queries. 31:28
• vEB Space Optimization: Standard vEB trees use O(U) space, which is impractical for large W. This can be optimized to O(N) space (linear in the number of elements N, not universe size) by using hash tables to store only non-empty clusters. 55:14
• Fusion Trees: This alternative data structure supports predecessor queries in O(log base W of N) time and also uses linear space, offering an advantage when W (word size) is large relative to N (number of items). 23:02
• Optimal Bounds: Combining vEB/Y-fast trees (O(log W)) and Fusion trees (O(log base W of N)) yields an optimal query/update time of O(sqrt(log N)) in the Word RAM model for linear space data structures. 24:11
• Faster Sorting: Dynamic predecessor structures achieving O(sqrt(log N)) query/update time imply that sorting N numbers can be done in O(N * sqrt(log N)) time. 25:03
• Advanced Sorting Algorithms: Even faster Word RAM sorting algorithms exist, such as O(N log log N) deterministically or O(N * sqrt(log log N)) randomized, with O(N) linear time sorting remaining an open problem. 26:24
• Y-Fast Tries (Sketch): These also achieve O(log W) time and O(N) space by using an X-fast trie on a subset of items (N/W) and then balanced binary search trees for "super items," leveraging indirection. 1:22:18