CS224 Advanced Algorithms

Instructor Information

• Instructor: Gelani Nelson
• Teaching Fellow: Jeffrey
• Contact: cs224@df14.dstaff.cse.harvard.edu

Course Logistics

Components & Grading

1. Scribing (10%)
   • No textbook; students take turns scribing lecture notes
   • Use the provided LaTeX template
   • Lecture recording available for reference
   • Notes due next day, edited if needed
2. Problem Sets (60%)
   • LaTeX required for submissions via email
   • Adhere to page limits for brevity
3. Final Project (30%)
   • Written project due end of reading period
   • Proposal due October 30th
   • Read proposals and provide feedback

Additional Logistics

• Mailing List: Sign up on the course website
• Grading Participation: Students will take turns grading Psets with TF
• Sign-ups: First come, first serve for scribing and grading

Course Description

Prerequisites

• CS124 or equivalent algorithms course

Differences from CS124

• Focus on different measures of efficiency and models of algorithms
• Theory-focused, no programming assignments except optional project
• Introduces new techniques for analyzing and creating algorithms

Course Goals

• Enhance ability to analyze and create algorithms
• Explore different models for algorithm analysis beyond just running time and memory usage

Course Content

Initial Topic: Models of Efficiency for Algorithms

• Sorting: Cannot be done faster than N log N in general comparisons
• Predecessor Problem: Will be explored as a data structure problem

Data Structures & Algorithms Covered

Van Emde Boas Trees (Van Emde Boas Trees)

• Primary Problem: Static Predecessor Problem
• Structure: Hierarchical, recursive data structure
  • Contains \(
  • Summary structure maintaining non-empty clusters
  • Each cluster & summary could store \(\sqrt{U}\) items within a universe size \(U \)
• Operations:
  • Predecessor Query: \( \mathcal{O}( \log \log U)\)
  • Insertion: \( \mathcal{O}( \log \log U)\)
• Space: Initial order of \(U \); optimized with hashing to \( \Theta(N)\)
• Space Optimization: Store cluster indices and pointers in a hash table, resulting in linear allocated space

Y-fast Tries

• Derived from x-fast tries
• Uses hashing similar to optimized Van Emde Boas Trees

Advanced Techniques: Fusion Trees

• Efficient Queries: Supports queries \( \mathcal{O}( \log_{W} N)\)
• Efficient Inserts: Linear space complexity; outperforms traditional binary search trees when \(W > \log N\)

Summary

• Van Emde Boas Trees and Fusion Trees provide efficient solutions to predecessor queries within certain constraints.
• Essential knowledge includes the use of hashing and indirection to manage space and time complexity effectively.

Future Classes

• Explore Fusion Trees more deeply
• Discuss known optimal bounds for these data structures

Announcements & Reminders

• Stay tuned for the upcoming lecture on Fusion Trees.