CS224 Advanced Algorithms Lecture Notes

Instructor Information

• Name: Galani Nelson
• Teaching Fellow: Jeffrey
• Contact Email: cs224 df14 staff at C's. harvard.edu

Course Logistics

• Components:

  • Scribing (10%):
    • Students take turns writing notes on lectures.
    • The course is recorded for reference.
    • Use the provided LaTeX template on the course website.
  • Problem Sets (60%):
    • Must be submitted via email.
    • Limited page count for each problem set.
  • Final Project (30%):
    • Proposal due October 30th.
    • Submit final project last day of reading period.
    • Feedback will be provided on proposals.

• Grading:

  • Students may also serve as graders for a problem set (once per semester).

Course Overview

• Goals:
  • Increase ability to analyze and create algorithms.
  • Study different techniques and models for algorithm analysis.

Comparison with CS124

• CS224 is more theory-focused.
• No programming assignments; final project can involve implementation.
• More in-depth algorithms analysis compared to CS124.

Key Topics Covered

• Sorting Algorithms:

  • Can achieve faster than O(n log n) under certain conditions.
  • Exploring static predecessor problem related to sorting.
  • Static vs. Dynamic Data Structures:
    • Static: No insertions/deletions allowed.
    • Dynamic: Supports insertions/deletions.

• Dynamic Predecessor Problem:

  • Represents a set and supports queries for predecessors efficiently.
  • Traditional methods (e.g., binary search trees) provide O(log n) complexity.

Key Data Structures

• Van Emde Boas Trees:

  • Supports updates and queries in O(log W) time.
  • Uses O(U) space, but can be optimized for linear space.
  • Recursive structure with clusters.

• Fusion Trees:

  • Supports query in O(log base W of n) time.
  • Achieves linear space complexity.

Word RAM Model

• Assumes operations fit within a machine word (e.g., comparisons, bitwise operations).
• Key to develop faster algorithms beyond traditional comparison-based sorting.

Important Results

• Sorting Algorithms:
  • O(n sqrt(log n)) achievable with Dynamic Fusion Trees.
  • O(n log log n) deterministic sorting possible.

Predecessor Data Structure Techniques

• Insertion and Query Methods:

  • Recursive structure and binary search on clusters.
  • Use of summaries to track non-empty clusters.

• Space Complexity Analysis:

  • Space can be reduced using hash tables to store clusters, leading to linear space complexity.

Conclusion

• This lecture focused on dynamic predecessor problems and data structures, including Van Emde Boas Trees and Fusion Trees.
• Emphasized efficient query and insertion methods, and ensuring linear space usage.

Next Steps

• Upcoming topics include Fusion Trees in greater detail.