CS224: Advanced Algorithms Lecture Notes

Instructor and Course Information

• Instructor: Gelani Nelson
• Teaching Fellow: Jeffrey
• Contact: cs224 df14 D staff at cs.harvard.edu
• Course Website: Google search "CS224 Harvard" or "Gelani Nelson" for URL.
• Mailing List: Sign up on the course website.

Course Logistics

• Grading Components:
  • Scribing: 10% of the grade. Take lecture notes, use LATEX template from the website.
  • Problem Sets (P-Sets): 60% of the grade. Must be LATEXed and submitted by email.
  • Final Project: 30% of the grade. Proposal due by October 30, submission on the last day of the reading period.
• Scribing and Grading:
  • Students take turns scribing and grading.
  • Scribe notes due by 9:00 AM the following day after the lecture.
  • Grading is team-based, done with the TF once per P-Set.

Course Goals and Content

• Focus: Advanced techniques and theoretical approaches to algorithm analysis and design.
• No Programming Assignments: All written P-Sets, though final project may involve programming.
• Topics: New models and measures of efficiency beyond basic running time and memory.
• Comparisons:
  • CS124 vs. CS224: More theory, advanced models, and no programming.

Key Concepts Explored

• Sorting Algorithms:
  • Discussed limitations of comparison-based sorting (N log N).
  • Introduction to more efficient sorting methods using non-comparison-based models.
• Dynamic and Static Predecessor Problem:
  • Data structure goal: Support efficient queries with minimized space and fast access.
  • Explored binary search tree methods and advanced data structures.

Advanced Data Structures

Van Emde Boas Trees (VEB Trees)

• Purpose: Dynamic predecessor solution with efficient querying.
• Components:
  • Clusters and a summary structure, each handling square root of universe size.
  • Stores min and max to optimize searches.
• Operations:
  • Predecessor Query: Log-log U time complexity.
  • Insertion: Log-log U time complexity.
• Space Complexity: Originally U, optimized to linear using hashing.

Fusion Trees

• Purpose: Efficient static data structure for queries.
• Query Time: Log base W of N.
• Space: Linear.

Comparative Efficiency

• Sorting with Fusion Trees:
  • Potential for faster-than-N log N sorting using advanced structures.
• Han and Thorup's Results:
  • O(N log log N) deterministic sorting, O(N sqrt(log log N)) expected randomized sorting.

Word RAM Model

• Operations: Beyond mere comparison — includes bitwise operations and integer arithmetic.
• Assumptions: Items fit in a word, allowing complex manipulations beyond simple comparisons.

Additional Considerations

• Dictionary Problem: Efficient data structure to handle dynamic storage of key-value pairs.
• Utilization of Hash Tables: Key in reducing space in sophisticated trees like VEB.

Upcoming Topics

• Next Lecture: Discussion on Fusion Trees and their application.
• Optimality: Discussed optimality of VEB and Fusion Trees in linear space constraints.