CS224: Advanced Algorithms Lecture 1 Notes

Jul 20, 2024

CS224: Advanced Algorithms

Instructor and Contact Information

Course Information and Requirements

  • Course Website: Google the course or the instructor's name to find the website.
  • Mailing List: Sign up on the course website.

Course Components and Grading

  1. Scribing (10%):
    • Take turns taking lecture notes.
    • The course is recorded for reference.
    • Write up lecture notes using the LaTeX template on the website.
  2. Problem Sets (PSETs) (60%):
    • Submit PSETs via email.
    • Adhere to page limits.
  3. Final Project (30%):
    • Proposal due October 30th.
    • Project due on the last day of the reading period.
    • Details available on the course website.

Scribing and Grading Logistics

  • Scribing:
    • Due the following day at 9 AM.
    • Students might need to scribe more than once if the class size is small.
  • Grading:
    • Students will take turns grading PSETs along with the TF.
    • Can only be done once per semester, in teams of 3-4 students.

Course Goals

  • Enhance the ability to analyze and create algorithms.
  • Focus on different models for analyzing efficiency and measures of efficiency not covered in CS124.

Differences from CS124

  • More theory-focused; no programming assignments except for the final project (can be implementation-based).
  • Analysis of algorithms beyond running time and memory usage, including other efficiency parameters.

Course Content Overview

Analyzing Sorting Algorithms

  • Sorting n numbers can be faster than n log n in some models.
  • Predecessor Problem: Exploring fast static predecessor problem solutions.
  • Static vs Dynamic Structures:
    • Static Predecessor Problem: No insertions or deletions.
    • Dynamic Predecessor Problem: Allows insertions and deletions.

Binary Search Trees (BSTs)

  • Static and dynamic BSTs can help with predecessor queries.
  • Static Solution: Store numbers in order and perform binary search.
  • Dynamic Solution: Use balanced BSTs (e.g., red-black trees).

Advanced Data Structures

Van Emde Boas (VEB) Trees

  • Recursive Structure: VEB trees have recursive clusters of square root size.
  • Components: Minimum element, root U size summary, and clusters.
  • Insertions and Queries: Efficient insertion and predecessor queries using divide and conquer strategy.
  • Performance: O(log log U) time for insertion and queries due to balanced recursive depth.
  • Space: Originally U, optimized to O(n) using hash tables for non-empty clusters.

Fusion Trees

  • Paper: Fredman and Willard (1993).
  • Query Time: O(log^W n) with linear space.
  • Fusion Tree Property: Faster than binary search trees for large word sizes.

RAM Model Assumptions**

  • Items: Integer values fitting within word size (W bits).
  • Operations: Basic arithmetic, bitwise operations, shifting, all in constant time.

Hash Tables and Minimal Space Solutions

  • Dictionary Problem: Efficiently store key-value pairs.
  • Linear Space Hashing: Achievable with dynamic dictionaries.
  • X-Fast and Y-Fast Tries:
    • X-Fast Tries: Store bits in a binary tree with O(log log U) search time, using linear space with hash tables.
    • Y-Fast Tries: Use indirection to optimize space while maintaining efficient search times.

Optimality and Practical Considerations

  • Optimal Bounds: Van Emde Boas and Fusion trees achieve optimal bounds for their respective models.

Follow-up and Conclusion

  • Next lecture will cover Fusion Trees in detail.
  • Mention of optimal bounds paper.