CS224 Advanced Algorithms - Lecture Notes

Introduction

• Instructor: Gelani Nelson
• Teaching Fellow: Jeffrey
• Contact: cs224 df14 D staff at cs.harvard.edu
• Fill out the yellow sheet being circulated
• Course Website: Search "CS224" or Gelani Nelson's name for the URL
• Sign up for the mailing list on the course website

Course Logistics

• Grading Components:

  1. Scribing (10%):
     • Students take turns writing lecture notes.
     • Notes due the following day by 9:00 AM.
     • Template available on the website.
  2. Problem Sets (60%):
     • Must be submitted by email.
     • Page limits apply.
  3. Final Project (30%):
     • Proposal due October 30.
     • Final project due last day of reading period.
     • Must be in writing.

• Students may need to grade problem sets (at least once) and scribe lectures (once or twice).

• Scribing and grading are on a first-come, first-serve basis.

Course Overview

• Course Focus: Advanced algorithms with more theoretical emphasis than CS124.
• Goals:
  • Improve ability to analyze and create algorithms.
  • Introduce new techniques and models for analyzing algorithms.

Key Concepts and Techniques

• Discussion on the static predecessor problem (data structure representing a set of items with queries for the maximum element less than a specified value).
• Distinctions between static (no insertions) and dynamic (supporting insertions and deletions) data structures.

Sorting Algorithms and Lower Bounds

• Sorting n numbers cannot be done faster than O(n log n) in a comparison-based model.
• Different approaches to achieve faster sorting using data structures like dynamic predecessor.

Data Structures

1. Van Emde Boas Trees:

   • Supports queries and updates in O(log W) time, where W is the word size.
   • Space complexity:
     • Initially O(U) (U = universe size), can be improved to Θ(N) with randomization.

2. Fusion Trees:

   • Query time: O(log_W N) with linear space.
   • Comparison with other data structures.

3. Y Fast Tries:

   • Achieves similar bounds as van Emde Boas Trees.
   • Introduces hashing techniques to optimize space complexity.

Conclusion

• The bounds discussed are optimal for linear space data structures.
• Next lecture: Fusion Trees and their applications in algorithm analysis.