Lecture Notes: CS224 Advanced Algorithms

Introduction

• Instructor: Gelani Nelson
• Teaching Fellow: Jeffrey
• Contact email: [email protected]
• Course website: Google Gelani Nelson or CS224.

Logistics

• Grading Components:

  • Scribing: 10%
  • Problem Sets (Psets): 60%
  • Final Project: 30%

• Scribing:

  • No textbook
  • Students take turns taking notes
  • Use LaTeX template
  • Course is recorded for reference

• Problem Sets:

  • Must be submitted in LaTeX
  • Submit via email
  • Has page limits

• Final Project:

  • Proposal due around October 30th
  • Project due by last day of reading period

• Additional Points:

  • Students will take turns grading
  • Sign up for scribing and grading is first-come first-served
  • Scribing notes due by 9 AM the following day

Course Goals

• Increase ability to analyze and create algorithms
• Explore different techniques and models for algorithm efficiency
• More theory-focused than CS124

Key Differences from CS124

• CS224 covers additional models and measures of algorithm efficiency
• No programming assignments except possible final project
• Focus on theoretical analysis

Models and Techniques Covered

• Sorting and Efficiency:

  • Challenges to sorting faster than n log n with comparison-based algorithms
  • Non-comparison based approaches possible in RAM model

• RAM Model:

  • Assumes integers within a certain range
  • Allows bitwise operations, arithmetic, etc.

Key Data Structures

• Van Emde Boas (VEB) Trees:

  • Dynamic data structure
  • Operations in log log U time
  • Initially uses u-space, but can be optimized to Theta n space with hashing

• Fusion Trees:

  • Support query in log base w of n time
  • Linear space
  • Faster than binary search trees

Sorting Algorithms

• Faster than n log n sorting possible with these data structures in RAM model
• Open problems in achieving linear time sorting

Dictionary Problem and Hashing

• Dictionary Problem:
  • Allows constant time query and insertion with hashing
  • Important for reducing space complexity in VEB trees

Further Topics

• Y-Fast Tries:
  • Achieve similar bounds as VEB trees but with linear space
  • Utilizes indirection

Observations

• Lecture Feedback: Understanding complex data structures and space-time trade-offs through examples
• Course Aim: Equip students with knowledge to apply efficient algorithms and data structures in theoretical and practical scenarios.