CS224 Advanced Algorithms Lecture Notes

Introduction

• Instructor: Jelani Nelson
• Teaching Fellow: Jeffrey
• Contact Email: cs224-f14-staff at cs.harvard.edu
• Course Website: Search for the course or instructor's name for the URL
• Mailing List: Sign up on the course website

Logistics

• Grading Components:
  • Scribing: 10%
    • Students take turns writing lecture notes in LaTeX.
  • Problem Sets (P-sets): 60%
    • Submit by email, adhere to page limits.
    • Solutions should be brief if the answer isn't known.
  • Final Project: 30%
    • Proposal due by October 30th.
    • Submit on the last day of the reading period.
    • Feedback will be given on proposals.
• Grading Requirements:
  • Students will take turns grading P-sets (at least once during the semester).

Course Goals

• Increase ability to analyze and create algorithms.
• Introduction to different techniques for analyzing algorithms not covered in previous courses (like CS124).
• Move towards theoretical analysis with a focus on various efficiency measures.

Course Content Overview

• Static Predecessor Problem:
  • Data structure to represent a set of items and support predecessor queries.
  • Static: Set of items does not change.
  • Dynamic: Allows insertions and deletions of items.
• Students are expected to know the efficiency of sorting algorithms (e.g., sorting n items cannot be done faster than n log n in a comparison-based model).

Dynamic Predecessor Data Structures

1. Van Emde Boas Trees

• Update/Query Time: O(log w)
• Space: Θ(U), where U is the universe size.
• Structure: Recursive data structure containing smaller van Emde Boas trees.

2. YFast Trees

• Uses hash tables for space efficiency.
• Matches the bounds of Van Emde Boas trees but reduces space requirements to linear.

3. Fusion Trees

• A related data structure also achieving O(n sqrt log n) for sorting.
• Details will be covered in the next lecture.

Key Concepts

• WordRAM Model:
  • Assumptions about the operations allowed on integers (bitwise operations, etc.).
  • Focus on integer sorting and predecessor queries.
• Sorting with Dynamic Predecessor:
  • Using predecessor data structures allows sorting faster than n log n in certain models.

Analyzing Running Time

• Recurrences for operations in van Emde Boas trees and YFast trees lead to logarithmic complexity.
• Discussion on handling updates, queries, and the space complexities of different structures.

Questions & Discussions

• Clarifications on the content covered.
• Emphasis on practical applications and theoretical implications of data structures in algorithm development.

Note: Further exploration of hashing and its applications in data structure efficiency will be addressed in future lectures.