CS224 Advanced Algorithms - Lecture Notes

Instructor and Admin Info

• Instructor: Gelani Nelson
• TF: Jeffrey
• Contact: [email protected]
• Course Website: Google "CS224 Gelani Nelson"
• Mailing List: Sign up on the course website

Course Logistics

Grading Components

1. Scribing: 10%
   • Students take turns taking notes on lectures
   • Use the LaTeX template on the website
   • Notes are due the following day by 9 AM
2. Problem Sets (Psets): 60%
   • All psets must be in LaTeX format
   • Submit by email
   • Psets have page limits
3. Final Project: 30%
   • Proposal due: October 30th
   • Final project due: Last day of reading period
   • Graded by the instructor

Additional Requirements

• Scribing: Minimum of once, possibly twice depending on class size
• Grading: Students will take turns being graders for psets, guided by the TF

Course Goals

• Increase ability to analyze and create algorithms
• Cover different techniques and models that were not included in CS124

Key Topics

Difference from CS124

• More theory-focused, no programming assignments except for the optional implementation in the final project
• Focus on different efficiency measures and models

Example Topic: Sorting

• Common Knowledge: Sorting n numbers can't be done faster than n log n using comparison sort
• Class Fact: Sorting can be faster than n log n with non-comparison based methods (e.g., RAM model)

RAM Model

• Assumptions:
  • Items are integers in the range 0 to 2^W - 1
  • W is the word size
  • Pointers fit in a word, so W >= log(n)
• Operations: Integer arithmetic, bitwise operations, bit shifting (constant time)

Predecessor Problem

• Static Predecessor Problem:
  • Data Structure: Set S of items {X1,...,Xn}
  • Query: Predecessor of Z is the maximum element in S less than Z
• Dynamic Predecessor Problem:
  • Supports insertions and deletions
  • Requires low space and fast query

Solutions

1. Binary Search Tree (BST)
   • Dynamic: Supports log(n) time for both queries and updates

Ven Emde Boas (VEB) Trees

• Structure: Divides universe into clusters and summary
• Operations:
  • Query: Time O(log log U)
  • Insert: Time O(log log U)
• Space: Initially U, can be reduced to linear space using hashing

X-Fast and Y-Fast Trees

• X-Fast Trees:
  • Binary tree with each internal node storing OR of children
  • Query Time: O(log log U) with bit shifting
  • Space: Linear with hashing
• Y-Fast Trees:
  • Uses indirection and binary search tree (BST)
  • Space: Linear
  • Query Time: O(log log U)

Other Advanced Techniques

• Dynamic Fusion Trees:
  • Fast queries and updates: O(log_W n), linear space
  • Leads to faster sorting algorithms

Advanced Sorting Algorithms

• Deterministic: O(n log log n) by Han and Thorup (2002)
• Randomized: O(n √log log n) expected time by Han and Thorup (2002)

Dictionary Problem

• Solved using hashing techniques for constant time operations

Remaining Topics and Future Coverage

• Fusion Trees: Covered next lecture
• Optimal Data Structures: Clarified with lower bounds

Questions and End of Lecture