CS224 Advanced Algorithms Lecture Notes

Instructor Information

• Name: Gelani Nelson
• TF: Jeffrey
• Contact: cs224.df14d.staff@cs.harvard.edu

Course Logistics

• Components of Grading:
  • Scribing: 10% of your grade (write lecture notes using provided LaTeX template)
  • Problem Sets (Psets): 60%, submitted by email, have page limits
  • Final Project: 30%, proposal due around October 30 and submission last day of the reading period
• Students will take turns being graders (1x during the semester)
• Scribes are expected to submit notes the day after lecture by 9:00 AM
• There’s a mailing list—please sign up on the course website

Course Goals

• Increase ability to analyze and create algorithms
• Focus on theory—no programming assignments; final project can be an implementation project
• Explore different efficiency models for analyzing algorithms

Course Content Overview

Algorithms vs. Previous Courses

• CS124 covered only a fraction of algorithms; CS224 continues with advanced topics
• More theory-focused with new algorithm models

The Importance of Efficiency Models

• Analyze not just running time and memory, but other parameters

Key Topics Covered

Sorting and Data Structures

• Dynamic Predecessor Problem: finding the maximum element less than a given value
• Static vs. Dynamic Predecessor:
  • Static: set doesn't change; dynamic: supports modifications like insertions
• Overview of potential solutions:
  • Using binary search on a sorted list (static, O(log n))
  • Balanced BSTs for dynamic queries (O(log n) for updates)

Introduction to Van Emde Boas Trees

• Designed by van Emde Boas in the 1970s
• Supports efficient updates and queries in O(log w) time where w = word size
• Space used is typically U (universe size), which can be huge (e.g., 2^64)

Fusion Trees

• Another key structure developed by Fredman and Willard in 1993
• Supports queries in O(log_w n) time and has linear space complexity
• Important for consideration of sorting algorithms

Word-RAM Model

• More than just comparison operations can be used (integer arithmetics, bitwise operations)
• Critical for developing faster algorithms than traditional comparison sorts (n log n)

Optimality and Open Questions

• The best deterministic sorting algorithm achieved is O(n log log n), while randomized approaches can reach O(n sqrt(log log n))
• Ongoing exploration for potential linear time sorting algorithms in the word-RAM model

Summary of Data Structures Presented

1. Van Emde Boas Trees:

   • Supports dynamic operations efficiently
   • Uses potentially large space (U) but can be adjusted to achieve linear space

2. Fusion Trees:

   • Better space efficiency, offers crucial performance improvements

3. Y Fast Tries and X Fast Tries:

   • Provide insights into predecessor operations, leveraging techniques like partial aggregation of elements

Conclusion

• The focus of CS224 will be on expanding existing knowledge of algorithms with theoretical frameworks and efficient implementations.

• Next class will cover Fusion Trees in more detail.