CS224 高级算法 - 讲义

讲师信息

• 讲师: Gelani Nelson
• 助教 (TF): Jeffrey
• 联系: cs224-df14Dstaff@cs.harvard.edu
• 课堂上传递的黄色报名表
• 课程网站: 在谷歌搜索课程或讲师的名字，链接在讲师的网站上
• 在课程网站上注册邮件列表

课程安排

• 评分组件:
  • 记录讲义: 10%
    • 学生轮流记录讲义
    • 使用课程网站上的ltech模板
    • 可用录音来帮助创建笔记
  • 问题集 (Psets): 60%
    • 必须使用LaTeX打字
    • 页面限制强制执行
  • 期末项目: 30%
    • 提案截止日期为10月30日
    • 项目截止日期为阅读期的最后一天
    • 详情见课程网站
• 额外职责:
  • 评分: 学生将轮流评分问题集
  • 记录讲义: 至少一次，可能因为班级较小会有两次记录讲义的机会
  • 笔记需在第二天上午9点前交

课程介绍

• 先修课程: CS124或同等算法课程
• 课程重点:
  • 探讨CS124未涵盖的高级效率模型和分析
  • 更注重理论，无编程作业
  • 期末项目可以基于实现

课程目标

• 提高分析和创造算法的能力
• 介绍各种算法分析技术
• 探索不同的效率模型和评估标准

讨论的关键主题

排序算法

• 排序复杂度:
  • 传统界限: n log n
  • 在特定条件下可以更快，非比较排序

前驱问题

• 静态前驱问题:
  • 数据结构: 集合S，包含元素X1到Xn
  • 查询前驱X: S中小于X的最大元素
  • 目标: 低空间占用和快速查询时间

vEB树

• 结构:
  • 递归定义
  • 宇宙大小U，有平方根U个簇，每个簇大小为平方根U
  • 显式存储最小值和最大值
• 查询:
  • 查询时间: O(log log U)，相当于O(log W)
• 插入:
  • 特殊处理最小元素
  • 检查簇是否为空，如有需要插入摘要中
  • 插入时间: O(log log U)
• 空间:
  • 基本vEB使用O(U)空间
  • 可以通过哈希技术优化为线性空间

字存储器模型

• 假设:
  • 项为可以装入机器字的整数
  • 操作包括常数时间内的整数运算和位操作
  • 字大小W与宇宙大小U相关: W ≥ log N
• 更快的前驱数据结构:
  • Fusion Trees和Y-fast Trees
  • 证明的最优界: O(min(log W, log base W N))
  • Y-fast Trees: 使用间接技术的线性空间

进一步的排序算法

• 高级排序界限:
  • 可以达到O(N log log N)确定性
  • O(N sqrt(log log N))预期时间的随机算法
  • 开放问题: 在字存储器模型中实现线性时间排序

字典问题和哈希

• 字典问题:
  • 目标: 存储键值对，并高效查询和更新
  • 解决方案: 使用哈希表实现线性空间和常数时间操作

X-fast 和 Y-fast Tries

• X-fast Tries:
  • 使用位数组和完美二叉树
  • 在O(log log U)时间内搜索
  • 空间: O(N W)
• Y-fast Tries:
  • 通过使用间接技术改进x-fast
  • 结合x-fast和平衡BST，保持最佳时间和空间复杂度

结论

• 以线性空间实现前驱查询的最佳界限
• 下节课: Fusion Trees，数据结构的理论界限