๐Ÿ“š

Overview of Advanced Algorithms Course CS224

Apr 24, 2025

CS224 Advanced Algorithms

Logistics and Course Overview

  • Instructor: Galani Nelson
  • Teaching Fellow: Jeffrey
  • Contact: cs224 df14 staff at C's. harvard.edu
  • Yellow sheet going around for attendance
  • Course website: Google course name or instructor's name
  • Mailing list: Sign up on the course website

Course Components and Grading

  • Scribing: 10%

    • No textbook; students take turns writing lecture notes
    • Use the provided LaTeX template on the website
    • Course is recorded for reference
  • Problem Sets (P-sets): 60%

    • Must use LaTeX
    • Submit via email
    • Page limits enforced
  • Final Project: 30%

    • Proposal due October 30th
    • Project due last day of reading period
    • Feedback on proposals provided

Scribing and Grading

  • Students will rotate roles as scribes and graders
  • Scribe notes are due the following day, 9 AM
  • Graders work in teams with the TF
  • Be proactive in signing up for preferred dates

Key Differences from CS124

  • Focus on theoretical analysis of algorithms
  • No programming assignments for problem sets
  • Final project can include implementation

Course Goals

  • Enhance ability to analyze and create algorithms
  • Introduce new models and measures of algorithmic efficiency

Topics Covered

Sorting and Predecessor Problem

  • Sorting: Can be faster than O(n log n) under certain models
  • Static Predecessor Problem:
    • Data structure represents a set ( S ) of items
    • Support query for predecessor of an element ( x )

Data Structure Models

  • Dynamic vs Static Data Structures:
    • Static: Set elements donโ€™t change
    • Dynamic: Allows insertions and deletions

Advanced Data Structures

  • Van Emde Boas Trees:

    • Supports Dynamic Predecessor queries
    • Time complexity: O(log log U)
    • Space complexity can be reduced to linear with hashing
  • Fusion Trees:

    • Time complexity: O(log base W of N)
    • Space complexity: Linear

Word RAM Model

  • Supports various operations beyond comparisons
  • Assumes integers and pointers fit in a word

Other Sorting Algorithms

  • Han and Thorup (2002):
    • Deterministic: O(n log log n)
    • Randomized: O(n \sqrt{\log \log n})

Techniques Discussed

Van Emde Boas Trees

  • Recursive construction
  • Clusters and Summary structure
  • Efficient for small universe sizes

Y-Fast Tries

  • Use hashing to reduce space complexity to linear

Dictionary Problem

  • Dynamic dictionary with constant time queries and updates

Class Engagement

  • Opportunity for questions
  • Encouraged to participate and contact instructors for clarification

Next Lecture Preview

  • Exploration of Fusion Trees
  • Discussion of lower bounds for data structures