CS224: Advanced Algorithms Lecture Notes

Instructor Info

• Instructor: Galani Nelson
• TF: Jeffrey
• Contact Email: [email protected]
• Course Website: Google "CS224 Harvard" or Galani Nelson's website.
• Mailing List: Sign up on the course website.

Course Logistics

Grading Components

1. Scribing: 10%
   • No textbook; students take turns scribing lecture notes.
   • Lectures are recorded.
   • Use the provided LaTeX template.
2. Problem Sets (Psets): 60%
   • Must be typeset in LaTeX.
   • Submit via email.
   • Observe page limits.
3. Final Project: 30%
   • Proposals due October 30th.
   • Project due last day of reading period.
   • Submit project by email for grading.

Additional Logistics

• Students will be graders for Psets, likely only once per semester.
• Scribe notes are due by 9 AM the following day.

Course Content

Course Goals

• Increase ability to analyze and create algorithms.
• Focus on theoretical aspects of algorithms not covered in CS124.
• Consider measures of efficiency beyond basic time and space.

Pre-requisites

• Knowledge of CS124 or equivalent, covering basic algorithms.

Key Topics

Sorting and Efficiency

• Sorting Assumption: Can't sort n numbers faster than n log n with comparison sort.
• Models of Computation: RAM model allows operations beyond comparison such as bit manipulations.
• Word RAM Model:
  • Items as integers in range 0 to 2^W - 1.
  • Assumes pointers fit in a word.

Predecessor Problem

• Static Predecessor Problem:
  • Data structure supporting predecessor queries.
  • Static vs Dynamic (supports insertions/deletions).
• Dynamic Predecessor Solutions:
  • Balanced Binary Search Trees for O(log n) time.
  • Advanced structures to beat O(log n).

Van Emde Boas Trees

• Structure:
  • Recursive structure with top and child clusters.
  • Stores minimum element separately.
  • Supports O(log log U) insertions and queries.
• Space Optimization:
  • Original O(U) space reduced to O(n) using hashing.

Fusion Trees

• Characteristics:
  • O(log base W n) query time.
  • Linear space.
  • Improves as W increases relative to n.

Advanced Topics

• Alternative Sorting Algorithms:
  • Han and Thorup for deterministic O(n log log n).
  • Randomized sorting approaches.
• Open Problems:
  • Faster than O(n log log n) sorting in RAM model.

Other Discussions

Dictionary Problem

• Hash Tables:
  • Key-value pairs with constant time operations.
  • Solutions exist for constant query and update times.

Indirection Technique

• Useful for improving both space and time complexity, e.g., in Y-fast tries.

Next Lecture Preview

• Fusion Trees: Further analysis and details.