CS224 Advanced Algorithms - Lecture Notes

Course Information

• Instructor: Jelani Nelson
• TF: Jeffrey (Contact via [email protected])
• Website: Google the course or Jelani Nelson for URL
• Mailing List: Sign up via course website

Logistics

• Grading Components:
  • Scribing: 10%
    • Students take turns making notes during lectures
    • Notes are written in LaTeX using a template from the website
  • Problem Sets (P-sets): 60%
    • Should be written in LaTeX, submitted via email
    • P-sets have page limits
  • Final Project: 30%
    • Proposal due October 30th
    • Project due last day of reading period
• Participation:
  • Students act as graders at least once
  • Scribe notes are due by 9 PM the following day

Course Goals

• Focus: Advanced algorithms with more theory
• No programming assignments, except for optional implementation project
• Models and Analysis: Learn different models and techniques for analyzing and creating algorithms

Topics Overview

• Comparison with CS124:
  • CS224 covers broader topics and different models of analysis
  • Focus on theoretical aspects and efficiency measures
• Sorting Algorithms:
  • Understand that sorting can be done faster than n log n under certain conditions

WordRAM Model

• Basics:
  • Items: Integers within a word range
  • Word size W and universe size U = 2^W
  • Pointers fit in a word, W >= log(n)
  • Operations: Integer arithmetic, bitwise operations, bit shifting
• Predecessor Problem:
  • Static Predecessor: Data structure with low space and fast query
  • Dynamic vs. Static: Supports insertions and deletions

Van Emde Boas Trees

• Structure:
  • Recursive data structure with clusters and a summary
  • Uses space of Theta(U), can be optimized to Theta(n) with hashing
• Operations:
  • Predecessor and Insertion both in O(log(log(U))) time
  • Min and Max elements are stored for efficient operations
• Challenges:
  • Initially uses U space, optimized using hashing for non-empty clusters

Y-Fast Tries

• Concept: Use hashing to reduce space from Theta(U) to Theta(n)
• Optimization: Indirection to balance space and time
• X-Fast Tries: Binary search on a tree with linked list optimization

Expected Learning

• Data Structures for Sorting:
  • Understand different data structures that can achieve better than n log n sorting
  • Explore models that challenge traditional assumptions of sorting

References

• Van Emde Boas Trees: Van Emde Boas, 1970s
• Fusion Trees: Fredman and Willard, 1993
• X-Fast/Y-Fast Tries: Willard, 1983
• Further Reading: Han, 2002; Han and Thorup, 2002 on advanced sorting algorithms

Conclusion

• Next Lecture: Focus on Fusion Trees
• Importance: Recognize lower bounds and optimal efficiency in data structures