CS224 Advanced Algorithms Lecture Notes

Introduction

• Instructor: Gelani Nelson
• Teaching Fellow: Jeffrey
• Contact: [email protected]
• Course website available via Google search
• Mailing list signup encouraged

Logistics

• Grading Components
  • Scribing: 10% (students take turns writing up lecture notes)
  • Problem Sets (Psets): 60% (details on website)
  • Final Project: 30%
    • Proposal due: October 30th
    • Project due: Last day of reading period
    • Project feedback provided
• Psets must be submitted via email and adhere to page limits
• Students will also participate in grading at least once
• Scribe notes due the following day by 9:00 AM

Course Goals

• Increase ability to analyze and create algorithms
• Focus on theory rather than programming assignments
• Topics include efficiency analysis and different algorithm models

Course Content Overview

• Advanced topics in algorithms not covered in CS124
• Dynamic vs Static Structures:
  • Static: No insertions, only queries
  • Dynamic: Supports insertions and deletions
• Example of sorting algorithms and the static predecessor problem

Sorting and Predecessor Problem

• Predecessor problem: Find the maximum element less than a given element
• Challenge: Structuring data to allow fast queries and updates
• Models of Efficiency:
  • Comparison-based sorting: Worst case O(n log n)
  • Non-comparison based methods can achieve better bounds with different assumptions

Data Structures Discussed

1. Van Emde Boas Trees

• Structure: Utilizes a recursive layout with clusters
• Operations:
  • Supports update and query in O(log W) time
  • Space complexity: U (universe size)
• Optimization: Transition to linear space using hashing for non-empty clusters

2. Fusion Trees

• Achieve query time of O(log_W n) and linear space
• Potential for faster sorting algorithms compared to traditional methods

3. Y-Fast Trees

• Combines binary search trees with x-fast tries for efficient predecessor queries
• Space complexity reduced to linear

Conclusion

• Upcoming topics include Fusion Trees
• Aim to cover advanced data structures and algorithms in detail
• Important: No better than the established bounds for these data structures were found

Questions

• Encourage students to ask questions for clarification on topics covered.