CS224 Advanced Algorithms

Course Introduction

• Lecturer: Gelani Nelson
• TF: Jeffrey
• Contact: [email protected]
• Course Website: Google the course or lecturer's name - linked from the lecturer’s website
• Mailing List: Sign up on the course website

Course Components

• Scribing (10%): Note-taking for lectures, reviewed lectures are recorded
  • Use LaTeX template from the website
• Problem Sets (Psets, 60%): Submit via email, ensure it fits within page limits
• Final Project (30%): Proposal due October 30th, Project due last day of reading period
  • Can include implementation projects, details on the website

Additional Logistics

• Students may need to serve as graders once per semester
• Sign-up processes for scribing and grading are first come, first serve
• Scribe notes due by 9 AM the following day

Course Focus and Goals

• Covers advanced algorithmic techniques not seen in previous courses
• Theory-focused, no programming assignments (with exceptions for final projects)
• Objectives:
  • Enhance ability to analyze and create algorithms
  • Introduce new models and measures of efficiency
  • Explore parameters beyond basic running time and memory

Key Differences from CS124 Algorithms

• Advanced models for analyzing and creating algorithms
• Additional theoretical focus and measures beyond running time

Example Topic: Static Predecessor Problem

• Problem Definition: Find the largest element in a set that is less than a given element
• Static vs Dynamic:
  • Static: No insertions or deletions
  • Dynamic: Supports insertions and deletions
• Basic Solutions:
  • Binary Search Trees: Logarithmic time complexity for query and update
  • Sorting with Dynamic Predecessor Data Structure: Can beat O(n log n) time complexity

Van Emde Boas Trees (VEB Trees)

• Concept: Hierarchically structured data that uses divide-and-conquer methodology
• Structure:
  • Array of size sqrt(U), where U is the universe size
  • Summary of clusters and min/max elements
• Recursive Definition:
  • Divide element X into upper half C and lower half I
  • Store I in the Cth cluster and C in the summary if the cluster was empty
• Operations:
  • Predecessor Query: Use recursive calls and summary data for efficient lookup
  • Insertion: Swap X with min if X is smaller, insert recursively
• Complexity:
  • Time: O(log log U) for both queries and insertions
  • Space: O(U) initially, optimized to O(n) with improved techniques such as using hash tables

Fusion Trees

• Concept: Optimized data structure for integer keys
• Structure: Uses advanced bit manipulation
• Operations:
  • Query time: O(log_W N)
  • Space: Linear space, scalable for larger universes

Extensions and Open Questions

• Other Sorting Bounds:
  • O(n sqrt(log n)) sorting using Dynamic Fusion Trees
  • O(n log log n) deterministic sorting (Han, 2002)
  • O(n sqrt(log log n)) expected time randomized sorting (Han and Thorup, 2002)
• Word RAM Model: Allows for operations beyond simple comparisons

Indirection Technique

• Method to reduce space from O(n * w) to O(n) by grouping elements into super items and creating balanced BSTs*

Final Remarks

• Latest developments confirm optimality of stated bounds for linear space data structures