CS224: Advanced Algorithms

Introduction

• Lecturer: Gelani Nelson
• TF: Jeffrey (back of the class)
• Contact: cs224 df14 D staff at C’s.harvard.edu
• Course website: Google the course name or lecturer's name
  • Website contains a mailing list, sign up required

Course Logistics

• **Grading Components:
  • Scribing (10%): Take turns taking notes, use recorded lectures and LWtech template from the website
  • Problem Sets (Psets) (60%): Must be in LWtech format and submitted via email, page limits enforced
  • Final Project (30%): Written project, details on website
    • Proposal due: October 30th
    • Project due: Last day of reading period
• Students may be required to help with grading at least once during the semester
  • Students also need to sign up for scribing at least once, notes due by 9 AM the next day**

Questions and Clarifications

• Concerns about scribing and grading logistics

Course Content Overview

• **Comparison to CS124: Broad coverage of algorithms, different efficiency models and measures, more theory focused, no programming assignments (except final project which can be implementation-based)
• Goals: Increase ability to analyze and create algorithms, introduce new techniques and models
  • Beyond running time and memory from CS124, introducing new parameters**

Models of Sorting and Predecessor Problem

• Reviewed concepts of sorting:
  • Analyzing efficiency: beyond n log n for sorting
  • Models differ, including data structures for predecessor problems
• Static Predecessor Problem: Data structure representing a set, supporting queries for the max element less than Z
  • Low space and fast query goals
  • Static: no insertions; Dynamic allows insertion and deletion
• Discussed BSTs, emphasized logging query times

Van Emde Boas Trees (VEB Trees)

• Efficient structure for dynamic predecessor problems:
  • Log W query and update time
  • O(U) space, improved to O(n) using hash tables
• Insertion and Search Algorithm
  • Split elements into clusters, recursively manage clusters and summary
  • Handle minimum separately to optimize query and insertion algorithms

Analysis and Optimization

• Recurrence relations analyzed for time and space, emphasizing improvements and the need for optimizations like hash tables
• Dynamic Predecessor Data Structures
  • Various approaches discussed (including Fusion Trees and Y-Fast Trees)
  • Emphasis on linear space and optimal query times

Ram Model and Word Size Assumptions

• Discussed additional operations available in the word RAM model
  • Constant time arithmetic, bitwise operations, bit shifting, multiplication assuming fit in two words

VEB Trees in Detail

• Recursive definition and data layout
• Methods for efficient insertion and searching, handling special scenarios like empty clusters
• Space optimization via hash tables

Y-Fast and X-Fast Trees

• Introduced by Willard (1983)
  • Combining hash tables and binary trees to achieve efficient space and time
  • Key techniques like binary search on ancestors in constant time

Additional Notes on Sorting

• Improvements over n log n for non-comparison based sorting
  • Advanced algorithms: randomized and deterministic approaches

Upcoming Topics

• Next class to cover Fusion Trees
  • Highlights optimal bounds for certain data structure operations

Key Takeaways

1. Course structure and grading expectations
2. Differences between CS224 and CS124
3. Overview of advanced sorting algorithms and data structures
4. In-depth look at VEB trees and their optimizations
5. Introduction to word RAM model and its implications