📚

CS224 Advanced Algorithms Course Overview

Aug 5, 2024

CS224 Advanced Algorithms Lecture Notes

Introduction

  • Instructor: Gelani Nelson
  • Teaching Fellow: Jeffrey
  • Contact email: cs224 df14 D staff at C's.harvard.edu
  • Course website can be found via Google or instructor's personal webpage.

Logistics

  • Grading Components:

    • Scribing (10%): Taking notes during lectures. Course is recorded for reference.
    • Problem Sets (60%): Must be submitted via email; page limits apply to avoid excessive content.
    • Final Project (30%):
      • Proposal due: October 30th
      • Final submission: Last day of reading period.
      • Focus on written submissions; implementation projects allowed.
  • Students will take turns grading and scribing; first-come, first-served for signing up.

  • Scribe notes are due the following day by 9:00 AM.

Course Overview

  • Prerequisites: Familiarity with CS124 or equivalent algorithms course.
  • Course Goals:
    • Enhance ability to analyze and create algorithms.
    • Explore various techniques for algorithm efficiency and modeling.
  • Theoretical focus; no programming assignments, only written problem sets and the final project.

Key Concepts

  • Sorting and Efficiency:
    • Traditional sorting cannot be faster than O(n log n) under comparison-based models.
    • Introduction to the static predecessor problem as a related data structure problem.

Predecessor Problem

  • Definition: Predecessor of Z is the maximum element in set S such that X < Z.
  • Static vs Dynamic:
    • Static: No insertions/deletions; uses binary search.
    • Dynamic: Supports insertions/deletions; uses balanced binary search trees.

Dynamic Predecessor Solutions

  • Van Emde Boas Trees:
    • Update and query in O(log W) time; uses O(U) space.
    • Recursive structure based on partitioning universe size (U).
  • Fusion Trees:
    • Query in O(log_w(n)) time; uses linear space.
    • Efficient for both space and time.

Theoretical Underpinnings

  • Word RAM Model: Allows more than just comparisons; supports arithmetic operations, bit manipulation, etc.
  • Space Complexity: Utilization of linear space is essential for efficiency.

Advanced Data Structures

  • Y Fast Trees:
    • Combines benefits of previous models; maintains linear space with efficient query time.
    • Utilizes a balanced binary search tree for optimizing queries.
  • X Fast Trees:
    • Introduces hashing for managing non-empty clusters and optimizing space usage.

Conclusion

  • Summary of courses and discussions on data structures.
  • Questions encouraged for clarifications and deeper understanding.
  • Upcoming topics: Fusion Trees and additional advanced data structures.