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.