Advanced Algorithms Course Overview

Sep 2, 2024

CS224 Advanced Algorithms Lecture Notes

Instructor Information

  • Instructor: Jelani Nelson
  • Teaching Fellow: Jeffrey (available for questions)
  • Contact Email: cs224-f14-staff@cs.harvard.edu

Course Logistics

  • Grading Components:
    • Scribing: 10%
      • Students take notes during lectures and submit them in LaTeX format.
      • Template available on course website.
    • Problem Sets (P-sets): 60%
      • Submitted via email with specified page limits.
    • Final Project: 30%
      • Proposal due by October 30th.
      • Final submission on the last day of the reading period.
      • Feedback provided on draft proposals.

Course Format

  • No textbook: Lecture notes and recorded lectures available for review.
  • Required Grading: Students may be assigned to grade P-sets (at least once per semester).
  • Scribing schedule: First-come, first-served basis; notes due by 9 PM the next day.

Course Goals

  • Focus:
    • Increase ability to analyze and create algorithms.
    • Explore different techniques for algorithm analysis.
    • Discuss efficiency measures beyond running time and memory usage.

Course Content Overview

  • Difference from CS124:
    • More theory-focused, no programming assignments except for final project.
    • Topics include advanced models for analyzing algorithms.

Key Concepts Introduced

  • Sorting Algorithms:
    • Example: Sorting n numbers faster than n log n under certain conditions.
    • Introduction of data structural problems, particularly the static predecessor problem.
  • Static vs. Dynamic Predecessor:
    • Static: Set S of items does not change.
    • Dynamic: Supports insertion and deletion of items.

Predecessor Problem

  • Definition: Given a set S, find the maximum element in S that is less than a specified value z.
  • Example solutions:
    • Use a binary search tree for static queries (O(log n)).
    • Use balanced BST for dynamic queries with O(log n) for updates.

Advanced Data Structures

  1. Van Emde Boas Trees

    • Recursive structure on a universe size U.
    • Supports queries and updates in O(log w) time.
    • Space complexity is O(u) but can be optimized to linear space with randomization.

  2. Fusion Trees

    • Supports query time of O(log_w n) and linear space.
    • Utilizes a balanced structure for efficient operations.

Sorting Implications

  • Both data structures can be used to create faster sorting algorithms, potentially achieving O(n sqrt(log n)) in certain conditions.
  • Open questions regarding the existence of linear time sorting algorithms in specific models.

WordRAM Model

  • Assumes the ability to perform operations like bitwise operations and arithmetic in constant time.
  • Discussion on how this model influences algorithm design and efficiency.

Summary of Data Structures and Performance

  • Van Emde Boas Trees
    • Recursive, efficient for predecessor problem, linear space achievable.
    • Useful for dynamic queries.
  • Fusion Trees
    • Efficient space usage with improved query time.
    • Balancing techniques discussed for optimization.

Final Thoughts

  • Importance of data structure choices in algorithmic efficiency.
  • Encouragement to explore beyond standard sorting methods for enhanced performance.

Note: Remember to check the course website for further details and updates.