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