CS224: Advanced Algorithms

Instructor and Contact Information

• Instructor: Galani Nelson
• TF (Teaching Fellow): Jeffrey
• Contact Email: cs224 df14 staff at cs.harvard.edu

Course Logistics

• Yellow Sheet: Fill out the yellow sheet circulating in the class.
• Course Website: Google "CS224 Advanced Algorithms" or "Galani Nelson" to find it.
• Mailing List: Sign up on the course website.

Grading Components

1. Scribing (10%)
   • Students take turns scribing lecture notes.
   • Use LaTeX template on the website.
   • Notes are due by 9 AM the next day.
   • Recorded lectures available.
2. Problem Sets (Psets) (60%)
   • Lawteched submission by email.
   • Page limits enforced.
   • Brief answers appreciated.
3. Final Project (30%)
   • Proposal due October 30th.
   • Final submission on the last day of the reading period.
   • Feedback on proposals provided.

Additional Course Requirements

• Grading Participation: Students may assist in grading (once per semester).
• Scribing: Students must scribe at least once, possibly twice.

Course Content Overview

• Comparison to CS124:
  • CS224 expands on algorithms with more theory and models of efficiency.
  • No programming assignments, but an option for a project involving implementation.
• Course Goals:
  • Enhance ability to analyze and create algorithms.
  • Explore new techniques and models of efficiency.

Models and Sorting

• Sorting Models Covered:
  • Van Emde Boas Trees
  • Fusion Trees
• Ram Model Assumptions:
  • Integer arithmetic, bitwise operations, and shifts in constant time.
• Word Size Assumption:
  • Word size (W) >= log n.

Detailed Topic: Van Emde Boas Trees

• Structure:
  • Recursive data structure.
  • Contains clusters and a summary.
• Operations:
  • Predecessor queries and Insertions both operate in O(log log U) time.
• Space:
  • U space initially, optimized to linear space using hashing.

Detailed Topic: Fusion Trees

• Efficiency:
  • Query in O(log base W n) time.
  • Linear space usage.
• Comparison:
  • Better for larger W values.

Advanced Sorting

• Improvements Over n log n:
  • Han and Thorup methods for faster sorting beyond the constraints of comparison-based models.
• Open Questions:
  • Linear time sorting in this model is still an open question.

Word RAM Model

• Operations:
  • Integer arithmetic, bitwise operations, and shifts in constant time.
• Space Management:
  • Managing space for Van Emde Boas Trees and X-fast tries for efficient queries.

Additional Resources

• Further Reading: Details on Van Emde Boas trees, Fusion Trees, and Y-fast tries available in the referenced papers.

Important Notes

• Preprocessing Time: Noted in Fusion Trees discussion as polynomial.
• Optimality: Known lower bound proofs for these data structures' efficiencies.

This summary captures the main concepts and logistics covered in this class session on advanced algorithms, focusing on various data structures and their efficiencies in sorting and query operations.